文档介绍：第3章栈和队列
栈
队列
应用
本章学****目标
理解栈的定义及其基本运算
掌握顺序栈和链栈的各种操作实现
理解队列的定义及其基本运算
掌握循环队列和链队列的各种操作实现
学会利用栈和队列解决一些问题
栈和队列是两种重要的线性结构
栈和队列是操作受限的线性表
出
进
排队买票
汉诺塔
进
出
栈
栈的基本概念
栈:限制仅在表尾进行插入和删除操作的线性表
栈的操作特性:按先进后出(F I L O )或后进先出(LIFO)的原则
栈顶(top):允许插入和删除的一端。
约定top始终指向栈顶位置。
栈底(bottom): 不允许插入和删除的一端。
入栈顺序:
e0 e1 e2 … en-2 en-1
出栈顺序:
en-1 en-2 … e2 e1 e0
栈可以对序列实现求逆
en-1
e0
e1
en-2
…
进栈(Push) 出栈(Pop)
栈顶 top
栈底bottom
栈的基本运算:
InitStack(s) 初始化操作,初始化为空栈s 。
IsEmpty(s) 判断栈空函数。如果s是空栈,返回“true”,否则返回“false”。
IsFull(s) 判断栈满函数。主要应用在顺序存储结构中,如果s栈满,返回“true”,否则返回“false”。
Push(s,x) 压栈操作。将元素x插入到栈s中,并使x成为新的栈顶元素。
Pop(s) 出栈函数。如果栈s非空,那么返回栈顶元素,并删除该栈顶元素,否则返回空值NULL。
GetTop(s) 获取栈顶元素。如果栈s非空,那么返回值为栈顶元素,否则返回空值NULL。
EmptyStack(s) 清空栈操作。将栈s中的所有元素清除掉,使之成为一个空栈。
DestroyStack ()销毁栈。释放栈占用的存储空间。
栈有两种存储结构:顺序存储结构和链式存储结构。
栈的顺序存储结构
顺序栈:顺序存储结构的栈。
顺序栈:用一组连续的存储单元存放自栈底到栈顶的数据元素,一般用一维数组表示
栈顶指针:指示栈顶位置
A
B
A
C
B
A
(a)空栈(b)元素A进栈(c)元素B、C进栈( d)出栈一次( e)出栈二次
top
-1
top
top
top
top
-1
4
3
2
1
0
4
3
2
1
0
4
3
2
1
0
4
3
2
1
0
4
3
2
1
0
顺序栈类型:
#define StackSize 100 /*顺序栈的初始分配空间*/
typedef struct sqst
{
DataType data[StackSize]; /*保存栈中元素*/
int top; /*栈指针*/
} SeqStack;
顺序栈被定义为一个结构体类型,有两个域:data和top。
data为一维数组,存储栈中元素,DataType为栈元素的数据类型,可以根据需要而指定为某种具体的类型。
top为int型,它的实际取值范围为0~StackSize-1。
top=-l表示栈空;top=StackSize-1表示栈满。
栈的长度:栈顶指针+1
顺序栈的基本运算算法:
(1) 初始化栈运算
功能:创建一个空栈,并将初始化栈顶下标top=-1。
int InitStack(SeqStack *&sq)
{
sq=(SeqStack *)malloc(sizeof(SeqStack));
if (!sq)
{ printf(“memory is not enough!”);
return 0;
}
sq->top=-1 ; return 1;
}
(2)进栈运算
功能:栈顶指针加1,将进栈元素放进栈顶指针所指的位置上。
int Push(SeqStack *sq, DataType x)
{
if(sq->top== StackSize-1)/*栈满*/
return 0;
else
{
sq->top++;
sq->data[sq->top]=x ;
return 1; }
}
(3)出栈运算
功能:先将栈顶元素取出,然后将栈顶指针减1。
int Pop(SeqStack *sq, DataType &x)
{
if(sq->top==-1) /*栈空*/
return 0;
else
{ x=sq->data[sq->top];
sq->top--; return 1;
}
}