文档介绍：第3章栈和队列
张成文
北京邮电大学计算机学院
概述
两种特殊的线性表。
逻辑结构和线性表相同。
比起线性表其运算受限制,故又称它们为运算受限的线性表。
1. 栈
栈的定义
顺序栈
链栈
栈的定义
栈是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。 (2)当表中没有元素时称为空栈。 (3)栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。
每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶,而每次出栈的总是当前栈中“最新”的元素,即最后进栈的元素。因此,栈又称为后进先出的线性表。简称为LIFO表。
栈的示意图
a1
a2
an
栈顶(表尾)
栈底
bottom
top
入栈push
出栈pop
栈的示意图
S3
bottom
top
S1
S2
S5
S6
S3
S4
S3
S3
S3
S3
S3
PUSH
PUSH
PUSH
POP
PUSH
PUSH
PUSH
栈在计算机中主要有两种基本的存储结构:顺序存储结构和链式存储结构。
顺序存储的栈为顺序栈
链式存储的栈为链栈
栈的存储方式
顺序栈
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
顺序栈的类型定义
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
 typedef struct
{ StackElementType elem[Stack_Size];
/* 一维数组*/
int top;
/*用来存放栈顶元素的下标*/
}SeqStack;
top
空栈
top
top
top
top
top
a 进栈
b 进栈
a
a
b
a
b
c
d
e
e 进栈
a
b
c
d
e
f 进栈溢出
a
b
d
e
e 退栈
c