1
3.1 堆栈（ Stack）
基本概念、抽象数据类型、顺序表示和实现、链
式表示和实现
3.2 堆栈应用
括号匹配问题
3.3 队列（ Queue）
基本概念、抽象数据类型、顺序队列、顺序循环
队列、链式队列、队列的应用
第三章 堆栈和队列
2
1,定义
一、堆栈的基本概念
与线性表相同，仍为一对一 ( 1:1)关系。
用 顺序栈 或 链栈 存储均可，但以顺序栈更常见
只能在 栈顶 运算，且访问结点时依照 后进先出
（ LIFO）或 先进后出 （ FILO）的原则。
关键是编写 入栈 和 出栈 函数，具体实现依顺
序栈或链栈的存储结构有别而不同。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构
限定只能在表的 一端 进行插入和删除操作的线性表。
特点：后进先出。
基本操作有, 建栈、判断栈满或栈空、入栈、出栈、
读栈顶元素值等等。
3
在栈满时还进行入栈运算，必定会产生空
间的溢出
7、栈, 下溢,
6、栈, 上溢,
当栈空时仍进行出栈运算，必定会产生
空间的溢出。
4
栈 是仅在 表尾 进行插入、删除操作的线性表。
表尾 (即 an 端 )称为 栈顶 /top ; 表头 (即 a1 端 )称为 栈底 /base
例如,栈 S= (a０,a2,a3,……….,an-1,an )
插入元素到栈顶的
操作，称为 入栈 。
从栈顶删除最后一
个元素的操作，称
为 出栈 。
an称为栈顶元素a1称为栈底元素
强调,插入和删除都只能在表
的一端（栈顶）进行！
注：堆栈可以完成比较复杂的数据元素特定序列
的转换任务，但它不能完成任何输入输出序列的
转换任务。
5
例 1：堆栈是什么？它与一般线性表有什么不同？
堆栈是一种特殊的线性表，它只能在表的 一端（即
栈顶） 进行插入和删除运算。
与一般线性表的区别：仅在于 运算规则 不同。
一般线性表 堆栈
逻辑结构,1:1 逻辑结构,1:1
存储结构：顺序 表,链 表 存储结构：顺序 栈,链 栈
运算规则,随机存取 运算规则,后进先出 (LIFO)
“进, ＝插入 =压入
“出, ＝删除 =弹
出
6
例 2,一个栈的输入序列为 1,2,3，若在 入栈的过程中允
许出栈,则可能得到的出栈序列是什么？
解,可以通过穷举所有可能性来求解：
① 1入 1出,2入 2出,3入 3出,即 123；
② 1入 1出,2,3入,3,2出,即 132；
③ 1,2入,2出,3入 3出,即 231；
④ 1,2入,2,1出,3入 3出,即 213；
⑤ 1,2,3入,3,2,1出,即 321；
合计有 5种可能性。
7
例 3,一个栈的输入序列是 12345，若在 入栈的过
程中允许出栈, 则栈的输出序列 43512可能实现
吗？ 12345的输出呢？
解：
43512不可能实现，主要是其中的 12顺序不
能实现；
12345的输出可以实现，每压入一数便立即
弹出即可。
8
二、堆栈抽象数据类型
数据集合,{ a0,a1,…,an-1 ｝ ai的数据类型为
DataType
操作集合, (1)StackInitiate(S) 初始化堆栈 S
(2)StackNotEmpty(S) 堆栈 S非空否
(3)StackPush(S,x) 入栈
(4)StackPop(S,d) 出栈
(5)StackTop(S,d) 取栈顶数据元素
等
9
三、堆栈的顺序表示和实现
1,顺序（堆）栈
顺序存储结构的堆栈。
2、顺序栈的存储结构
它是利用一组地址连续的存储
单元依次存放自栈底到栈顶的数据元
素，同时设指针 top指示栈顶元素的
当前位置。用 C语言定义为：
typedef struct
{ DataType stack[MaxStackSize];
int top;
}SeqStack; a
0
a1
……
an-1
顺序栈 S
ai
……
an
栈底 base
栈顶 top
10
a0
a1
……
an-1
顺序栈 S
ai
……
问：顺序表和顺序栈的操作有何区别？
表头
表尾
低地址
高地址
写入,S[i]= ai
读出,e= S[i]
压入 (PUSH),S[top++]=an
弹出 ( POP), e=S[--top]
低地址
高地址
S[i]
a0
a1
ai
an-1
……
顺序表 S
……
an
以线性表 S= (a0,a1,….,an-2,an-1)为例
栈底 base
栈顶 top
前提：一定要 预设 栈顶指针 top
栈顶 top
11
栈不存在的条件,base=NULL;
栈为空 的条件, base=top;
栈满的条件, top-base=MaxSize;
a0
a1
……
an-1
顺序栈 S
ai
……
低地址
高地址 an
栈底 base
栈顶 top
入栈 口诀：堆栈指针 top,先
压后加”, S[top++]=an
出栈 口诀：堆栈指针 top,先
减后弹”, e=S[--top]
12
问：为什么要设计堆栈？它有什么独特用途？
1,调用函数或子程序非它莫属；
2,递归 运算的有力工具；
3,用于保护现场和恢复现场；
4,简化了程序设计的问题。
下面用 3个例子来帮助理解堆栈：
13
void test(int *sum){
int x;
scanf(“%d”,&x);
if(x==0)sum=0;
else{test(sum);sum+=x;}
printf(sum);
}
断点地址
入栈
例 1,阅读下列递归过程，说明其功能。
输入 x1≠0 输入 x5＝ 0输入 x2 输入 x3 输入 x4
输出
sum＝ 0
输出
sum＝
0+x4
输出
sum＝
x4+x3
输出
sum＝
x4+x3
+x2
输出 sum＝
x4+x3 +x2+x1注意：最先输入的数据
x1 最后才被
累加
程序功能：对键盘输入数
据求和，直到输入 0结束
14
例 2,一个栈的输入序列是 12345，若在 入栈的过
程中允许出栈, 则栈的输出序列 43512可能实现
吗？ 12345的输出呢？
答：
43512不可能实现，主要是其中的 12顺序不能实
现；
12345的输出可以实现，每压入一数便立即弹出
即可。
思考：有无通用的判别原则？
15
例 3、
设依次进入一个栈的元素序列为 c,a,b,d，
则可得到出栈的元素序列是：
Ａ） a,b,c,d Ｂ） c,d,a,b
Ｃ） b,c,d,a Ｄ） a,c,d,b
A）,D）可以,B）,C）不行。
讨论：有无通用的判别原则？
有！若输入序列是 …,Pj… Pk… Pi … (Pj<Pk<Pi),
一定不存在这样的输出序列 …,Pi… Pj… Pk …
答：
即对于输入序列 1,2,3，不存在输出序列 3,1,2
16
3、顺序栈的操作实现
(1)初始化栈
void StackInitiate(SeqStack *S)
/*初始化顺序堆栈 S*/
{
S->top = 0; /*定义初始栈顶下标值 */
}
17
(2)判栈非空否
int StackNotEmpty(SeqStack S)
/*判顺序堆栈 S非空否，非空则返回 1，否则返回
0*/
{
if(S.top <= 0) return 0;
else return 1;
}
18
(3)入栈
int StackPush(SeqStack *S,DataType x)
/*把数据元素值 x压入顺序堆栈 S，入栈成功则返回 1，否
则返回 0 */
{ if(S->top >= MaxStackSize)
{ printf("堆栈已满无法插入 ! \n");
return 0; }
else {
S->stack[S->top] = x;
S->top ++;
return 1; }
}
19
(4)出栈
int StackPop(SeqStack *S,DataType *d)
/*弹出顺序堆栈 S的栈顶数据元素值到参数 d,出栈成
功则返回 1，否则返回 0*/
{ if(S->top <= 0)
{ printf("堆栈已空无数据元素出栈 ! \n");
return 0; }
else{
S->top --;
*d = S->stack[S->top];
return 1; }
}
20
(5)取栈顶数据元素
int StackTop(SeqStack S,DataType *d)
/*取顺序堆栈 S的当前栈顶数据元素值到参数 d,成功
则返回 1，否则返回 0*/
{ if(S.top <= 0)
{ printf("堆栈已空 ! \n");
return 0; }
else {
*d = S.stack[S.top - 1];
return 1;
}
}
21
例,用堆栈存放（ A,B,C,D）
A A
C
B
A
B
Atop
顺序栈 入栈 函数的核心语句：
S->stack[S->top] = x;
S->top ++;
top
top
top
top
低地址 L
高地址 M
B
C
D
22
例：从栈中取出 ‘ B’
D
C
B
A top
top
D
C
A
B
D
C
B
A
topD
C
B
A
top
低地址 L
高地址 M
顺序栈出栈函数的核心语句：
S->top --;
*d = S->stack[S->top];
注,DataType *d；
SeqStack *S；
23
四、堆栈的链式表示和实现
1,链栈的存储结构 以头指针为栈顶,在头指针处 插入或删除,
栈顶
栈底
栈也可以用链式结构来表示，用链式结构来表示的栈就是 链栈
h
a0
a1
an-2
an-1
nextdata 链栈中每个结点由两个域构成：
data域和 next域，其定义为：
typedef struct snode
{ DataType data;
struct snode * next;
}LSNode;
24
2、链式堆栈的操作实现
(1) 入栈
int StackPush(LSNode *head,DataType x)
{ LSNode *p;
if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL)
{ printf("内存空间不足无法插入 ! \n");
return 0; }
p->data = x;
p->next = head->next; /*新结点链入栈顶 */
head->next = p; /*新结点成为新的栈顶 */
return 1;
}
25
(2)出栈
int StackPop(LSNode *head,DataType *d)
{ LSNode *p = head->next;
if(p == NULL)
{ printf("堆栈已空出错！ ");
return 0; }
head->next = p->next; /*删除原栈顶结点 */
*d = p->data; /*原栈顶结点元素赋予 d*/
free(p); /*释放原栈顶结点内存空间 */
return 1;
} 注,由此可以看出：一个链栈由其 栈顶指针唯一指定
设 head指向栈顶元素，则 head=NULL 表示栈空
26
1) 在链栈中的头结点对操作的实现影响不大，栈顶（表
头）操作频繁,可 不设头结点 链栈。
2) 一般 不会出现栈满 情况；除非没有空间导致 malloc分
配失败。
3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，
修改指针即可完成 。
4) 采用链栈存储方式的优点是，可使 多个栈共享空间 ；
当栈中元素个数变化较大，且存在多个栈的情况下，
链栈是栈的首选存储方式。
几点说明,
27
例 1,括号匹配的检验
假设一个算法表达式中包含圆括号、方括号和
花括号三种类型的括号，编写一个判别表达式
中括号是否正确配对的函数。
设计 思路：用栈暂存左括号
3.2 栈 的应用举例
28
void ExpIsCorrect(char exp[],int n)
//判断有 n个字符的字符串 exp左右括号是否配对正确
{ SeqStack myStack; int i; char c;
StackInitiate(&myStack);
for(i=0;i<n;i++)
{if((exp[i]=='(')||(exp[i]== '[')||(exp[i]==
'{'))
StackPush(&myStack,exp[i]);
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '(')
StackPop(&myStack,&c);
29
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '(')
{ printf("左右括号配对次序不正确！ \n");
return;
} else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c !=
'['){ printf("左右括号配对次序不正确！ \n");
return; }
30
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '[')
printf("左右括号配对次序不正确！ \n");
return;
}
…,.
3.1 堆栈（ Stack）
基本概念、抽象数据类型、顺序表示和实现、链
式表示和实现
3.2 堆栈应用
括号匹配问题
3.3 队列（ Queue）
基本概念、抽象数据类型、顺序队列、顺序循环
队列、链式队列、队列的应用
第三章 堆栈和队列
2
1,定义
一、堆栈的基本概念
与线性表相同，仍为一对一 ( 1:1)关系。
用 顺序栈 或 链栈 存储均可，但以顺序栈更常见
只能在 栈顶 运算，且访问结点时依照 后进先出
（ LIFO）或 先进后出 （ FILO）的原则。
关键是编写 入栈 和 出栈 函数，具体实现依顺
序栈或链栈的存储结构有别而不同。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构
限定只能在表的 一端 进行插入和删除操作的线性表。
特点：后进先出。
基本操作有, 建栈、判断栈满或栈空、入栈、出栈、
读栈顶元素值等等。
3
在栈满时还进行入栈运算，必定会产生空
间的溢出
7、栈, 下溢,
6、栈, 上溢,
当栈空时仍进行出栈运算，必定会产生
空间的溢出。
4
栈 是仅在 表尾 进行插入、删除操作的线性表。
表尾 (即 an 端 )称为 栈顶 /top ; 表头 (即 a1 端 )称为 栈底 /base
例如,栈 S= (a０,a2,a3,……….,an-1,an )
插入元素到栈顶的
操作，称为 入栈 。
从栈顶删除最后一
个元素的操作，称
为 出栈 。
an称为栈顶元素a1称为栈底元素
强调,插入和删除都只能在表
的一端（栈顶）进行！
注：堆栈可以完成比较复杂的数据元素特定序列
的转换任务，但它不能完成任何输入输出序列的
转换任务。
5
例 1：堆栈是什么？它与一般线性表有什么不同？
堆栈是一种特殊的线性表，它只能在表的 一端（即
栈顶） 进行插入和删除运算。
与一般线性表的区别：仅在于 运算规则 不同。
一般线性表 堆栈
逻辑结构,1:1 逻辑结构,1:1
存储结构：顺序 表,链 表 存储结构：顺序 栈,链 栈
运算规则,随机存取 运算规则,后进先出 (LIFO)
“进, ＝插入 =压入
“出, ＝删除 =弹
出
6
例 2,一个栈的输入序列为 1,2,3，若在 入栈的过程中允
许出栈,则可能得到的出栈序列是什么？
解,可以通过穷举所有可能性来求解：
① 1入 1出,2入 2出,3入 3出,即 123；
② 1入 1出,2,3入,3,2出,即 132；
③ 1,2入,2出,3入 3出,即 231；
④ 1,2入,2,1出,3入 3出,即 213；
⑤ 1,2,3入,3,2,1出,即 321；
合计有 5种可能性。
7
例 3,一个栈的输入序列是 12345，若在 入栈的过
程中允许出栈, 则栈的输出序列 43512可能实现
吗？ 12345的输出呢？
解：
43512不可能实现，主要是其中的 12顺序不
能实现；
12345的输出可以实现，每压入一数便立即
弹出即可。
8
二、堆栈抽象数据类型
数据集合,{ a0,a1,…,an-1 ｝ ai的数据类型为
DataType
操作集合, (1)StackInitiate(S) 初始化堆栈 S
(2)StackNotEmpty(S) 堆栈 S非空否
(3)StackPush(S,x) 入栈
(4)StackPop(S,d) 出栈
(5)StackTop(S,d) 取栈顶数据元素
等
9
三、堆栈的顺序表示和实现
1,顺序（堆）栈
顺序存储结构的堆栈。
2、顺序栈的存储结构
它是利用一组地址连续的存储
单元依次存放自栈底到栈顶的数据元
素，同时设指针 top指示栈顶元素的
当前位置。用 C语言定义为：
typedef struct
{ DataType stack[MaxStackSize];
int top;
}SeqStack; a
0
a1
……
an-1
顺序栈 S
ai
……
an
栈底 base
栈顶 top
10
a0
a1
……
an-1
顺序栈 S
ai
……
问：顺序表和顺序栈的操作有何区别？
表头
表尾
低地址
高地址
写入,S[i]= ai
读出,e= S[i]
压入 (PUSH),S[top++]=an
弹出 ( POP), e=S[--top]
低地址
高地址
S[i]
a0
a1
ai
an-1
……
顺序表 S
……
an
以线性表 S= (a0,a1,….,an-2,an-1)为例
栈底 base
栈顶 top
前提：一定要 预设 栈顶指针 top
栈顶 top
11
栈不存在的条件,base=NULL;
栈为空 的条件, base=top;
栈满的条件, top-base=MaxSize;
a0
a1
……
an-1
顺序栈 S
ai
……
低地址
高地址 an
栈底 base
栈顶 top
入栈 口诀：堆栈指针 top,先
压后加”, S[top++]=an
出栈 口诀：堆栈指针 top,先
减后弹”, e=S[--top]
12
问：为什么要设计堆栈？它有什么独特用途？
1,调用函数或子程序非它莫属；
2,递归 运算的有力工具；
3,用于保护现场和恢复现场；
4,简化了程序设计的问题。
下面用 3个例子来帮助理解堆栈：
13
void test(int *sum){
int x;
scanf(“%d”,&x);
if(x==0)sum=0;
else{test(sum);sum+=x;}
printf(sum);
}
断点地址
入栈
例 1,阅读下列递归过程，说明其功能。
输入 x1≠0 输入 x5＝ 0输入 x2 输入 x3 输入 x4
输出
sum＝ 0
输出
sum＝
0+x4
输出
sum＝
x4+x3
输出
sum＝
x4+x3
+x2
输出 sum＝
x4+x3 +x2+x1注意：最先输入的数据
x1 最后才被
累加
程序功能：对键盘输入数
据求和，直到输入 0结束
14
例 2,一个栈的输入序列是 12345，若在 入栈的过
程中允许出栈, 则栈的输出序列 43512可能实现
吗？ 12345的输出呢？
答：
43512不可能实现，主要是其中的 12顺序不能实
现；
12345的输出可以实现，每压入一数便立即弹出
即可。
思考：有无通用的判别原则？
15
例 3、
设依次进入一个栈的元素序列为 c,a,b,d，
则可得到出栈的元素序列是：
Ａ） a,b,c,d Ｂ） c,d,a,b
Ｃ） b,c,d,a Ｄ） a,c,d,b
A）,D）可以,B）,C）不行。
讨论：有无通用的判别原则？
有！若输入序列是 …,Pj… Pk… Pi … (Pj<Pk<Pi),
一定不存在这样的输出序列 …,Pi… Pj… Pk …
答：
即对于输入序列 1,2,3，不存在输出序列 3,1,2
16
3、顺序栈的操作实现
(1)初始化栈
void StackInitiate(SeqStack *S)
/*初始化顺序堆栈 S*/
{
S->top = 0; /*定义初始栈顶下标值 */
}
17
(2)判栈非空否
int StackNotEmpty(SeqStack S)
/*判顺序堆栈 S非空否，非空则返回 1，否则返回
0*/
{
if(S.top <= 0) return 0;
else return 1;
}
18
(3)入栈
int StackPush(SeqStack *S,DataType x)
/*把数据元素值 x压入顺序堆栈 S，入栈成功则返回 1，否
则返回 0 */
{ if(S->top >= MaxStackSize)
{ printf("堆栈已满无法插入 ! \n");
return 0; }
else {
S->stack[S->top] = x;
S->top ++;
return 1; }
}
19
(4)出栈
int StackPop(SeqStack *S,DataType *d)
/*弹出顺序堆栈 S的栈顶数据元素值到参数 d,出栈成
功则返回 1，否则返回 0*/
{ if(S->top <= 0)
{ printf("堆栈已空无数据元素出栈 ! \n");
return 0; }
else{
S->top --;
*d = S->stack[S->top];
return 1; }
}
20
(5)取栈顶数据元素
int StackTop(SeqStack S,DataType *d)
/*取顺序堆栈 S的当前栈顶数据元素值到参数 d,成功
则返回 1，否则返回 0*/
{ if(S.top <= 0)
{ printf("堆栈已空 ! \n");
return 0; }
else {
*d = S.stack[S.top - 1];
return 1;
}
}
21
例,用堆栈存放（ A,B,C,D）
A A
C
B
A
B
Atop
顺序栈 入栈 函数的核心语句：
S->stack[S->top] = x;
S->top ++;
top
top
top
top
低地址 L
高地址 M
B
C
D
22
例：从栈中取出 ‘ B’
D
C
B
A top
top
D
C
A
B
D
C
B
A
topD
C
B
A
top
低地址 L
高地址 M
顺序栈出栈函数的核心语句：
S->top --;
*d = S->stack[S->top];
注,DataType *d；
SeqStack *S；
23
四、堆栈的链式表示和实现
1,链栈的存储结构 以头指针为栈顶,在头指针处 插入或删除,
栈顶
栈底
栈也可以用链式结构来表示，用链式结构来表示的栈就是 链栈
h
a0
a1
an-2
an-1
nextdata 链栈中每个结点由两个域构成：
data域和 next域，其定义为：
typedef struct snode
{ DataType data;
struct snode * next;
}LSNode;
24
2、链式堆栈的操作实现
(1) 入栈
int StackPush(LSNode *head,DataType x)
{ LSNode *p;
if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL)
{ printf("内存空间不足无法插入 ! \n");
return 0; }
p->data = x;
p->next = head->next; /*新结点链入栈顶 */
head->next = p; /*新结点成为新的栈顶 */
return 1;
}
25
(2)出栈
int StackPop(LSNode *head,DataType *d)
{ LSNode *p = head->next;
if(p == NULL)
{ printf("堆栈已空出错！ ");
return 0; }
head->next = p->next; /*删除原栈顶结点 */
*d = p->data; /*原栈顶结点元素赋予 d*/
free(p); /*释放原栈顶结点内存空间 */
return 1;
} 注,由此可以看出：一个链栈由其 栈顶指针唯一指定
设 head指向栈顶元素，则 head=NULL 表示栈空
26
1) 在链栈中的头结点对操作的实现影响不大，栈顶（表
头）操作频繁,可 不设头结点 链栈。
2) 一般 不会出现栈满 情况；除非没有空间导致 malloc分
配失败。
3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，
修改指针即可完成 。
4) 采用链栈存储方式的优点是，可使 多个栈共享空间 ；
当栈中元素个数变化较大，且存在多个栈的情况下，
链栈是栈的首选存储方式。
几点说明,
27
例 1,括号匹配的检验
假设一个算法表达式中包含圆括号、方括号和
花括号三种类型的括号，编写一个判别表达式
中括号是否正确配对的函数。
设计 思路：用栈暂存左括号
3.2 栈 的应用举例
28
void ExpIsCorrect(char exp[],int n)
//判断有 n个字符的字符串 exp左右括号是否配对正确
{ SeqStack myStack; int i; char c;
StackInitiate(&myStack);
for(i=0;i<n;i++)
{if((exp[i]=='(')||(exp[i]== '[')||(exp[i]==
'{'))
StackPush(&myStack,exp[i]);
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '(')
StackPop(&myStack,&c);
29
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '(')
{ printf("左右括号配对次序不正确！ \n");
return;
} else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c !=
'['){ printf("左右括号配对次序不正确！ \n");
return; }
30
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '[')
printf("左右括号配对次序不正确！ \n");
return;
}
…,.
