第五节 栈

一、栈的基本概念

栈(Stack)：也是运算受限的线性表。是一种先进后出(First In Last Out ，简称FILO)的线性表。只允许在表的一端进行插入和删除。

栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。

栈底(Bottom)：是固定端，又称为表头。

空栈：当表中没有元素时称为空栈。

栈的示意图（src: ）

二、栈的抽象数据类型

ADT Stack{

数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 }

数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n }

约定a1端为栈底，an端为栈顶。

基本操作：

InitStack()：初始化一个栈；

IsStackEmpty()：若栈为空，则返回true ，否则返回flase ；

⋯⋯

InsertStack(x) ：向栈中插入元素x；

DeleteStack(x) ：删除栈顶元素x；

}

三、栈的顺序存储结构实现

（src: ）

习惯上，栈顶（top）指针指示的是栈顶元素的上一个位置。

SeqStack.h （顺序栈类型的定义、以及操作的声明）

#ifndef __SEQSTACK_H__ /* 防止多次包含头文件带来的重复定义错误 */#define __SEQSTACK_H__typedef int ElementType; /* 假设数据元素的类型为整型 */typedef struct SequenceStack {    ElementType *data; /* 定义一个动态数组 */    int top; /* 栈顶 */    int capacity; /* 数组的容量 */} SequenceStack;/* 初始化一个容量为n的栈 *//* 成功返回0，失败返回-1 */int initSeqStack(SequenceStack *stack, int n);/* 获取栈的长度 */int getSeqStackLength(const SequenceStack *stack);/* 判断栈是否为空 *//* 空则返回true/1，非空返回false/0 */int isSeqStackEmpty(const SequenceStack *stack);/* 判断栈是否满 *//* 满则返回true/1，不满返回false/0 */int isSeqStackFull(const SequenceStack *stack);/* 把元素入栈（压栈） *//* 成功则返回新的长度，失败返回-1 */int pushSeqStack(SequenceStack *stack, ElementType e);/* 弹出栈顶元素（弹栈） *//* 成功则返回新的长度，失败返回-1 */int popSeqStack(SequenceStack *stack, ElementType *e);/* 查看栈顶元素（只看，不取出） *//* 成功则返回0，失败返回-1 */int peakSeqStack (const SequenceStack *stack, ElementType *e);/* 销毁栈 */void destroySeqStack(SequenceStack *stack);#endif

SeqStack.c （栈操作的定义）

#include <stdlib.h> /* for malloc(), free() */#include “SeqStack.h”/* 初始化一个容量为n的栈 *//* 成功返回0，失败返回-1 */int initSeqStack(SequenceStack *stack, int n){/* 动态分配数组 *//* 如何初始化top? */    return 0;}/* 获取栈的长度 */int getSeqStackLength(const SequenceStack *stack){    return 0;}/* 判断栈是否为空 *//* 空则返回true/1，非空返回false/0 */int isSeqStackEmpty(const SequenceStack *stack){    return 0;}/* 判断栈是否满 *//* 满则返回true/1，不满返回false/0 */int isSeqStackFull(const SequenceStack *stack){    return 0;}/* 把元素入栈（压栈） *//* 成功则返回新的长度，失败返回-1 */int pushSeqStack(SequenceStack *stack, ElementType e){/* */    return 0;}/* 弹出栈顶元素（弹栈） *//* 成功则返回新的长度，失败返回-1 */int popSeqStack(SequenceStack *stack, ElementType *e){/* */    return 0;}/* 查看栈顶元素（只看，不取出） *//* 成功则返回0，失败返回-1 */int peakSeqStack (const SequenceStack *stack, ElementType *e){    return 0;}/* 销毁栈 */void destroySeqStack(SequenceStack *stack){}

四、栈的应用

（一）后缀表达式求值

我们把平时所用的标准四则运算表达式叫做中缀表达式，例如9+(3-1)*3+8÷2，因为所有的运算符号都在两数字的中间。

而后缀表达式则是将运算符放在操作数的后面,如9 3 1 – 3 * + 8 2 / +。后缀表达式中没有括号, 只表达了计算的顺序, 而这个顺序恰好就是机器最喜欢的方式。

计算后缀表达式需要用一个栈来存储运算数，规则如下：

从左到右遍历表达式的每个数字和符号

遇到是数字就进栈；遇到是符号，就将处于栈顶和次栈顶的两个数字出栈，进行运算，运算结果再次进栈。

对于上述的后缀表达式9 3 1 – 3 * + 8 2 / +，计算过程如下：

后缀表达式“9 3 1 – 3 * + 8 2 / +”的计算过程

待处理的表达式

从左到右扫描表达式

栈（栈底->栈顶）

9 3 1 – 3 * + 8 2 / +

数字9，直接压栈

9

3 1 – 3 * + 8 2 / +

数字3，直接压栈

9 3

1 – 3 * + 8 2 / +

数字1，直接压栈

9 3 1

- 3 * + 8 2 / +

运算符-，弹栈2次，得到1和3，进行运算3-1=2，压栈

9 2

3 * + 8 2 / +

数字3，直接压栈

9 2 3

* + 8 2 / +

运算符*，弹栈2次，得到3和2，进行运算2*3=6，压栈

9 6

+ 8 2 / +

运算符+，弹栈2次，得到6 和9.进行运算9+6=15，压栈

15

8 2 / +

数字8，压栈

15 8

2 / +

数字2，压栈

15 8 2

/ +

运算符/，弹栈2次，得到2和8，进行运算8/2=4，压栈

15 4

+

运算符+，弹栈2次，得到4和15，进行运算15+4=19，压栈

19

表达式结束，弹栈，结果为19

（二）中缀表达式转为后缀表达式

需要使用一个栈来存储运算符，转换的规则为：

1.是数字，直接输出

2.是运算符

2.1 : “(” 直接入栈

2.2 : “)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出

2.3: 其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到比当前符号优先级更低的符号或者”(“。 将当前符号入栈。

3.扫描完后, 将栈中剩余符号依次输出。

中缀表达式9+(3-1)*3+8/2的转换过程如下：

中缀

处理

栈底->栈顶

后缀

9+(3-1)*3+8/2

数字9，直接输出

9

+(3-1)*3+8/2

运算符+，栈空，压栈

+

(3-1)*3+8/2

(，压栈

+(

3-1)*3+8/2

数字3，输出

9 3

-1)*3+8/2

运算符-，与栈顶比较：

- > (，压栈

+ ( -

1)*3+8/2

数字1，输出

9 3 1

)*3+8/2

)，弹栈并输出，直至(

+

9 3 1 -

*3+8/2

运算符*，与栈顶比较：

* > +，

+ *

3+8/2

数字3，输出

+ *

9 3 1 - 3

+8/2

运算符+，与栈顶比较：

+ < *，弹栈输出

+ = +，弹栈输出

栈空，压栈

+

+

9 3 1 – 3 *

9 3 1 – 3 * +

8/2

数字8，输出

9 3 1 – 3 * + 8

/2

运算符/，与栈顶比较：

/ > +，压栈

+

+ /

9 3 1 – 3 * + 8

2

数字2，输出

+ /

9 3 1 – 3 * + 8 2

扫描结束，弹栈输出

9 3 1 – 3 * + 8 2 / +

按第一章介绍的三层结构，栈的定义放在访问层，表示层和业务层主要体现在main()函数中。

#include <stdio.h>#include “SeqStack.h” /* 引入栈 *//* 以下是业务相关代码 */int main(){  int i;  ElementType e;  SequenceStack stack1, stack2; /* 定义了2个栈 */  /* 初始化栈 */  initSeqStack(&stack1, 100); /* 容量初始化为100 */  /* 销毁栈，释放资源 */  destroySeqStack(&Stack1);  return 0;}