栈和队列

栈

内容

栈：栈的抽象数据类型定义、栈的存储表示及基本操作实现、栈的应用

栈的定义（特点）

栈是一种后进先出（LIFO）的线性表，只能在一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。

打个比方：

有一个胡同很窄只能通过一辆车，而且是死胡同，只能从胡同口进出，如果第一个进入，出去会很麻烦，需要所有的车辆出去后才能出去，如图：

栈的存储表示

栈的存储表示有两种方式：顺序栈和链栈。顺序栈是用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，用一个变量top记录栈顶元素的位置。链栈是用链表存放数据元素，每个结点包含数据域和指针域，用一个指针top指向栈顶结点。

顺序存储方式

链式存储方式

栈的基本操作

栈的基本操作有以下几种：

• 初始化：创建一个空栈
• 判空：判断栈是否为空
• 进栈：在栈顶插入一个元素
• 出栈：删除并返回栈顶元素
• 取栈顶：返回但不删除栈顶元素

栈的顺序存储方式和基本操作实现

顺序栈的定义

//定义顺序栈结构体类型
#define MaxSize 50 //定义栈的最大长度
typedef struct{int data[MaxSize]; //存放栈中元素int top; //栈顶指针
}SqStack;

顺序栈的初始化

//初始化栈
void InitStack(SqStack &S){S.top = -1; //将栈顶指针置为-1，表示空栈
}

顺序栈的判空

//判断栈是否为空
bool Empty(SqStack S){return S.top == -1; //栈顶指针为-1，说明栈为空
}

顺序栈的判满

//判断栈是否已满
bool Full(SqStack S){return S.top == MaxSize - 1; //栈顶指针为MaxSize-1，说明栈已满
}

顺序栈的进栈

//进栈
bool Push(SqStack &S, int x){if(Full(S)) return false; //栈已满，无法进栈S.data[++S.top] = x; //栈顶指针加1，将元素x放入栈顶return true;
}

顺序栈的出栈

//出栈
bool Pop(SqStack &S, int &x){if(Empty(S)) return false; //栈为空，无法出栈x = S.data[S.top--]; //将栈顶元素赋值给x，栈顶指针减1return true;
}

取栈顶元素

//取栈顶元素
bool GetTop(SqStack S, int &x){if(Empty(S)) return false; //栈为空，无法取栈顶元素x = S.data[S.top]; //将栈顶元素赋值给xreturn true;
}

main函数测试

//测试代码
int main(){SqStack S;InitStack(S);if (Empty(S))printf("栈为空\\n");if (Full(S)){printf("栈满\\n");} else{printf("栈未满\\n");};for(int i = 1; i <= 10; i++){Push(S, i);}int x;GetTop(S,x);printf("%d ", x);printf("\\n");while(!Empty(S)){Pop(S, x);printf("%d ", x);}printf("\\n");return 0;
}

栈的链式存储方式和基本操作实现

链栈的定义

//定义链栈结构体类型
typedef struct LinkNode{int data; //存放栈中元素struct LinkNode *next; //指向下一个结点的指针
}LinkNode, *LinkStack;

链栈的初始化

//初始化栈
void InitStack(LinkStack &S){S = NULL; //将栈顶指针置为NULL，表示空栈
}

链栈的判空

//判断栈是否为空
bool Empty(LinkStack S){return S == NULL; //栈顶指针为NULL，说明栈为空
}

链栈的进栈

//进栈
bool Push(LinkStack &S, int x){LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode)); //分配新结点空间if(p == NULL) return false; //分配失败，返回falsep->data = x; //将元素x赋值给新结点p->next = S; //新结点的指针域指向栈顶结点S = p; //栈顶指针指向新结点return true;
}

链栈的出栈

//出栈
bool Pop(LinkStack &S, int &x){if(Empty(S)) return false; //栈为空，无法出栈LinkNode *p = S; //p指向栈顶结点x = p->data; //将栈顶元素赋值给xS = p->next; //栈顶指针指向下一个结点free(p); //释放原栈顶结点空间return true;
}

取栈顶元素

//取栈顶元素
bool GetTop(LinkStack S, int &x){if(Empty(S)) return false; //栈为空，无法取栈顶元素x = S->data; //将栈顶元素赋值给xreturn true;
}

main函数测试

int main(){LinkStack S;InitStack(S);if (Empty(S))printf("栈为空\\n");for(int i = 1; i <= 10; i++){Push(S, i);}int x;GetTop(S,x);printf("%d ", x);printf("\\n");while(!Empty(S)){Pop(S, x);printf("%d ", x);}printf("\\n");return 0;
}

栈的应用

栈的应用有很多，例如：

• 括号匹配：用一个栈存放左括号，遇到右括号时出栈并匹配，最后判断栈是否为空

• 表达式求值：用两个栈分别存放操作数和运算符，按照运算符优先级和结合性进行计算

• 递归实现：用一个栈存放函数调用时的参数、返回地址和局部变量，实现递归过程

括号匹配(注意栈中数据元素类型改为char)

1. switch语句匹配实现

   //栈的应用:括号匹配
   bool BracketMatch(char exp[]){SqStack S; //定义一个顺序栈//LinkStack S;//定义一个链栈InitStack(S); //初始化栈for (int i = 0; exp[i] !='\\0'; ++i) { //遍历表达式switch(exp[i]){ //根据字符类型进行分类讨论case '(':case '[':case '{':Push(S, exp[i]); //左括号进栈break;case ')':case ']':case '}':if(Empty(S)) return false; //栈为空，说明右括号多余char topElem;Pop(S, topElem); //取出栈顶元素if((exp[i] == ')' && topElem != '(') || //右括号与左括号不匹配(exp[i] == ']' && topElem != '[') ||(exp[i] == '}' && topElem != '{')){return false;}break;default:break;}}return Empty(S); //如果栈为空，说明括号匹配
   }
   

2. if…else…判断语句实现

   //栈的应用:括号匹配
   bool BracketMatch(char exp[]){SqStack S;InitStack(S);for(int i = 0; exp[i] != '\\0'; i++){if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{'){ //左括号进栈Push(S, exp[i]);}else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}'){ //右括号出栈if(Empty(S)) return false; //栈为空，说明右括号多余char topElem;Pop(S, topElem); //取出栈顶元素if(exp[i] == ')' && topElem != '(') return false; //右括号与左括号不匹配if(exp[i] == ']' && topElem != '[') return false; //右括号与左括号不匹配if(exp[i] == '}' && topElem != '{') return false; //右括号与左括号不匹配}}return Empty(S); //如果栈为空，说明括号匹配
   }
   

main函数测试

int main(){char exp1[] = "((()))";char exp2[] = "(()())";char exp3[] = "(()))";char exp4[] = "((){}[])";char exp5[] = "((){[}])";if(BracketMatch(exp1)) printf("exp1匹配\\n");else printf("exp1不匹配\\n");if(BracketMatch(exp2)) printf("exp2匹配\\n");else printf("exp2不匹配\\n");if(BracketMatch(exp3)) printf("exp3匹配\\n");else printf("exp3不匹配\\n");if(BracketMatch(exp4)) printf("exp4匹配\\n");else printf("exp4不匹配\\n");if(BracketMatch(exp5)) printf("exp5匹配\\n");else printf("exp5不匹配\\n");return 0;
}

表达式求值

计算中缀表达式的值的代码是一种利用栈结构来实现的方法，它需要用到两个栈，一个用于存储操作数，一个用于存储运算符。它的基本思路是：

1. 从左到右扫描中缀表达式，遇到操作数就压入操作数栈，遇到运算符就进行比较。
2. 如果运算符栈为空，或者栈顶运算符为左括号，或者当前运算符优先级高于栈顶运算符，就直接压入运算符栈。
3. 如果当前运算符为右括号，就依次弹出运算符栈顶的运算符，并从操作数栈中弹出相应的操作数，进行计算，并将结果压入操作数栈，直到遇到左括号为止，然后弹出左括号。
4. 如果当前运算符优先级低于或等于栈顶运算符，就弹出栈顶运算符，并从操作数栈中弹出相应的操作数，进行计算，并将结果压入操作数栈，然后再次比较当前运算符和新的栈顶运算符，重复这个过程，直到满足条件2或者扫描完毕为止。
5. 当中缀表达式扫描完毕后，如果运算符栈中还有运算符，就依次弹出，并从操作数栈中弹出相应的操作数，进行计算，并将结果压入操作数栈，直到运算符栈为空为止。
6. 此时操作数栈中只有一个元素，就是最终的计算结果。

两个栈的代码

#include <cstdio>
#define MaxSize 50
//定义一个存储字符的栈结构
typedef struct {char data[MaxSize]; //用数组存储栈元素int top; //用一个变量记录栈顶位置
}SqStackChar;//定义一个存储双精度浮点数的栈结构
typedef struct {double data[MaxSize]; //用数组存储栈元素int top; //用一个变量记录栈顶位置
}SqStackDouble;//初始化字符栈，将栈顶位置设为-1，表示空栈
void InitStack(SqStackChar &S){S.top = -1;
}
//初始化双精度浮点数栈，将栈顶位置设为-1，表示空栈
void InitStack(SqStackDouble &S){S.top = -1;
}//判断字符栈是否为空，如果为空返回true，否则返回false
bool Empty(SqStackChar S){return S.top ==-1;
}
//判断双精度浮点数栈是否为空，如果为空返回true，否则返回false
bool Empty(SqStackDouble S){return S.top ==-1;
}
//判断字符栈是否为满，如果为满返回true，否则返回false
bool Full(SqStackChar S){return S.top == MaxSize-1;
}
//判断双精度浮点数栈是否为满，如果为满返回true，否则返回false
bool Full(SqStackDouble S){return S.top == MaxSize-1;
}
//将一个字符压入字符栈，如果成功返回true，否则返回false
bool Push(SqStackChar &S,char n){if (Full(S))return false; //如果栈满，无法压入，返回falseS.data[++S.top] = n; //将字符n存入栈顶位置，并将栈顶指针加一return true; //返回true表示成功
}
//将一个双精度浮点数压入双精度浮点数栈，如果成功返回true，否则返回false
bool Push(SqStackDouble &S,double n){if (Full(S))return false; //如果栈满，无法压入，返回falseS.data[++S.top] = n; //将双精度浮点数n存入栈顶位置，并将栈顶指针加一return true; //返回true表示成功
}
//将一个字符从字符栈弹出，并赋值给n，如果成功返回true，否则返回false
bool Pop(SqStackChar &S,char &n){if (Empty(S))return false; //如果栈空，无法弹出，返回falsen = S.data[S.top--]; //将栈顶元素赋值给n，并将栈顶指针减一return true; //返回true表示成功
}
//将一个双精度浮点数从双精度浮点数栈弹出，并赋值给n，如果成功返回true，否则返回false
bool Pop(SqStackDouble &S,double &n){if (Empty(S))return false; //如果栈空，无法弹出，返回falsen = S.data[S.top--]; //将栈顶元素赋值给n，并将栈顶指针减一return true; //返回true表示成功
}//取字符栈的栈顶元素，并赋值给n，如果成功返回true，否则返回false
bool GetTop(SqStackChar S,char &n){if (Empty(S))return false; //如果栈空，无法取得元素，返回falsen = S.data[S.top]; //将栈顶元素赋值给nreturn true;//返回true表示成功
}

利用中缀转后缀的思想完成求值

//返回运算符的优先级
int Precedence(char op){switch(op){case '+': //加号的优先级为1case '-': return 1; //减号的优先级为1case '*': //乘号的优先级为2case '/': return 2; //除号的优先级为2case '(': return 0; //左括号的优先级为0，最低}
}//对两个操作数进行运算
double Operate(double a, char op, double b){switch(op){case '+': return a + b; //加法运算case '-': return a - b; //减法运算case '*': return a * b; //乘法运算case '/': return a / b; //除法运算，注意除数不能为0}
}//计算中缀表达式的值
double EvaluateExpression(char exp[]){SqStackChar notation; //定义一个存储运算符的栈SqStackDouble number; //定义一个存储运算数的栈InitStack(notation); //初始化运算符栈InitStack(number); //初始化运算数栈int i=0;while (exp[i] !='\\0'){ //遍历中缀表达式的每个字符if(exp[i] >= '0' && exp[i] <= '9') { //如果是数字double x = 0;while (exp[i] >= '0' && exp[i] <= '9') { //将数字字符转换为数字x = x * 10 + exp[i] - '0';i++;}Push(number, x); //将数字压入操作数栈} else{ //如果是符号if (Empty(notation)) {Push(notation, exp[i]) ;//符号栈中无符号，直接入栈i++;continue;}if (exp[i] == '('){Push(notation, exp[i]) ;//符号为左括号，入栈i++;continue;}char op ;GetTop(notation,op); //获取符号栈顶的运算符if (exp[i] == ')') { //符号为右括号while (true) {Pop(notation, op); //弹出符号栈顶的运算符if (op != '(') { //如果不是左括号，说明还在括号内部，需要计算double a = 0, b = 0;Pop(number, b); //弹出操作数栈顶的两个数作为运算数Pop(number, a);Push(number, Operate(a, op, b)); //将运算结果压入操作数栈} else { //如果是左括号，说明括号内部已经计算完毕，跳出循环i++;break;}}} else if ( Precedence(exp[i]) > Precedence(op) ){ //如果当前符号的优先级大于符号栈顶的优先级，直接入栈Push(notation, exp[i]) ;i++;continue;} else{ //如果当前符号的优先级小于等于符号栈顶的优先级，需要先计算前面的表达式，再入栈Pop(notation,op); //弹出符号栈顶的运算符double a , b ;Pop(number,b); //弹出操作数栈顶的两个数作为运算数Pop(number,a);Push(number,Operate(a,op,b)); //将运算结果压入操作数栈}}}while (!Empty(notation)){ //当中缀表达式遍历完毕后，如果符号栈还有元素，继续计算直到为空char op;Pop(notation,op); //弹出符号栈顶的运算符double a , b ;Pop(number,b); //弹出操作数栈顶的两个数作为运算数Pop(number,a);Push(number,Operate(a,op,b)); //将运算结果压入操作数栈}double result;Pop(number, result); //弹出操作数栈的栈顶元素作为表达式的值return result;
}

main函数

int main(){char exp[MaxSize];//char exp[] = "20*(10+10)";printf("请输入中缀表达式：\\n");scanf("%s", exp);printf("中缀表达式的值为：%lf", EvaluateExpression(exp));return 0;
}

递归实现

栈的应用：递归实现是一个常见的数据结构和算法的话题。递归是一种程序设计技巧，它可以让一个函数直接或间接地调用自身，从而将一个复杂的问题分解为更小的子问题。递归的实现需要借助栈这种数据结构，因为栈具有后进先出的特点，可以保存函数调用时的返回地址、参数、局部变量等信息，以便在函数返回时恢复现场。

概述：

• 递归函数通常有三个部分：递归终止条件、递归前进段和递归返回段。当终止条件满足时，递归返回；当终止条件不满足时，递归前进；递归返回段是在每次递归调用之后执行的操作。
• 递归函数在调用自身之前，会将当前的状态（包括参数、局部变量、返回地址等）压入栈中，形成一个调用帧；在调用自身之后，会从栈中弹出上一层的状态，恢复现场。所有的调用帧形成一个调用栈。
• 递归函数可以看作是两个过程：“递"和"归”。"递"是指不断地向更小的子问题前进，直到达到终止条件；"归"是指从最小的子问题开始返回，依次执行返回段的操作，直到回到最初的问题。

优点：

• 代码简洁清晰，可读性更好
• 可以解决一些循环难以解决或无法解决的问题
• 可以利用栈实现反向输出或倒序遍历

缺点：

• 时间和空间消耗比较大，因为每次调用都需要分配栈空间和压入弹出数据
• 很多计算都是重复的，因为同一个子问题可能会被多次调用
• 调用栈可能会溢出，因为栈的大小是有限的

针对栈的缺点可以进行尾递归优化

尾递归是一种特殊的递归形式，它是指在函数的最后一步调用自身，而不需要做任何其他的操作。尾递归可以避免栈溢出的风险，也可以节省空间和时间，因为它不需要保存每次调用的状态，只需要保留一个栈帧即可。

//一个简单的递归函数，计算n的阶乘
int factorial(int n){if(n == 0 || n == 1){ //递归终止条件，当n为0或1时，返回1return 1;}else{ //递归调用，当n大于1时，返回n乘以n-1的阶乘return n * factorial(n-1);}
}//一个简单的非递归函数，计算n的阶乘
int factorial(int n){int result = 1; //定义一个变量存储结果for(int i = 1; i <= n; i++){ //循环从1到n，依次乘以iresult *= i;}return result; //返回结果
}//一个尾递归函数，计算n的阶乘
int factorial(int n, int acc){ //定义一个累积参数acc，用来存储中间结果if(n == 0 || n == 1){ //递归终止条件，当n为0或1时，返回accreturn acc;}else{ //递归调用，在最后一步将n-1和n乘以acc作为参数传入return factorial(n-1, n * acc);}
}//调用尾递归函数时，需要将初始值1作为acc参数传入
int result = factorial(5, 1); //计算5的阶乘

队列

队列是一种先进先出（FIFO）的线性表，只允许在一端（称为队头）进行删除操作，而在另一端（称为队尾）进行插入操作。队列中没有元素时，称为空队列。

队列的存储表示有两种方式：顺序存储和链式存储。

队列的基本操作有以下几种：

• 初始化操作：InitQueue(Q)。构造一个空队列Q。
• 判空操作：QueueEmpty(Q)。判断队列Q是否为空，若为空则返回true，否则返回false。
• 入队操作：EnQueue(Q)。将元素x插入到队列Q的队尾。
• 出队操作：DeQueue(Q,x)。删除队列Q的队头元素，并用x返回其值。
• 取队头操作：GetHead(Q,x)。用x返回队列Q的队头元素，但不删除该元素。

队列的链式存储

队列的链式存储是指使用链表来实现队列的存储结构。相比于顺序存储，链式存储不需要预先分配一定大小的空间，可以动态地分配和释放内存，因此更加灵活。同时，链式存储也避免了顺序存储中可能出现的“假溢出”问题。

方式1

定义

//
// Created by lenovo on 2023/4/17.
//
#include <cstdlib>
#include <cstdio>// 链式队列结点
typedef struct LinkNode {int data; // 数据域LinkNode *next; // 指针域
}LinkNode;// 链式队列结构体
typedef struct {LinkNode *front, *rear; // 队头指针和队尾指针
}LinkQueue;

初始化

// 初始化队列
void InitQueue(LinkQueue &Q){Q.front = Q.rear = (LinkNode*) malloc(sizeof(LinkNode)); // 初始化队头指针和队尾指针Q.front->next = NULL; // 队头指针的下一个结点为空
}

判空

// 判断队列是否为空
bool Empty(LinkQueue Q){return Q.front == Q.rear; // 队头指针等于队尾指针，说明队列为空
}

入队列

// 入队列
void EnQueue(LinkQueue &Q, int x){LinkNode *s = (LinkNode*) malloc(sizeof(LinkNode)); // 创建新结点s->data = x; // 将元素x放入新结点的数据域s->next = NULL; // 新结点的指针域为空Q.rear->next = s; // 将新结点插入队尾Q.rear = s; // 队尾指针指向新结点
}

出队列

// 出队列
bool DeQueue(LinkQueue &Q, int &x){if (Q.front == Q.rear) return false; // 队列为空，无法出队列LinkNode *s = Q.front->next; // 指向队头结点x = s->data; // 将队头元素赋值给xQ.front->next = s->next; // 队头指针指向下一个结点if (Q.rear == s) Q.rear = Q.front; // 如果队列为空，队尾指针置为NULLfree(s); // 释放原队头结点空间return true;
}

取队头元素

// 取队头元素
bool GetHead(LinkQueue Q, int &x){if (Empty(Q)) return false; // 队列为空，无法取队头元素x = Q.front->next->data; // 将队头元素赋值给xreturn true;
}

main 方法测试

int main(){LinkQueue Q;InitQueue(Q); // 初始化队列if (Empty(Q)) printf("队列为空\\n"); // 判断队列是否为空EnQueue(Q, 1); // 入队列EnQueue(Q, 2);EnQueue(Q, 3);EnQueue(Q, 4);EnQueue(Q, 5);int x;GetHead(Q, x); // 取队头元素printf("队头元素：%d\\n", x);while (!Empty(Q)){ // 遍历队列DeQueue(Q, x); // 出队列printf("%d ", x);}printf("\\n");if (Empty(Q)) printf("队列为空\\n"); // 判断队列是否为空return 0;
}

方式2

//队列的抽象数据类型定义
typedef struct LinkNode{int data; //数据域struct LinkNode *next; //指针域
}LinkNode, *LinkQueue;//队列的存储表示与基本操作实现
//初始化队列
void InitQueue(LinkQueue &Q){Q = (LinkNode*)malloc(sizeof(LinkNode)); //创建头结点Q->next = NULL; //头结点的指针域置为NULL
}//判断队列是否为空
bool Empty(LinkQueue Q){return Q->next == NULL; //头结点的指针域为NULL，说明队列为空
}//进队列
void CreateList_Tail(LinkQueue &L){int x;//输入的数据LinkNode *tailNode = L; //tailNode指向尾结点，初始时指向头结点scanf("%d",&x); //读入第一个数据while (x!=9999){ //用9999作为结束标志LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode)); //分配新结点空间if (s == NULL) exit(-1); //分配失败退出s->next = NULL; //尾结点的指针域置空s->data = x; //新结点的数据域赋值为xtailNode->next = s; //原尾结点的指针域指向新结点tailNode = s; //tailNode指向新的尾结点scanf("%d",&x); //读入下一个数据}// tailNode->next =NULL
}//出队列
bool DeQueue(LinkQueue &Q, int &x){if(Empty(Q)) return false; //队列为空，无法出队列LinkNode *p = Q->next; //p指向队头结点x = p->data; //将队头元素赋值给xQ->next = p->next; //队头指针指向下一个结点if(Q->next == NULL) Q = NULL; //如果队列为空，队尾指针置为NULLfree(p); //释放原队头结点空间return true;
}//取队头元素
bool GetHead(LinkQueue Q, int &x){if(Empty(Q)) return false; //队列为空，无法取队头元素x = Q->next->data; //将队头元素赋值给xreturn true;
}int main(){LinkQueue Q;InitQueue(Q);if (Empty(Q))printf("队列为空\\n");CreateList_Tail(Q);int x;GetHead(Q,x);printf("对头元素：%d\\n",x);while(!Empty(Q)){DeQueue(Q, x);printf("%d ", x);}printf("\\n");return 0;}

循环队列（顺序）

循环队列是一种线性数据结构，它具有队列的所有特点，同时在实现上采用了循环数组的思想，可以更高效地利用存储空间。

在循环队列的实现中，需要维护队头指针和队尾指针，它们的初始值都为0，表示空队列。

当队列中有元素进队列时，队尾指针加1；当队列中有元素出队列时，队头指针加1。

为了实现循环，当队尾指针到达数组的末尾时，需要将其置为0，从而形成一个循环。

定义

//
// Created by lenovo on 2023/4/17.
//
#include <cstdlib>
#include <cstdio>#define MAXSIZE 5//队列的抽象数据类型定义
typedef struct{int data[MAXSIZE]; //存放队列元素int front, rear; //队头指针和队尾指针
}SqQueue;

初始化

//队列的存储表示与基本操作实现
//初始化队列
void InitQueue(SqQueue &Q){Q.front = Q.rear = 0; //队头指针和队尾指针置为0，表示空队列
}

判空

//判断队列是否为空
bool Empty(SqQueue Q){return Q.front == Q.rear; //队头指针等于队尾指针，说明队列为空
}

判满

//判断队列是否已满
bool Full(SqQueue Q){return (Q.rear + 1) % MAXSIZE == Q.front; //队尾指针的下一个位置等于队头指针，说明队列已满
}

入队列

//进队列
bool EnQueue(SqQueue &Q, int x){if(Full(Q)) return false; //队列已满，无法进队列Q.data[Q.rear] = x; //将元素x放入队尾Q.rear = (Q.rear + 1) % MAXSIZE; //队尾指针加1return true;
}

出队列

//出队列
bool DeQueue(SqQueue &Q, int &x){if(Empty(Q)) return false; //队列为空，无法出队列x = Q.data[Q.front]; //将队头元素赋值给xQ.front = (Q.front + 1) % MAXSIZE; //队头指针加1return true;
}

取对头元素

//取队头元素
bool GetHead(SqQueue Q, int &x){if(Empty(Q)) return false; //队列为空，无法取队头元素x = Q.data[Q.front]; //将队头元素赋值给xreturn true;
}

main方法测试

int main(){SqQueue Q;InitQueue(Q);if (Empty(Q))printf("队列为空\\n");EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);if (Full(Q))printf("队列为满\\n");int x;GetHead(Q,x);printf("对头元素：%d\\n",x);while(!Empty(Q)){DeQueue(Q, x);printf("%d ", x);}printf("\\n");return 0;}