2009-7-30 软件基础（第 3章 堆栈和队列）
第三章 堆栈和队列
3.1堆栈 概念及算法
3.2堆栈的应用
3.3队列 概念及算法
3.4队列的应用
Chapter 3 Stack and Queue
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1 堆栈的概念及其算法 ( Stack )
3.1.1堆栈的基本概念
3.1.2栈的 顺序 存储结构
3.1.3栈的链接存储结构
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1.1 堆栈的基本概念
堆栈,只允许在一端插入和删除的线性表。
栈顶 (top),允许插入和删除的一端称为 栈顶,
栈底 (bottom),另一端出栈或退栈入栈或进栈
a0
a1
…
an-2
an-1
bottom
top
特点,Last In First Out
后进先出 (LIFO)
1.栈的定义
2009-7-30 软件基础（第 3章 堆栈和队列）
相关术语
(1),栈满,栈内元素个数为 Maxsize时。
top=Maxsize
(2),栈空,栈内无元素。 top=0
(3),上溢,当栈满时，还要进栈。
(4),下溢,当栈空时，还要出栈。
2009-7-30 软件基础（第 3章 堆栈和队列）
2,栈的基本操作
1、初始化
2、进栈
3、退栈
4、取栈顶元素
5、判栈是否非空
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1.2,栈的顺序存储结构
typedef int elemtype;
#define maxsize 10
elemtype stack[maxsize];
int top;
顺序栈用一维数组表示。用 top指向栈顶，表示栈内元素 个数,即数组 下标 。
数组简单形式：
1,顺序栈的 C语言描述：
2009-7-30 软件基础（第 3章 堆栈和队列）
a0 a1 a2 a3 a4 ……
Maxsize-1
stack
0 1 2 3 4 5
top
=
栈底 栈顶顺序堆栈的存储示意图
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef int elemtype;
#define maxsize 64
typedef struct
{
elemtype stack[maxsize];
int top;
}seqstack;
结构体形式：
Seqstack
包括：
stack数组和 top两项
Seqstack
是一个结构体类型
2009-7-30 软件基础（第 3章 堆栈和队列）
seqstack *s;
c语言的算法描述使用的数据类型示意图
top
stack[maxsize]
ss->tops->stack[0]
s->stack[1]
s->stack[2]
s->stack[maxsize-1]
2009-7-30 软件基础（第 3章 堆栈和队列）
top
top
a0
a1
a2
a3
top
top
top
maxsize个进栈过程示例
2009-7-30 软件基础（第 3章 堆栈和队列）
2,顺序栈的基本运算
(1).栈的初始化
seqstack *inistack(seqstack *s)
{
s->top=0;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
int NotEmpty(seqstack *s)
{if (s->top==0)
return 0;
else return 1;
}
(2).判栈非空判断顺序堆栈 S非空否，非空返回 1，否则返回 0；
2009-7-30 软件基础（第 3章 堆栈和队列）
int StackPush (seqstack *s,elemtype x)
{
if (s->top==maxsize)
{ printf(,overflow\n” );return 0;}
else
{s->stack[s->top]＝ x;
s->top++;
}
return 1;
}
判栈满？
栈顶指针加 1
入栈
(3).入栈算法
2009-7-30 软件基础（第 3章 堆栈和队列）
int PopStack(seqstack *s,elemtype *d)
{
if (s->top==0)
{ printf(,underflow\n” ); return 0;
}
else
{ s->top--;
*d=s->stack[s->top];
return 1;
}
}
判栈空？
栈顶减 1
返回栈顶元素
(4).退栈算法
2009-7-30 软件基础（第 3章 堆栈和队列）
int StackTop (seqstack s,elemtype *d)
{if (s.top==0)
{printf(,underflow\n” );
return NULL;
}
else
{*d=s.stack[s.top-1];
return 1;
}
}
(5).取栈顶元素
2009-7-30 软件基础（第 3章 堆栈和队列）
1.栈的链接表示 — 链式栈
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
3.1.3 栈的链接存储结构
∧top
栈顶 栈底
2009-7-30 软件基础（第 3章 堆栈和队列）
2.链栈的结点定义
typedef int elemtype;
typedef struct node
{ elemtype data;
struct node *next;
} linkstack;
linkstack *top;
2009-7-30 软件基础（第 3章 堆栈和队列）
top ∧
p x
链栈入栈过程示意
2009-7-30 软件基础（第 3章 堆栈和队列）
2,链栈的基本运算
(1).栈的初始化
seqstack inistack(seqstack **h)
{
seqstack *h;
if ((*h=(seqstack *)malloc(sizeof(seqstack)))==NULL)
return 0;
(*h)->next=NULL;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
int NotEmpty(seqstack *h)
{if (h->next=NULL)
return 0;
else return 1;
}
(2).判栈非空判断顺序堆栈 S非空否，非空返回 1，否则返回 0；
int *StackPush (linkstack *top,elemtype x)
{ linkstack *p;
if ((p＝ malloc(sizeof(linkstack)))==NULL;
{printf(,\n失败,)； return 0； }
p->data＝ x;
p->next＝ top->next;
top->next=p;
return 1;
}
(3) 链栈的入栈算法产生一个新结点进栈
top ∧
p x
linkstack *StackPop (linkstack *top)
{ linkstack *p;
elemtype datap;
p=top->next;
if (p==NULL)
{printf(,under flow\n” ); return NULL;}
datap＝ p->data;
top->next＝ p->next;
free(p);
return datap;
}
}
(4)链栈的出栈算法判栈空出栈
top ∧
p datap
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype StackTop (seqstack *h,Datatype *d)
{seqstack *h=h->next;
if (p==NULL)
{printf(,堆栈已空出错 \n” );
return 0;
}
*d=p->data;
return 1;
}
(5).取栈顶元素
2009-7-30 软件基础（第 3章 堆栈和队列）
不可能产生输出序列 CAB
3.2 栈的应用例：对于一个栈，如果输入项序列由 ABC组成，试给出所有可能的输出序列。 (s:进栈； x：出栈 )
出栈序列 操作序列
ABC sx sx sx
ACB sx ss xx
BAC ss xx sx
BCA ss xs xx
CBA ss sx xx
1.调度问题
C,B,A
2009-7-30 软件基础（第 3章 堆栈和队列）
2.栈的应用－－嵌套和递归函数主程序
t1子程序
t1子程序
t2子程序
t2子程序
t3子程序
t3子程序栈栈
t1 t2t1
t3t2
t1
t3t2
t1t2t1t1
2009-7-30 软件基础（第 3章 堆栈和队列）
int fact(int n)
{int y;
if (n==0) return(1);
y=fact(n-1);
return(n*y);
}
1 当 n=0
例,n!=
n× (n-1) × … × 1 当 n>0
main()
{int fn;
fn=fact(3);
Printf(“\nfn=%1d”,fn);
}
2009-7-30 软件基础（第 3章 堆栈和队列）
main
.
.
.
fn=fact(3)
fact(3)
.
.
.
y=fact(2)
fact(2)
.
.
.
y=fact(1)
fact(1)
.
.
.
y=fact(0)
fact(0)
.
.
.
returu(1)
1126
过 程：
returu(3*y) returu(2*y) returu(1*y)
2009-7-30 软件基础（第 3章 堆栈和队列）
3,栈的应用－－表达式计算中缀表达式,A + ( B – C / D) × E
后缀表达式,ABCD/－ E× +
应用于编译软件中，计算机求表达式的值。
后缀表达式特点,
1、与相应的中缀表达式中的操作数次序相同
2、没有括号
2009-7-30 软件基础（第 3章 堆栈和队列）
后缀表达式的处理过程操作顺序 后缀表达式
ABCD/－ E× +
T1 ← C/D ABT1－ E× +
T2 ← B – T1 AT2E× +
T3 ← T2 × E AT3+
T4 ← A + T3 T4
2009-7-30 软件基础（第 3章 堆栈和队列）
A
B
C
D
Top=4
0
1
2
3
a
A
B
T1
Top=3
1
0
2
b
A
T2
Top=2
0
1
c
A
T2
E
Top=3
0
1
2
d
A
T3
Top=2
0
1
e
T4
Top=1
0
f
(a)读入 ABCD
(b)读入,/”做 T1 C/D
(c)读入,-”做 T2 B-T1
(d)读入 E
(e)读入,*”做 T3 T2*E
(f)读入,+”做 T4 A+T3
后缀表达式求值时顺序堆栈的变化情况
ABCD/ － E × ＋
2009-7-30 软件基础（第 3章 堆栈和队列）
中缀表达式转换为后缀表达式的处理规则
1、如为操作数，直接输出到队列；
2、如栈顶运算符低于当前运算符，入栈；
3、如栈顶运算符高于当前运算符，栈顶运算符退栈，
并输出到队列，当前运算符再与栈顶运算符比较；
4、如栈顶运算符等于当前运算符，且栈顶运算符为
,（,,当前运算符为,）,,则栈顶运算符退栈，
继续读下一符号；
5、如栈顶运算符等于当前运算符，且栈顶运算符为
,#”,当前运算符也为,#”,则栈顶运算符退栈，
继续读下一符号；
2009-7-30 软件基础（第 3章 堆栈和队列）
＋ － × ／ ( ) #
＋ > > < < < > >
－ > > < < < > >
× > > > > < > >
／ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
当前运算符 (x2)
栈顶运算符
(x1)
运算符优先级关系
2009-7-30 软件基础（第 3章 堆栈和队列）
步骤 中缀表达式 STACK 输出
1 A＋ (B－ C／ D)× E# #
2 ＋ (B－ C／ D)× E# # A
3 (B－ C／ D)× E# # ＋ A
4 B－ C／ D)× E# # ＋ ( A
5 － C／ D)× E# # ＋ ( AB
6 C／ D)× E# # ＋ (－ AB
7 ／ D)× E# # ＋ (－ ABC
8 D)× E# # ＋ (－ / ABC
9 )× E# # ＋ (－ / ABCD
2009-7-30 软件基础（第 3章 堆栈和队列）
步骤 中缀表达式 STACK 输出
10 )× E# # ＋ (－ ABCD/
11 )× E# # ＋ ( ABCD/ －
12 × E# # ＋ ABCD/ －
13 E# # ＋ × ABCD/ －
14 # # ＋ × ABCD/ － E
15 # # + ABCD/ － E ×
16 # # ABCD/ － E × ＋
2009-7-30 软件基础（第 3章 堆栈和队列）
概念：堆栈，栈顶，栈底，栈满，栈空，上溢，下溢,顺序栈，链栈。
算法：初始化，入栈，出栈，取栈顶元素。
（顺序栈，链栈）
应用,1.递归和嵌套
2.表达式求值。
总 结
第三章 堆栈和队列
3.1堆栈 概念及算法
3.2堆栈的应用
3.3队列 概念及算法
3.4队列的应用
Chapter 3 Stack and Queue
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1 堆栈的概念及其算法 ( Stack )
3.1.1堆栈的基本概念
3.1.2栈的 顺序 存储结构
3.1.3栈的链接存储结构
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1.1 堆栈的基本概念
堆栈,只允许在一端插入和删除的线性表。
栈顶 (top),允许插入和删除的一端称为 栈顶,
栈底 (bottom),另一端出栈或退栈入栈或进栈
a0
a1
…
an-2
an-1
bottom
top
特点,Last In First Out
后进先出 (LIFO)
1.栈的定义
2009-7-30 软件基础（第 3章 堆栈和队列）
相关术语
(1),栈满,栈内元素个数为 Maxsize时。
top=Maxsize
(2),栈空,栈内无元素。 top=0
(3),上溢,当栈满时，还要进栈。
(4),下溢,当栈空时，还要出栈。
2009-7-30 软件基础（第 3章 堆栈和队列）
2,栈的基本操作
1、初始化
2、进栈
3、退栈
4、取栈顶元素
5、判栈是否非空
2009-7-30 软件基础（第 3章 堆栈和队列）
3.1.2,栈的顺序存储结构
typedef int elemtype;
#define maxsize 10
elemtype stack[maxsize];
int top;
顺序栈用一维数组表示。用 top指向栈顶，表示栈内元素 个数,即数组 下标 。
数组简单形式：
1,顺序栈的 C语言描述：
2009-7-30 软件基础（第 3章 堆栈和队列）
a0 a1 a2 a3 a4 ……
Maxsize-1
stack
0 1 2 3 4 5
top
=
栈底 栈顶顺序堆栈的存储示意图
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef int elemtype;
#define maxsize 64
typedef struct
{
elemtype stack[maxsize];
int top;
}seqstack;
结构体形式：
Seqstack
包括：
stack数组和 top两项
Seqstack
是一个结构体类型
2009-7-30 软件基础（第 3章 堆栈和队列）
seqstack *s;
c语言的算法描述使用的数据类型示意图
top
stack[maxsize]
ss->tops->stack[0]
s->stack[1]
s->stack[2]
s->stack[maxsize-1]
2009-7-30 软件基础（第 3章 堆栈和队列）
top
top
a0
a1
a2
a3
top
top
top
maxsize个进栈过程示例
2009-7-30 软件基础（第 3章 堆栈和队列）
2,顺序栈的基本运算
(1).栈的初始化
seqstack *inistack(seqstack *s)
{
s->top=0;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
int NotEmpty(seqstack *s)
{if (s->top==0)
return 0;
else return 1;
}
(2).判栈非空判断顺序堆栈 S非空否，非空返回 1，否则返回 0；
2009-7-30 软件基础（第 3章 堆栈和队列）
int StackPush (seqstack *s,elemtype x)
{
if (s->top==maxsize)
{ printf(,overflow\n” );return 0;}
else
{s->stack[s->top]＝ x;
s->top++;
}
return 1;
}
判栈满？
栈顶指针加 1
入栈
(3).入栈算法
2009-7-30 软件基础（第 3章 堆栈和队列）
int PopStack(seqstack *s,elemtype *d)
{
if (s->top==0)
{ printf(,underflow\n” ); return 0;
}
else
{ s->top--;
*d=s->stack[s->top];
return 1;
}
}
判栈空？
栈顶减 1
返回栈顶元素
(4).退栈算法
2009-7-30 软件基础（第 3章 堆栈和队列）
int StackTop (seqstack s,elemtype *d)
{if (s.top==0)
{printf(,underflow\n” );
return NULL;
}
else
{*d=s.stack[s.top-1];
return 1;
}
}
(5).取栈顶元素
2009-7-30 软件基础（第 3章 堆栈和队列）
1.栈的链接表示 — 链式栈
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
3.1.3 栈的链接存储结构
∧top
栈顶 栈底
2009-7-30 软件基础（第 3章 堆栈和队列）
2.链栈的结点定义
typedef int elemtype;
typedef struct node
{ elemtype data;
struct node *next;
} linkstack;
linkstack *top;
2009-7-30 软件基础（第 3章 堆栈和队列）
top ∧
p x
链栈入栈过程示意
2009-7-30 软件基础（第 3章 堆栈和队列）
2,链栈的基本运算
(1).栈的初始化
seqstack inistack(seqstack **h)
{
seqstack *h;
if ((*h=(seqstack *)malloc(sizeof(seqstack)))==NULL)
return 0;
(*h)->next=NULL;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
int NotEmpty(seqstack *h)
{if (h->next=NULL)
return 0;
else return 1;
}
(2).判栈非空判断顺序堆栈 S非空否，非空返回 1，否则返回 0；
int *StackPush (linkstack *top,elemtype x)
{ linkstack *p;
if ((p＝ malloc(sizeof(linkstack)))==NULL;
{printf(,\n失败,)； return 0； }
p->data＝ x;
p->next＝ top->next;
top->next=p;
return 1;
}
(3) 链栈的入栈算法产生一个新结点进栈
top ∧
p x
linkstack *StackPop (linkstack *top)
{ linkstack *p;
elemtype datap;
p=top->next;
if (p==NULL)
{printf(,under flow\n” ); return NULL;}
datap＝ p->data;
top->next＝ p->next;
free(p);
return datap;
}
}
(4)链栈的出栈算法判栈空出栈
top ∧
p datap
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype StackTop (seqstack *h,Datatype *d)
{seqstack *h=h->next;
if (p==NULL)
{printf(,堆栈已空出错 \n” );
return 0;
}
*d=p->data;
return 1;
}
(5).取栈顶元素
2009-7-30 软件基础（第 3章 堆栈和队列）
不可能产生输出序列 CAB
3.2 栈的应用例：对于一个栈，如果输入项序列由 ABC组成，试给出所有可能的输出序列。 (s:进栈； x：出栈 )
出栈序列 操作序列
ABC sx sx sx
ACB sx ss xx
BAC ss xx sx
BCA ss xs xx
CBA ss sx xx
1.调度问题
C,B,A
2009-7-30 软件基础（第 3章 堆栈和队列）
2.栈的应用－－嵌套和递归函数主程序
t1子程序
t1子程序
t2子程序
t2子程序
t3子程序
t3子程序栈栈
t1 t2t1
t3t2
t1
t3t2
t1t2t1t1
2009-7-30 软件基础（第 3章 堆栈和队列）
int fact(int n)
{int y;
if (n==0) return(1);
y=fact(n-1);
return(n*y);
}
1 当 n=0
例,n!=
n× (n-1) × … × 1 当 n>0
main()
{int fn;
fn=fact(3);
Printf(“\nfn=%1d”,fn);
}
2009-7-30 软件基础（第 3章 堆栈和队列）
main
.
.
.
fn=fact(3)
fact(3)
.
.
.
y=fact(2)
fact(2)
.
.
.
y=fact(1)
fact(1)
.
.
.
y=fact(0)
fact(0)
.
.
.
returu(1)
1126
过 程：
returu(3*y) returu(2*y) returu(1*y)
2009-7-30 软件基础（第 3章 堆栈和队列）
3,栈的应用－－表达式计算中缀表达式,A + ( B – C / D) × E
后缀表达式,ABCD/－ E× +
应用于编译软件中，计算机求表达式的值。
后缀表达式特点,
1、与相应的中缀表达式中的操作数次序相同
2、没有括号
2009-7-30 软件基础（第 3章 堆栈和队列）
后缀表达式的处理过程操作顺序 后缀表达式
ABCD/－ E× +
T1 ← C/D ABT1－ E× +
T2 ← B – T1 AT2E× +
T3 ← T2 × E AT3+
T4 ← A + T3 T4
2009-7-30 软件基础（第 3章 堆栈和队列）
A
B
C
D
Top=4
0
1
2
3
a
A
B
T1
Top=3
1
0
2
b
A
T2
Top=2
0
1
c
A
T2
E
Top=3
0
1
2
d
A
T3
Top=2
0
1
e
T4
Top=1
0
f
(a)读入 ABCD
(b)读入,/”做 T1 C/D
(c)读入,-”做 T2 B-T1
(d)读入 E
(e)读入,*”做 T3 T2*E
(f)读入,+”做 T4 A+T3
后缀表达式求值时顺序堆栈的变化情况
ABCD/ － E × ＋
2009-7-30 软件基础（第 3章 堆栈和队列）
中缀表达式转换为后缀表达式的处理规则
1、如为操作数，直接输出到队列；
2、如栈顶运算符低于当前运算符，入栈；
3、如栈顶运算符高于当前运算符，栈顶运算符退栈，
并输出到队列，当前运算符再与栈顶运算符比较；
4、如栈顶运算符等于当前运算符，且栈顶运算符为
,（,,当前运算符为,）,,则栈顶运算符退栈，
继续读下一符号；
5、如栈顶运算符等于当前运算符，且栈顶运算符为
,#”,当前运算符也为,#”,则栈顶运算符退栈，
继续读下一符号；
2009-7-30 软件基础（第 3章 堆栈和队列）
＋ － × ／ ( ) #
＋ > > < < < > >
－ > > < < < > >
× > > > > < > >
／ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
当前运算符 (x2)
栈顶运算符
(x1)
运算符优先级关系
2009-7-30 软件基础（第 3章 堆栈和队列）
步骤 中缀表达式 STACK 输出
1 A＋ (B－ C／ D)× E# #
2 ＋ (B－ C／ D)× E# # A
3 (B－ C／ D)× E# # ＋ A
4 B－ C／ D)× E# # ＋ ( A
5 － C／ D)× E# # ＋ ( AB
6 C／ D)× E# # ＋ (－ AB
7 ／ D)× E# # ＋ (－ ABC
8 D)× E# # ＋ (－ / ABC
9 )× E# # ＋ (－ / ABCD
2009-7-30 软件基础（第 3章 堆栈和队列）
步骤 中缀表达式 STACK 输出
10 )× E# # ＋ (－ ABCD/
11 )× E# # ＋ ( ABCD/ －
12 × E# # ＋ ABCD/ －
13 E# # ＋ × ABCD/ －
14 # # ＋ × ABCD/ － E
15 # # + ABCD/ － E ×
16 # # ABCD/ － E × ＋
2009-7-30 软件基础（第 3章 堆栈和队列）
概念：堆栈，栈顶，栈底，栈满，栈空，上溢，下溢,顺序栈，链栈。
算法：初始化，入栈，出栈，取栈顶元素。
（顺序栈，链栈）
应用,1.递归和嵌套
2.表达式求值。
总 结
