第三章 栈和队列 栈 队列 线性结构 优先级队列 与表不同的是，它们都是限制 存取位置的线性结构
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 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 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 class SeqStack public Stack private: int top; /栈顶指针 E *elements; /栈元素数组 int maxSize; /栈最大容量 void overflowProcess(;/栈的益出处理
栈的数组表示 — 顺序栈 #include template class SeqStack : public Stack { 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
b top→a top L top→空栈 M进栈 b进栈 top e top e d d C c b b L L e进栈 ∫进栈溢出 进栈示例 6
top 空栈 top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 进栈示例 6
e top d d C top C C b b top b L L L e退栈 d退栈 C退栈 b top L L b退栈 top→a退栈 top→空栈 退栈示例
top c 退栈 b 退栈 a b a a 退栈 空栈 top a b d d 退栈 c top a b c top top top a b d e e 退栈 c 退栈示例7
顺序栈的操作 template void SeqStack::overflowProcess( /私有数：当栈满则执行扩充栈存储空间处 理 E *newArray new E[2*maxSizel; 川创建更大的存储数组 for (inti=0;i<-top;i++) newArray[i]elements[i; maxSize +maxSize; delete elements; elements newArray; /改变elements指针 }; 8
8 顺序栈的操作 template void SeqStack::overflowProcess() { //私有函数：当栈满则执行扩充栈存储空间处 理 E *newArray = new E[2*maxSize]; //创建更大的存储数组 for (int i = 0; i <= top; i++) newArray[i] = elements[i]; maxSize += maxSize; delete [ ]elements; elements = newArray; //改变elements指针 };
template void SeqStack:Push(E x) /若栈不满，则将元素X插入该栈栈顶，否则溢出处理 if (IsFullO==true)overflowProcess(); /栈满 elements[++top]=x; /栈顶指针先加1，再进栈 }; template bool SeqStack:Pop(E&x) /川丞数退出栈顶元素并返回栈顶元素的值 if (IsEmpty()==true)return false; x elements[top--]; 川栈顶指针退1 return true; 川退栈成功 }; 9
9 template void SeqStack::Push(E x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess(); //栈满 elements[++top] = x; //栈顶指针先加1, 再进栈 }; template bool SeqStack::Pop(E& x) { //函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; //栈顶指针退1 return true; //退栈成功 };
template bool Seqstack::getTop(E&x) /若栈不空则極数返回该栈栈顶元素的地址 if (IsEmpty()==true)return false; x elements[top]; return true; }; 10
10 template bool Seqstack::getTop(E& x) { //若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() == true) return false; x = elements[top]; return true; };