文档介绍：栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。
和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。
第三章 栈和队列
第三章 栈和队列
插 入 删 除
线性表： Insert(L,i,x) Delete(L,i) (1≤i≤n+1) (1≤i≤n)
栈： Insert(L,n+1,x) Delete(L,n)
队列： Insert(L,n+1,x) Delete(L,1)
正是由于这种限定，使得栈和队列无论是在系统软
件中，还是在应用软件中都被经常的应用。
栈的类型定义
栈的应用举例
队列
第三章 栈和队列
定义: 是限定仅在表尾进行插入或删除操作的线性表。
允许插入和删除的一端
称为栈顶(top)，另一端
称为栈底(bottom)
特点：后进先出 (LIFO)
a1
top
bottom
an
.
.
.
.
进栈
出栈
栈的类型定义
栈的类型定义
通常称往栈顶插入元素的操作为“入栈”，称删除栈顶元素的操作为“出栈”。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种“后进先出”的结构，因此又称LIFO（Last In First Out的缩写）表。很多书上都以如右图所示的铁路调度站形象地表示栈的这个特点。
栈的类型定义
举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
栈的抽象数据类型定义
ADT Stack｛
数据对象：
D=｛ai| ai ElemSet，i=1，2，…，n，n 0｝
数据关系：
R=｛< ai-1，ai > | ai-1 ， ai D，i=2，…，n｝
约定an端为栈顶，a1端为栈底。
基本操作：
1.｛结构初始化｝
InitStack（&S)
操作结果：构造一个空栈S。
栈的抽象数据类型定义
2.｛销毁结构｝
DestroyStack（&S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
3.｛引用型操作｝
StackEmpty(L)
初始条件：栈S已存在。
操作结果：若栈S为空，则返回TRUE，否则返回
FALSE。
栈的抽象数据类型定义
StackLength(S)
初始条件：栈 S 已存在。
操作结果：返回栈 S 中元素个数，即栈的长度。
GetTop(S, &e)
初始条件：栈 S 已存在且非空。
操作结果：用 e 返回S的栈顶元素。
StackTraverse(S, visit( ))
初始条件：栈 S 已存在且非空，visit( )为元素的访问函数。
操作结果：从栈底到栈顶依次对S的每个元素调用函数
visit( )，一旦visit( )失败，则操作失败。
栈的抽象数据类型定义
4.｛加工型操作｝
Push(&S, e)
初始条件：栈 S 已存在。
操作结果：插入元素 e 为新的栈顶元素。
Pop(&S, &e)
初始条件：栈 S 已存在且非空。
操作结果：删除 S 的栈顶元素，并用 e 返回其值。
ClearStack(&S)
初始条件：栈 S 已存在。
操作结果：将 S 清为空栈。
｝ADT Stack