文档介绍：第三章栈和队列
本章学****导读
从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。通过本章的学****读者应能掌握栈和队列的逻辑结构和存储结构,以及栈和队列的基本运算以及实现算法。
学****要点:
栈的定义
栈(stack)是限定在表尾一端进行插入或删除操作的线性表。在栈中,允许插入和删除操作的一端称为栈顶(top),而另一端称为栈底(bottom)。不含元素的栈称为空栈。
在栈的运算中,栈的插入操作称为进栈或入栈,栈的删除操作称为退栈或出栈。
a4 入栈
a3 出栈
栈底 bottom
栈的示意图
a3
a2
a1
栈顶top
根据栈的定义,每一次进栈的元素都在原栈顶元素之上,并成为新的栈顶元素;每一次出栈的元素总是当前的栈顶元素,因此最后进栈的元素总是最先出栈,所以栈也称为后进先出(Last In First Out)线性表,简称为LIFO表。
练****br/>设3个元素进栈的先后顺序为A,B,C,试问能否得到出栈顺序:
(1)ABC (2)CBA (3)ACB
(4)BAC (5)BCA (6)CAB
推论:元素进栈的先后顺序为…i…j…k…,则不能得到的出栈顺序为:
…k…i…j…
栈的学****br/>栈
逻辑结构:线性结构——后进先出
存储结构
基本运算:出栈、入栈、取栈顶元素
顺序存储:顺序栈
链接存储:链式栈
栈的存储实现和运算实现
1.  顺序栈
利用顺序存储方式实现的栈称为顺序栈。
c
b
a
0 1 2 3 … i-1 i i+1 … n-1 n …. n0
data
top
顺序栈的类型描述如下:
#define n0 100 //const int n0=100;
typedef char datatype;
typedef struct SeqStack
{
datatype data[n0+1];
int top;
}s;//定义一个顺序栈的变量: SeqStack s;
1.  顺序栈
通常0下标端设为栈底,这样空栈时栈顶指针top等于0; 入栈时,栈顶指针加1,指向新的栈顶; 出栈时,栈顶指针减1,指向新的栈顶。
top=0 top=1 top=5 top=2 top=0
(a)空栈(b)一个元素(c)5个元素(d)2个元素(e)空栈
栈的基本运算有如下几种:
(1)InitStack(S)
主要功能是:初始化操作,构造一个空栈操作。
(2)DestroyStack(S)
主要功能是:将已经存在的栈销毁。
(3)GetTop(S)
主要功能是:若栈S不空,则取栈顶元素的值,注意栈顶元素不被删除,栈顶指针top也不被改变。
(4)Push(S, x)
主要功能是:入栈操作,在S栈的顶部插入一个元素x,栈顶位置由top指针指出。
(5)Pop(S)
主要功能是:出栈操作,若栈S不空,则在栈顶删除栈顶元素,并返回被删除元素的值。
顺序栈的基本运算
以下几点说明:
1. 对于顺序栈,入栈时,首先判栈是否满了,栈满的条件为:= =n0,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。
2. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,否则产生错误。通常栈空时常作为一种控制转移的条件。
1. 置空栈:初始化栈顶指针。
void InitEmptyStack(SeqStack &st)
{ = 0; }
2. 判栈空
bool IsEmpty(SeqStack st)
{
if(==0)
return TRUE;
else
return FALSE;
}
3. 判栈满
bool IsFull(SeqStack st)
{
if(==n0)
return TRUE;
else
return FALSE;
}