翦四拿彎訇队 栈( Stack) 队列( Queue) 优先队列( Priority Oueue)
栈 ( Stack ) 队列 ( Queue ) 优先队列 (Priority Queue)
栈( Stack) 只允许在一端插入和删除的顺序表 允许插入和删除进栈 退栈 (压入) 弹出) 的一端称为栈顶 (tp),另一端称 to p n-1 为栈底( bottom) an-2 特点 后进先出(LFO 01 0 botton→
栈 ( Stack ) 只允许在一端插入和删除的顺序表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO)
栈的抽象数据类型 template class Stack i ublic Stack(int=10 ) /构造函数 void push( const Type&item);∥进栈 Type Pop o: 出栈 ype GetTop (; /取栈顶元素 void MakeEmp(;∥量空栈 int IsEmpty() const;/判栈空否 int IsFull( const; /判栈满否
template class Stack { public: Stack ( int=10 ); //构造函数 void Push ( const Type & item); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 } 栈的抽象数据类型
栈的数组表示一顺序栈 include assert h> template class Stack i public: Stack( int=10 ); 构造函数 Sck(){ delete[] elements;M/析构函数 void push( const Type&iem);∥进 Type Pop (; ∥/出栈 Type GetTop o; /取栈顶元素 void MakeEmpty(){top=-1;}∥量空栈 int IsEmpty( const return top==-1;)
#include template class Stack { public: Stack ( int=10 ); //构造函数 ~Stack ( ) { delete [ ] elements; }//析构函数 void Push ( const Type & item ); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ) { top=-1; } //置空栈 int IsEmpty ( ) const { return top == -1; } 栈的数组表示 — 顺序栈
int IsFull( const i return top==maxSize-l;3 private: int top; 顶数组指针 Iype* elements;数组 int max size 最大容量 template Stack:: Stack( int s): top(1), maxSize(s)i elements=new Type[max]; assert( elements!=0);∥断言
int IsFull ( ) const { return top == maxSize-1; } private: int top; //栈顶数组指针 Type *elements; //栈数组 int maxSize; //栈最大容量 } template Stack:: Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert ( elements != 0 ); //断言 }
b to p top→空栈 →a进栈 b进栈 to p to p edcb 充edcb 选栈示例 进栈 Z进栈溢出
进栈示例
to p edcb top- d top- b dcba 退栈 e退栈 d退栈 b 退栈示例 tp→a退栈top→空栈
退栈示例
template void Stack:: Push( const Type item)t assert(!Is Full () ∥/先决条件断言 elements[++top]=item;1入新元素 template Type Stack:: Popoi aert( EMpty());∥先决条件断言 return elements[op-;/出栈顶元素
template void Stack:: Push ( const Type & item ) { assert ( !IsFull ( ) ); //先决条件断言 elements[++top] = item; //加入新元素 } template Type Stack:: Pop ( ) { assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top--]; //退出栈顶元素 }
template Type stack:: GetTopoi assert(!sEm();∥先决条件断言 return elements{top];/取出栈顶元素 双栈共享一个栈空间 maxSize-1 b[0 t[0] t[ b[1
template Type stack:: GetTop ( ) { assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top]; //取出栈顶元素 } 双栈共享一个栈空间
多栈处理栈浮动技术 n栈共享一个数组空间Mml 设立栈顶指针数组tm+1和 栈底指针数组b[n+1 卬和b分别指示第栈的栈顶与栈底 bm作为控制量,指到数组最高下标 各栈初始分配空间s=Lm/n」 指针初始值t0=b[0]=-1bl=m-1 t=b=b[i-1+s,i=1,2,…,n-1
多栈处理 栈浮动技术 n栈共享一个数组空间V[m] 设立栈顶指针数组 t [n+1] 和 栈底指针数组 b [n+1] t[i]和b[i]分别指示第i个栈的栈顶与栈底 b[n]作为控制量，指到数组最高下标 各栈初始分配空间 s = m / n 指针初始值 t[0] = b[0] = -1 b[n] = m-1 t[i] = b[i] = b[i-1] + s, i = 1, 2, …, n-1