文档介绍：第3章栈和队列
栈
栈的基本概念
栈的顺序存储
栈的链式存储
栈的应用
队列
栈和队列是两种应用非常广泛的数据结构,它们都属于线性表数据结构,但属于“操作受限”的线性表。
栈在计算机中的实现有多种方式:
◆硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快;
◆软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种。
本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。
栈
栈的基本概念
栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom):是固定端,又称为表头。
空栈:当表中没有元素时称为空栈。
设栈S=(a1,a2,…an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。
栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。
图3-1 顺序栈示意图
a1
a2
ai
an
⋯⋯
⋯⋯
bottom
top
进栈(push)
出栈(pop)
栈的顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储栈。由数组是否可以依需要增大,又可分为静态顺序栈和动态顺序栈。
◆静态顺序栈实现简单,但不能根据需要增大栈的存储空间;
◆动态顺序栈可以根据需要增大栈的存储空间,但实现稍为复杂。
栈的顺序存储表示
采用动态一维数组来存储栈。所谓动态,指的是栈的大小可以根据需要增加。
◆用bottom表示栈底指针,栈底是固定不变的;栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
◆用top=bottom作为栈空的标记,每次top指向栈顶数组中的下一个存储位置。
◆结点进栈:首先将数据元素保存到栈顶(top所指的当前位置),然后执行top加1,使top指向栈顶的下一个存储位置;
◆结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。
图3-2是一个动态栈的变化示意图。
栈的动态顺序存储表示
空栈
bottom
top
元素a进栈
bottom
top
a
元素b,c进栈
bottom
top
a
b
c
图3-2 (动态)堆栈变化示意图
元素c退栈
bottom
top
a
b
bottom
top
a
b
d
e
f
元素d,e,f 进栈
基本操作的实现
(1)栈的类型定义
#define STACK_SIZE 100 /* 栈初始向量大小*/
#define STACKINCREMENT 10 /* 存储空间分配增量*/
#typedef int ElemType ;
typedef struct sqstack
{ ElemType *bottom; /* 栈底指针,栈不存在时值为NULL */
ElemType *top; /* 栈顶指针*/
int stacksize ; /* 栈分配空间,以元素为单位*/
}SqStack ;
(2)栈的初始化
Status Init_Stack(void)
{
SqStack S ;
=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));
if (!) return ERROR;
= ; /* 栈空时栈顶和栈底指针相同*/
= STACK_SIZE;
return OK ;
}
(3)压栈(元素进栈)
Status push(SqStack S , ElemType e)
{
if (->=S. stacksize-1)
{ =(ElemType *)realloc((+STACK_SIZE)
*sizeof(ElemType)); /* 栈满,追加存储空间*/
if (!) return ERROR;
= + ;
+= STACKINCREMENT ;
}
*=