文档介绍：数据结构与算法
第四讲:栈和队列
内容提要
栈
队列
19/04/2018
2
从***说起。。。*** vs 弹夹式
为什么早期的军官都喜欢用******?
子弹质量 vs 子弹夹容量
弹夹式***结构——栈
19/04/2018
3
栈的定义
栈(stack)是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
应用举例:
后退键
Word、Photoshop软件中的撤销(undo)操作
19/04/2018
4
栈的几个概念
栈顶(top)——允许插入删除,栈的表尾。
栈底(bottom)——固定不动,栈的表头。
空栈——没有元素的栈。
插入操作——进栈(或压栈,入栈)。
删除操作——出栈(或弹栈)。
19/04/2018
5
栈顶
栈底
进栈
栈顶
栈底
栈顶
栈底
出栈
栈顶
栈底
进栈出栈的变化形式
19/04/2018
6
1
1
2
1
2
3
1
1
2
1
1
2
1
3
1
2
3
1
2
2
2
3
1
1
2
1
1
3
1
假设三个整型元素1、2、3依次进栈,有哪些出栈次序呢?
(1)1、2、3进,3、2、1出,出栈次序为321.
(2)1进、1出、2进、2出、3进、3出,出栈次序为123.
(3)1进、 2进、 2出、1出、3进、3出,出栈次序为213.
(4)1进、 1出、 2进、 3进、3出、2出,出栈次序为132.
(5)1进、 2进、 2出、 3进、3出、 1出,出栈次序为231.
【注意】:
只有5种可能。出栈次序不可能是312.
栈的抽象数据类型
ADT 栈(Stack)
Data
同线性表。元素具有相同的类型,相邻元素具有前驱和后继的关系。
Operation
InitStack(&S):初始化操作,建立一个空栈S。
DestroyStack(&S):若栈存在,则销毁它。
ClearStack(&S):将栈清空。
StackEmpty(S):若栈为空,返回true,否则返回false。
GetTop(S, &e):若栈存在且非空,用e返回S的栈顶元素。
Push(&S, e):若栈S存在,插入新元素e到栈S中并成为栈顶元素。
Pop(&S, &e):删除栈S中的栈顶元素,并用e返回其值。
StackLength(S):返回栈S的元素个数。
endADT
19/04/2018
7
【注意】:
由于栈本身就是线性表,于是栈也有
顺序存储和链式存储两种实现方式。
栈的顺序存储结构
19/04/2018
8
// 栈的顺序存储的结构代码
#define STACK_INIT_SIZE 5
#define STACKINCREMENT 10
typedef struct
{
SElemType * base;
SElemType * top;
int stacksize;
}SqStack;
a1
a2
a3
a4
a5
栈满,
(top-base)==5
4
3
2
1
0
栈有两个元素,(top-base)=2
4
3
2
1
0
a1
a2
base
top
top
【用数组实现栈】:
采用数组动态存储分配;
下标为0的一端作为栈底;
定义top指针变量指示栈顶元素,top可以随意游动,但与栈底距离必须小于stacksize。
即stacksize-1
base
顺序结构栈的基本操作(1)
Status InitStack(SqStack &S)
{ // 构造一个空栈
= (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!) exit(OVERFLOW); // 存储分配失败
= ;
= STACK_INIT_SIZE;
return OK;
}
19/04/2018
9
Status GetTop(SqStack S, SElemType &e)
{
if( == ) return ERROR;
e = *(-1);
return OK;
}
4
3
2
1
0
a1
a2
base
top
栈空,top==base
top
4
3
2
1
0
base
顺序结构栈的基本操作(2)
Status Push(SqStack &S, SE