栈是限定仅在表尾进行插入插入和删除操作的线性表； 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

4.1 开场白

4.2 栈的定义

4.2.1 栈的定义

栈是限定仅在表尾进行插入插入和删除操作的线性表。 　　允许插入和删除的一端称为栈顶（top），另一端称为栈底（button）。不含任何数据元素的栈称为空栈，栈又称为后进先出（Last In First Out)的线性表，简称LIFO结构。 　　栈是一个特殊的线性表，特殊之处在于限制了插入和删除的位置，它始终只在栈顶进行，这也就使得：栈底是固定的，最先进栈的只能在栈底。 　　栈的插入操作：叫做进栈，也称压栈、入栈；删除操作：叫做出栈，也叫做弹栈。 　　

4.2.2 进栈出栈变化形式

最先进栈的元素，不一定是最后出栈。在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以了。

4.3 栈的抽象数据类型

ADT 栈 （stack） Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继的关系。 Operation InitStack（*S）：初始化操作，建立一个空栈； DestroyStack（*S)：若栈存在，则销毁它； ClearStack（*S）：将栈清空； StackEmpty（S）：若栈为空，返回TRUE，否则返回false； GetTop（S, *e）：若栈存在且非空，用e 返回S的栈顶元素； Push（*S，e）：若栈存在，插入新元素e到S中并成为栈顶元素； Pop（*S，e):删除栈S中栈顶元素，并用e返回其值； StackLength（S）：返回栈S中的元素个数。

4.4 栈的顺序存储结构及实现

4.4.1 栈的顺序存储结构

简称为顺序栈。数组实现，下标为0的一端作为栈底。 栈的结构定义

#define MAXSIZE 20; typedef int SElemType; typedef struct{ SElemType data[MAXSIZE]; int top; //用于栈顶指针； }SqStack;

4.4.2 栈的顺序存储结构——进栈操作

//插入元素e为新的栈顶元素 Status Push(SqStack *S, SElemType e) { if (S->top == MAXSIZE - 1) return ERROR; S->top++; S->data[S->top] = e; return OK; }

4.4.3 栈的顺序存储结构——出栈操作

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status Pop(SqStack *S, SElemType *e) { if (S->top == -1) return ERROR; *e = S->data[S->top]; S->top--; return OK; }

两者的时间复杂度都是O(1)，由于不存在线性表的插入和删除需要移动元素问题， 栈的顺序存储结构还是很方便的。但是有一个很大的缺陷：必须事先确定数组存储空间的大小。

4.5 两栈共享空间

两个相同类型的栈，可以最大限度第利用其事先开辟的存储空间来进行操作。关键思路：它们是在数组的两端，向中间靠拢。 空间结构代码：

//两栈共享空间结构 typedef struct { SElemType data[MAXSIZE]; int top1; //栈1的栈顶指针 int top2; //栈2的栈顶指针 }SqDoubleStack; //插入元素e为新的栈顶元素 Status Push(SqDoubleStack *S, SElemType e, int stackNumber) { if (S->top1 + 1 == S->top2) return ERROR; if (stackNumber == 1) S->data[++S->top1] = e; else if (stackNumber == 2) S->data[++S->top2] = e; return OK; } //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber) { if (stackNumber == 1) { if (S->top == -1) return ERROR; *e = S->data[S->top1--]; } else if (stackNumber == 2) { if (S->top2 == MAXSIZE) return ERROR; *e = S->data[S->top2++]; } return OK; }

两栈共享空间，适用于两个栈的空间需求具有相反关系时，即一个栈增长时另一个栈在缩短的情况。

4.6 栈的链式存储结构及实现

4.6.1 栈的链式存储结构

简称为链栈。栈顶放在单链表的头部，对于链栈来说，不需要头指针的，用栈顶代替。 链栈的结构

//链栈的结构代码如下： typedef struct StackNode { SElemType data; struct StackNode * next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;

4.6.2 栈的链式存储结构——进栈操作

//插入元素e为新的栈顶元素 Status Push(LinkStack *S, SElemType e) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = e; s->next = S->top; S->top = s; S-count++; return OK; }

4.6.3 栈的链式存储结构——出栈操作

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK； Status Pop(LinkStack *S, SElemType *e) { LinkStackPtr p; if (StackEmpty(*S)) return ERROR; *e = S->top->data; p = S->top; S->top = S->top->next; free(p); S->count--; return OK; }

时间复杂度都为O(1)。 对比顺序栈和链栈：

时间复杂度都为O(1)；顺序栈需要事先确定一个固定的长度，存在空间浪费，但优势是存取定位很方便。链栈则要求每个元素都有指针，增加了内存开销，但对于栈的长度无限制如果栈的使用过程中元素变化不可预料，最后有链栈；反之，它的变化在可控范围内，建议使用顺序栈。

4.7 栈的使用

栈的引入简化了程序设计的问题，划分了不同的关注层次，使得思考范围缩小，更加聚焦与我们要解决的问题核心。

4.8 栈的应用——递归

4.8.1 斐波那契数列实现

f(n)=⎧⎩⎨0,1,F(n−1)+F(n−2),当 n = 0 时当n = 1 时当n>1 打印出前40位斐波那契数列

int main() { int i; int a[40]; a[0] = 0; a[1] = 1; printf("%d", a[0]); printf("%d", a[1]); for (i = 2; i < 40; i++){ a[i] = a[i-1] + a[i-2]; printf("%d", a[i]); } return 0; }

递归来实现

int main() { int i; int a[40]; a[0] = 0; a[1] = 1; printf("%d", a[0]); printf("%d", a[1]); for (i = 2; i < 40; i++){ a[i] = a[i-1] + a[i-2]; printf("%d", a[i]); } return 0; }

4.8.2 递归定义

把一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称做递归函数。 每个递归定义必须至少有一个条件，满足时递归不再进行，即不在引用自身而是返回值退出。 迭代使用循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、简单，但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代不需要反复调用函数和占用额外的内存。应该视情况不同选择不同的代码。 编译器使用栈实现递归。

4.9 栈的应用——四则运算表达式求值

4.9.1 后缀（逆波兰）表示法定义

不需要括号的后缀表示法，称为逆波兰表示。是表达式的一种新的显示方式，非常巧妙地解决了程序实现四则运算的难题。 对于“9+（3-1）*3+10 / 2”,用后缀表示法式“ 9 3 1- 3* + 10 2/ +”

4.9.2 后缀表达式计算结果

用后缀表示法式“ 9 3 1- 3* + 10 2/ +” 规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。 下面推导如何让9+（3-1）*3+10 / 2”,用后缀表示法式“ 9 3 1- 3* + 10 2/ +”

4.9.3中缀表达式转后缀表达式

平时用的标准四则运算表达式称中缀表达式。 中缀表达式9+（3-1）*3+10 / 2”,转化为后缀表达式“ 9 3 1- 3* + 10 2/ +” 规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。 要想让计算机具有处理标准表达式的能力：

将中缀表达式转化为后缀表达式；将后缀表达式进行运算得出结果。

4.10 队列的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端是队尾，允许删除的一端称为队头。

4.11 队列的抽象数据类型

ADT 栈 （Queue） Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继的关系。 Operation InitQueue（*Q）：初始化操作，建立一个空队列Q； DestroyQueue（*Q)：若队列存在，则销毁它； ClearQueue（*Q）：将队列清空； QueueEmpty（Q）：若为空，返回TRUE，否则返回false； GetHead（Q, *e）：若队里存在且非空，用e 返回队列的队头元素； EnQueue（*Q,e):若队列存在，插入新元素e到Q中并成为队尾元素； DeQueue（*Q，*e):删除队列中队头元素，并用e返回其值； QueueLength（Q）：返回队列中的元素个数。

4.12 循环队列

4.12.1 队列顺序存储的不足

插入队尾时间为O(1)，删除队头时间为O(n)。

4.12.2 循环队列定义

把队列的这种头尾相接的顺序存储结构称为循环队列。 引入两个指针front指针指向队头元素，rear指向队尾元素的下一个位置。若队列的最大尺寸为QueueSize，则队列慢的条件为（rear+1）%QueueSize == front 通用的计算队列长度公式为： （rear-front + QueueSize） % QueueSize

typedef int QElemType; typedef struct { QElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针，指向队尾元素的下一个位置 }SqQueue; //初始化一个空队列Q Status InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; } //返回Q的元素个数，即队列的当前长度 int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; } //插入元素e为新的队尾元素 Status EnQueue(SqQueue *Q, QElemType e) { if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR; Q->data[Q->rear] = e; Q->rear = (Q->rear+1) %MAXSIZE; return OK; } //若队列不空，则删除Q中队头元素，用e返回其值 Status DeQueue(SqQueue *Q, QElemType *e) { if (Q->front == Q->rear) return ERRROR; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return OK; }

4.13 队列的链式存储结构及实现

就是线性表的单链表，只不过它只能尾进头出而已， 简称为链队列。 链队列的结构为：

typedef int QElemType; typedef struct QNode{ QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front, rear; }LinkQueue;

4.13.1 队列的链式存储结构——入队操作

入队操作时，其实就是在链表尾部插入节点：

//插入元素e为Q的新的队尾元素 Status EnQueue(LinkQueue *Q, QElemType e) { QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if (!s) exit(OVERFLOW); s->data = e; s->next = NULL; Q->rear->next = s; Q->rear =s; return OK; }

4.13.2 队列的链式存储结构——出队操作

//若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p; if (Q->front == Q->rear) return ERROR; p = Q->front->next; *e = p->data; Q->front->next = p->next; if (Q->rear == p) Q->rear = Q->front; free(p); return OK; }

对于循环队列与链队列的比较，从时间上，它们的时间都为O(1)。空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题，而链队不存在这个问题，所以，链队列更加灵活。

4.14 总结回顾

4.15 结尾语