文档介绍：第四章第四章
堆栈和队列堆栈和队列
队列
队列
堆栈
堆栈
域
域
领
领
枚举法、回溯法递归程序的执行过程
变量的存储空间的分配表达式的翻译与求值计算
作业调度、进程调度内存空间的分配
机
机
…
算
算
程序设计编译程序操作系统
计
计
在
在
本章内容本章内容
堆栈的基本概念
堆栈的顺序存储结构
堆栈的链式存储结构
堆栈的应用举例(习题课)
队列的基本概念
队列的顺序存储结构
队列的链式存储结构
堆栈的基本概念堆栈的基本概念
一. 堆栈的定义后进先出后进先出
堆栈堆栈是一种只允许在表的一端进行插入操
作和删除操作的线性表。允许操作的一端称为栈
顶,栈顶元素的位置由一个称为栈顶指针的变量
给出。当表中没有元素时,称之为空栈。
a b c d e x 进栈进栈
top
aeb dc 出栈出栈
top
退退进进
栈栈栈栈
toptop a
栈顶 n 后后
an-1 进
…进
a3 先先
a2 出出
a1
栈底
二. 堆栈的基本操作
√主
1. 插入(进栈、入栈) 要
2. 删除(出栈、退栈) √操
3. 测试堆栈是否为空√作
4. 测试堆栈是否已满
5. 检索当前栈顶元素
特特 1. 其操作仅仅是一般线性表的
殊殊操作的一个子集。
性性 2. 插入和删除操作的位置受到
限制。
堆栈的顺序存储结构堆栈的顺序存储结构
一. 构造原理
描述堆栈的顺序存储结构最简单的方法是
利用一维数组 STACK[ 0..M–1 ] 来表示,同时
定义一个整型变量( 不妨取名为top) 给出栈顶
元素的位置。
STACK[0..M-1]
0 1 2 3 4 …… M-1
a b c d e
top=4
数组:数组: 静态结构
堆栈:堆栈: 动态结构
溢出溢出
上溢上溢—当堆栈已满时做插入操作。(top=M–1)
下溢下溢—当堆栈为空时做删除操作。(top=–1)
类类型定型定义义
#define M 1000
SElemType STACK[M];
int top;
初始时初始时,top=,top= –1–1
二. 堆栈的基本算法
. 初始化堆栈初始化堆栈
void INITIALS( int &top )
{
top= –1;
}
. 测试堆栈是否为空测试堆栈是否为空栈空,返回1,否则,返回0。
int EMPTYS( int top )
{
return top== –1;
}