川大数据结构与算法分析第三章堆栈和队列

Chapter 3 Stack & Queue

栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。 线性表 栈 队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n

栈和队列是两种常用的数据类型

Section 1 Stack

栈 ( Stack )只允许在一端插入和删除的线性表 允许插入和删除 退栈 进栈 的一端称为栈顶 (top),另一端称 top an-1 an-2 为栈底(bottom) 特点 a0 后进先出 (LIFO) bottom

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

DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &x) ClearStack(&S) Push(&S, x) Pop(&S, &x)

InitStack(&S)

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

StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈， 则返回 TRUE, 否则 FALE。

StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素 个数，即栈的 长度。

GetTop(S, &x) 初始条件：栈 S 已存在且非空 。 操作结果：用 x 返回 S 的栈顶 元素。a1 a 2 …… an

ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。

Push(&S, x) 初始条件：栈 S 已存在。 操作结果：插入元素 x 为新 的栈顶元素。a1 a 2 …… an x

Pop(&S, &x)初始条件：栈 S 已存在且非 空。 操作结果：删除 S 的栈顶元 素，并用 x 返回 其值。 a1 a2 … … an-1 an

栈的数组表示— 顺序栈

template <class Type> class Stack { private: int top; Type *elements; int maxSize; public: Stack ( int s = 10 ); ~Stack ( ) { delete [ ]elements; } int Push ( Type x );

int Pop ( Type &x ); int GetTop ( Type &x ); void MakeEmpty ( ) { top = -1; } int IsEmpty ( ) const { return top == 1; } int IsFull ( ) const { return top == maxSize-1; } }