中山大学-栈和队列

第三章 栈和队列 栈和队列是在程序设计中被广泛使用的两种线性数据结 构。 与线性表相比，它们的插入和删除操作受更多的约束和 限定，故又称为限定性的线性表结构。

线性表允许在表内任一位置进行插入和删除；栈只允许在表尾一端进行插入和删除； 队列只允许在表尾一端进行插入，在表头一端进行删除。

Data Structure

2014-7-28

Page 1

3.1 栈 栈

限定只能在表的一端进行插入和删除操作的线性表。 栈顶(top):允许插入和删除的一端。 栈底(bottom):不允许插入和删除的另一端。 空栈：不含元素的空表。进栈栈顶 ... 出栈

特点

先进后出(FILO) 后进先出(LIFO)

an

……...

(Last In First Out) 栈底Data Structure 2014-7-28

a2 a1Page 2

说明：

base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 top为栈顶指针 a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 stacksize ——当前栈可使用的最大容量

Data Structure

2014-7-28 第3 章

Page 3

栈的抽象数据类型定义ADT Stack { 数据对象：D={ai| ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1={ <ai-1,ai >| ai-1,ai∈D, i=2,...,n } 基本操作：

InitStack(&S) 操作结果：构造一个空栈 S。DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。

Data Structure

2014-7-28

Page 4

ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE,否则返回 FALSE。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回栈 S 中元素个数，即栈的长度。

Data Structure

2014-7-28

Page 5

GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。

Data Structure

2014-7-28

Page 6

StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( )为元素的访问 函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数 visit( ),一旦visit( )失败，则操作失败。 } ADT Stack

Data Structure

2014-7-28

Page 7

栈的顺序存储(顺序栈) 利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素。 结构定义： #define STACK_INIT_SIZE 100; // 存储空间初始分配量 #define STACKINCREMENT 10; // 存储空间分配增量 typedef struct { SElemType *base; // 存储空间基址 SElemType *top; // 栈顶指针 int

stacksize; // 当前已分配的存储空间，以元素位单位 } SqStack;

Data Structure

2014-7-28

Page 8

线性表的动态分配顺序存储结构(用一维数组)#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量 #define LISTINCREAMENT 10 //线性表存储空间的分配增量 typedef struct { ElemType *elem; //存储空间基地址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList;

Data Structure

2014-7-28

Page 9

栈的顺序存储(顺序栈) 利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素。 结构定义： #define STACK_INIT_SIZE 100; // 存储空间初始分配量 #define STACKINCREMENT 10; // 存储空间分配增量 typedef struct { SElemType *base; // 存储空间基址 SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素位单位 } SqStack;

Data Structure

2014-7-28

Page 10

栈满 5 top top top top top top F E D C B A 进栈

栈空 top top top top top top top

54 3 2 1 0

F E D CB A 出栈

5 4 3

4 32 1 top=0 0 栈空

2 1 0

设数组大小为M 栈顶指针top,指向实际栈顶 top=0,栈空，此时出栈，则下溢(underflow) 后的空位置，初值为0 top=M,栈满，此时入栈，则上溢(overflow)Data Structure 2014-7-28 Page 11

基本操作接口(函数声明)void InitStack (SqStack &S);//构造一个空栈S。

void DestroyStack (SqStack &S);//销毁栈S,S 不再存在。

void ClearStack (SqStack &S);//将 S 置为空栈。

bool StackEmpty (SqStack S);//若栈 S 为空栈。

int StackLength (SqStack S);//返回S的元素个数，即栈的长度。

bool GetTop (SqStack S, SElemType &e);//若栈不空，则用 e 返回S的栈顶元素，并返回TRUE;否则返回 FALSE。

bool Push (SqStack &S, SElemType e);//若栈的存储空间不满，则插入元素

e ,并返回 TRUE;否则返回FALSE。

bool Pop (SqStack &S, SElemType &e);//若栈不空，则删除S的栈顶元素，用e返回其值，并返回TRUE;否则返回FALSE。

void StackTraverse(SqStack S, Status (*visit())//依次对S的每个元素调用函数 visit( ),一旦 visit( )失败，操作失败。Data Structure 2014-7-28 Page 12

几点说明：

栈空条件：s. top =s. base 此时不能出栈 栈满条件：s.top-s.base>=s.stacksize 进栈操作：*s.top++=e; 或*s.top=e; s.top++; 退栈操作：e=*--s.top; 或s.top--; e=*s.top; 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。

Data Structure

2014-7-28 第3 章

Page 13

基本操作的算法描述Status InitSt …… 此处隐藏：1986字，全部文档内容请下载后查看。喜欢就下载吧 ……