文档介绍：第三章栈和队列
本章主要介绍栈和队列的定义,在顺序和链式存储结构上如何实现栈和队列的基本操作,以及栈和队列的基本应用等知识。
栈
定义
一、栈的定义及基本操作
与线性表相同,数据元素之间仍为一对一的关系。
用顺序栈或链栈存储均可。
只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。
关键是编写入栈、出栈等函数。
存储结构
运算规则
实现方式
逻辑结构
限定只能在表的一端进行插入和删除运算的线性表。
基本操作
建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值,等等。
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即an端)称为栈顶(top) ;
表头(即a1端)称为栈底(bottom)。
例如: 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作,称为入栈。
从栈顶删除元素的操作,称为出栈。
an称为栈顶元素
a1称为栈底元素
强调:插入和删除都只能在表的一端(栈顶)进行!
栈的基本操作:
InitStack(S): 构造一个空栈S。
ClearStack(S): 清除栈S中的所有元素。
StackEmpty(S):判断栈S是否为空,若为空,则返回 true否则返回false。
GetTop(S): 返回S的栈顶元素,但不移动栈顶指针。
Push(S,x):插入元素x为新的栈顶元素。
Pop(S,x): 删除S的栈顶元素并返回其值。
二、顺序栈的存储结构和操作的实现
顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。通常由一个一维数组和一个记录栈顶元素位置的变量组成。
在C语言中,预设一个数组的最大空间,栈底设置在0下标端,栈顶随着插入和删除元素而变化,用一个整型变量top来指示栈顶的位置。
a1
a2
……
an
顺序栈S
ai
……
0
n-1
压入(PUSH): S[++top]=an+1
弹出( POP): e=S[top --]
1、顺序栈存储结构的描述:
#define Maxsize 100 /*设顺序栈的最大长度为100,可依实际情况而修改*/
typedef int datatype;
typedef struct
{
datatype stack[Maxsize];
int top; /*栈顶指针*/
}SeqStack; /*顺序栈类型定义*/
SeqStack *s; /*s为顺序栈类型变量的指针*/
其中:
data域:为一个一维数组,用于存储栈中元素。
top域:栈顶指针。取值范围为0~MaxSize-1。
top=-1表示栈空,top=MaxSize-1表示栈满。(两个要素)
顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系(最大长度MaxSize为4)。
(a)当栈中无数据元素时,表示栈空。
(b)表示在(a)基础上执行Push(S, ‘A’)后得到这种状态。
(c)又有元素B,C,D先后入栈,此时栈顶元素的下标值top=3。
(d)表示在(c)状态下,执行一次Pop(S,x)运算得到。
(e)表示在(d)状态下,执行三次Pop(S,x)运算得到。
若入栈动作使地址向高端增长,称为“向上生成”的栈;
若入栈动作使地址向低端增长,称为“向下生成”的栈;
对于向上生成的堆栈:
入栈:栈指针top “先加后压”: S[++top]=an+1 (要素3)
出栈:栈指针top “先弹后减”: e=S[top--] (要素4)
2、顺序栈的基本操作
表示栈空:top=-1 (要素1)
表示栈满:top=MaxSize-1 (要素2)
试给出“向下生长”的栈的四个要素。
表示栈空:top=Maxsize (要素1)
表示栈满:top=0 (要素2)
入栈:栈指针top “先减后压”: S[- -top]=an+1 (要素3)
出栈:栈指针top “先弹后加”: e=S[top++] (要素4)