第三章 栈和队列 栈 队列 线性结构 优先级队列 与表不同的是，它们都是限制 存取位置的线性结构
1 第三章 栈和队列 栈 队列 优先级队列 与表不同的是，它们都是限制 存取位置的线性结构 线性结构
§3.1栈(stack) ·只允许在一端插入和删除的线性表 允许插入和删除 退栈 进栈 (弹出) (压入) 的一端称为栈顶 (top),另一端称 top an-1 为栈底(bottom) 4n-2 ·特点 1 o 后进先出(LIFO) bottom→ 2
§3.1 栈（stack） • 只允许在一端插入和删除的线性表 • 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) • 特点 后进先出(LIFO) 2
栈的抽象数据类型 template <class E>class Stack{ public: Stack int=10 ) /构造函数 void Push(const E&item);/进栈 E Pop () 出栈 E getTop () /取栈顶元素 void makeEmpty () /置空栈 int IsEmpty (const; /判栈空否 int IsFull const; /判栈满否 } 3
template <class E> class Stack { public: Stack ( int=10 ); //构造函数 void Push ( const E & item); //进栈 E Pop ( ); //出栈 E getTop ( ); //取栈顶元素 void makeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 } 栈的抽象数据类型 3
栈的数组表示一顺序栈 0123456789 maxSize-1 elements top(栈空) #include <assert.h template <class E> class SeqStack public Stack<E> private: int top; /栈顶指针 E *elements; /栈元素数组 int maxSize; /栈最大容量 void overflowProcess(;/栈的益出处理
栈的数组表示 — 顺序栈 #include <assert.h> template <class E> class SeqStack : public Stack<E> { private: int top; //栈顶指针 E *elements; //栈元素数组 int maxSize; //栈最大容量 void overflowProcess(); //栈的溢出处理 0 1 2 3 4 5 6 7 8 9 maxSize-1 top (栈空) elements 4
public: Stack (int sz=10); /构造函数 ~Stack )delete elements; void Push (E x); /进栈 int Pop E&x); /出栈 int getTop (E&x); /取栈顶 void makeEmpty(){top=-l;}∥置空栈 int IsEmpty (const return top ==-1;} int IsFull (const return top =maxSize-1; 3 5
public: Stack (int sz = 10); //构造函数 ~Stack ( ) { delete [ ] elements; } void Push (E x); //进栈 int Pop (E& x); //出栈 int getTop (E& x); //取栈顶 void makeEmpty ( ) { top = -1; } //置空栈 int IsEmpty ( ) const { return top == -1; } int IsFull ( ) const { return top == maxSize-1; } } 5