栈和队列

1、栈

1.1、栈的基本概念

1.1.1、栈的定义

栈（Stack）：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在一端进行插入和删除操作。如图：

栈顶（Top）：线性表允许进行插入和删除的那一端。

栈底（Bottom）：固定的，不允许进行插入和删除的另一端。

空栈：不含任何元素的空表。

特点：后进先出。

1.1.2、栈的基本操作

InitStack(&S)：初始化一个空栈 S；StackEmpty(S)：判空；Push(&S,x)：进栈，若栈 S 未满，将 x 加入使之成为新栈顶；Pop(&S,&x)：出栈，若栈 S 非空，弹出栈顶元素，并用 x 返回；GetTop(S,&x)：读栈顶元素，若栈 S 非空，用 x 返回栈顶元素；ClearStack(&S)：销毁栈。

1.2、栈的顺序存储结构

1.2.1、顺序栈的实现

栈的顺序存储也称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个栈顶（Top）指针。

栈的顺序存储类型可描述为：

#define MaxSize 50 //定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //存放栈中元素 int top; //栈顶指针 }SqStack;

栈顶指针：S.top，初始时设置 S.top = -1；栈顶元素：S.data[S.top]。

进栈操纵：栈不满时，栈顶指针先加 1，再送值到栈顶元素。

出栈操作：栈非空时，先去栈顶元素，在将栈顶指针减 1。

栈空条件：S.top == -1；栈满条件：S.top == MaxSize - 1；栈长：S.top + 1。

栈顶指针与栈中元素之间的关系：

1.2.2、顺序栈的基本运算

初始化

void InitStack(&S){ S.top = -1; //初始化栈顶指针 }

判栈空

bool StackEmpty(S){ if(S.top == -1) return true; else return false; }

进栈

bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) //栈满，报错 return false; S.data[++S.top] = x; //指针先加 1，再入栈 return true; }

出栈

bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) //栈满，报错 return false; x = S.data[S.top--]; //先出栈，指针再减 1 return true; }

读栈顶元素

bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; return true; }

1.2.3、共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图：

1.3、栈的链式存储

这里规定链栈没有头结点，LHead 指向栈顶元素，如图：

栈的链式存储类型描述为：

typedef struct LinkNode{ ElemType data; //数据域 struct LinkNode *next； //指针域 }*LiStack;

---

2、队列

2.1、队列的基本概念

2.1.1、队列的定义

队列（Queue）：队列简称队，也是一种操作受限的线性表，只允许在表的一端插入，而在表的另一端进行删除。先进先出。

队头（Front）：允许删除的一端，又称为队首。

队尾（Rear）：允许插入的一端。

空队列：不包含任何元素的空表。

2.1.2、队列常见的基本操作

InitQueue(&Q)：初始化一个空队列；QueueEmpty(Q)：判空；EnQueue(&Q,x)：入队；DeQueue(&Q,&x)：出队；GetHead(Q,&x)：读队头元素。

2.2、队列的顺序存储结构

2.2.1、队列的顺序存储结构

设队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front,rear; //队头队尾指针 }SqQueue;

初始状态（队空条件）：Q.front == Q.rear == 0；

进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1。

出队操作：队不空时，先取队头元素值，再将队头指针加 1。

2.2.2、循环队列

初始时：Q.rear = Q.front = 0；

队首指针进 1：Q.front = (Q.front + 1)%MaxSize；

队尾指针进 1 ：Q.rear = (Q.rear + 1)%MaxSize；

队列长度：(Q.rear - Q.front + MaxSize)%MaxSize。

但是还是会出现队空和队满条件一样的情况，即条件都是 Q.rear == Q.front。为了区分队空还是队满，可以采取以下三种方法：

牺牲一个单元来区分队空和队满；类型中增加表示元素个数的数据成员；类型中增加 tag 数据成员，bool 值表示队空和队满。

2.2.3、循环队列的基本操作

初始化

void InitQueue(&Q){ Q.front = Q.rear = 0; //初始化队首队尾指针 }

判空

bool isEmpty(Q){ if(Q.rear == Q.front) return true; else return false; }

入队

bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear+1) % MaxSize == Q.front) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1)% MaxSize; return ture; }

出队

bool DeQueue(SqQueue &Q,ElemType &x){ if(Q.rear == Q.front) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1)% MaxSize; return ture; }

2.3、队列的链式存储结构

typedef struct{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue;

2.4、双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，如图：

---

3、栈和队列的应用

3.1、栈在括号匹配中的应用

算法的基本思想：

初始化一个空栈，顺序读入括号；若是右括号，则或者置于栈顶的最急迫期待得以消除，或者是不合法的情况，或者是不合法的情况（括号序列不匹配，退出程序）；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性将一级。算法结束时，栈为空，否则括号序列不匹配。

3.2、栈在表达式求值中的应用

将中缀表达式转换成后缀表达式的算法思想如下：

从左向右开始扫描中缀表达式；

遇到数字时，加入后缀表达式；

遇到运算时：

若为 “(” ，入栈；若为 “)” ，则依次把栈中的运算符加入后缀表达式中，直到出现 “)”，从栈中删除 “(”；若为除括号外的其他运算符，当其优先级高于除 “(” 以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级相等的运算符，直到一个比它优先级低或者遇到一个左括号为止。

当题目要求直接变换成后缀或前缀表达式时：

第一步：按照运算符的优先级对所有的运算单位加括号。

第二步：把运算符号移动到对应的括号前面；然后把括号去掉，就变成了前缀表达式；

第三步：把运算符号移动到对应的括号后面，然后把括号去掉，就变成了后缀表达式。

3.3、栈在递归中的应用

3.4、队列在层次遍历中的应用

3.5、队列在计算机系统中的应用