文档介绍：第三章栈与队列
两种重要的,限定操作的线性结构。
学****要点:
栈的基本概念、结构特征和操作要点。
栈在顺序存储和链式存储结构下各种操作的实现,栈满与栈空判定条件。
队列基本概念、结构特征和操作要点。
队列在两种存储结构下各种操作如何实现,队满与队空判定条件。
循环队列基本概念,循环队列的队空与队满判定条件。
栈和队列的基本应用和应用要点。
§ 栈
栈的基本概念
栈的例子:操作系统中中断现场的保留等。
定义:限定只能在表的一端进行插入或删除操作的线性表。
修改原则:后进先出(LIFO)
练****br/>设进栈顺序为1、2、3、4,请说出以下的出栈顺序是否可能?
A、1 2 3 4 B、4 3 1 2
C、2 1 4 3 D、3 2 1 4
E、3 4 2 1 F、3 4 1 2
×
×
栈的抽象数据类型:
ADT Stack is
{数据对象:D={ai|ai∈DataType,i=0,1,2,…,n-1,n≥0}
数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n-1}约定an-1为栈顶,a0为栈底。
基本操作:
(1)Stack InitStack() 初始化并返回一个空栈;
(2)ClearStack (Stack S) 清空栈S中的元素;
(3)int IsEmpty(Stack S) 判断栈是否为空,返回栈空或非空标志;
(4)int IsFull(Stack S) 判断栈是否满,返回栈满或不满标志;
(5)Stack Push(Stack S, DataType x)
若栈未满,将数据元素x入栈;
(6)Stack Pop(Stack S) 若栈非空,删除栈顶元素;
(7)DataType GetTop(Stack S)
若栈非空,返回栈S中的取栈顶元素;
} ADT Stack
栈的顺序存储结构
数组定义栈:stack[max]
max-1
…
1
0
规定:top指向栈顶元素所在位置
初始:top=-1(空栈)
空栈:top=-1,出栈下溢
栈满:top=max-1,进栈上溢
栈的顺序存储结构2
(a)空栈(b)栈中有两个元素(c)栈满
图3-2 顺序栈各种情况
栈的顺序存储结构3
用C语言定义栈的顺序存储结构如下:
#define MAXSIZE 100
/* MAXSIZE指的是栈的最大长度*/
typedef struct
{DataType elem[MAXSIZE];
/* 定义数组依次存放栈里的数据元素*/
int top; /* 指向栈顶元素的下标*/
}Stack;
基本操作:顺序栈初始化
算法要求返回一个空的栈,空栈中数据元素个数为0,top值为-1。
00 Stack InitStack()
01 {
02 Stack S;
03 =-1; /* 空栈的top值为-1 */
04 return(S);
05 }
基本操作:进栈
已知栈S及数据元素x,需要将x放置进栈S
00 Stack Push(Stack S, DataType x)
/* 若栈未满,将数据元素x入栈*/
01 {
02 if (==MAXSIZE-1)
03 printf(“栈已满,无法入栈!”);
04 else
05 {
06 =+1;
07 []=x;
08 }
09 return(S);
10 }