《数据结构 Data Structure》课程教学资源（PPT课件讲稿）第三章 栈和队列

第三章栈和队列 栈 队列 线性结构 优先级队列 与表不同的是,它们都是限制 存取位置的线性结构

1 第三章 栈和队列 栈 队列 优先级队列 与表不同的是，它们都是限制 存取位置的线性结构 线性结构

§3.1栈( stack) ·只允许在一端插入和删除的线性表 ·允许插入和删除退栈 进栈 (弹出) (压入) 的一端称为栈顶 (ap),另一端称b-an 为栈底( bottom) n-2 特点 1 后进先出(LFO)bomn

§3.1 栈（stack） • 只允许在一端插入和删除的线性表 • 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) • 特点 后进先出(LIFO) 2

栈的抽象数据类型 template 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 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 template class seqstack public stack t private: int top 栈顶指针 E *elements: 栈元素数组 int maxsize. 栈最大容量 void overflow Processo,∥栈的滋出处理

栈的数组表示 — 顺序栈 #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 (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

top-b top-a top→空栈 a进栈 b进栈 p top edcba edcba e进栈 f∫进栈滋出 进示例

top 空栈 top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 进栈示例 6

top cba op dcba to p cba e退栈 d退栈 C退栈 top b退栈 0p一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 seqstackE>:: overflow Processo& 私有函数:当栈满则执行扩充栈存储空间处 理 e* newArray =new e[2* maxSize]; 创建更大的存储数组 for (int 1=0; i<=top; 1++) newArrayli]=elements[i maxSize + maxSize delete l elements; elements= newArray;∥1变 elements指针

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)t ∥若栈不满,则将元素ⅹ插入该栈栈顶,否则溢出处理 if (IsFullo==true)overflowProcesso /棧满 elements{++top]=x;∥栈顶指针先加1,再进栈 template bool Seq Stack :: Pop(E& x)i ∥/函数退出栈顶元素并返回栈顶元素的值 if(IsEmptyo-true)return falSe I X= elements[top--1;/栈顶指针 return true 退栈成功

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: get Top(e&x)t /若栈不空则函数返回该栈栈顶元素的地址 if (Is empty==true)return false; x=elements[top]; return true

10 template bool Seqstack::getTop(E& x) { //若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() == true) return false; x = elements[top]; return true; };