第三章栈和队列 栈 队列 线性结构 优先级队列 与表不同的是,它们都是限制 存取位置的线性结构
1 第三章 栈和队列 栈 队列 优先级队列 与表不同的是，它们都是限制 存取位置的线性结构 线性结构
§3.1栈( stack) ·只允许在一端插入和删除的线性表 ·允许插入和删除退栈 进栈 (弹出) (压入) 的一端称为栈顶 (ap),另一端称b-an 为栈底( bottom) n-2 特点 1 后进先出(LFO)bomn
§3.1 栈（stack） • 只允许在一端插入和删除的线性表 • 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) • 特点 后进先出(LIFO) 2
栈的抽象数据类型 template <class e> class stack i p ublic. Stack( int=10) /构造函数 void push( const e&iem);/进栈 E Pop o; /出栈 e getTopo /取栈顶元素 void make Empt(;置空栈 int IsEmpty() const;/判栈空否 int sfu( const;/判栈满否
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> t private: int top 栈顶指针 E *elements: 栈元素数组 int maxsize. 栈最大容量 void overflow Processo,∥栈的滋出处理
栈的数组表示 — 顺序栈 #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 (i delete [elements; void Push(e x 进栈 int Pop(& x) ∥/出栈 int getTop(E&x);∥取栈顶 void make Empty(){top=-1;}∥空栈 int Is Empty const return top ==-1; 3 int IsFull ( const freturn top=-maxSize-1; 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