《栈和队列梁》PPT课件

1、主讲：梁宝兰主讲：梁宝兰 三种特殊的线性表三种特殊的线性表栈、队列、优先队列栈、队列、优先队列掌握栈、队列、优先队列的相关概念；掌握栈、队列、优先队列的相关概念；掌握栈、队列、优先队列的顺序存储与链式存掌握栈、队列、优先队列的顺序存储与链式存储构造储构造掌握栈和队列的运用，了解优先队列的运用掌握栈和队列的运用，了解优先队列的运用生活中的例子：生活中的例子：羊肉串羊肉串 子弹夹子弹夹食堂吃饭队伍食堂吃饭队伍银行柜台效力银行柜台效力它们都是操作受限的线性表它们都是操作受限的线性表一、栈的根本概念一、栈的根本概念堆栈堆栈(Stack) (Stack) ：限定仅在表的一端进：限定仅在表的一端进展插入和

2、删除操作的线性表。展插入和删除操作的线性表。栈顶栈顶(top):(top):表的插入和删除端。表的插入和删除端。栈底栈底(bottom)(bottom)：表的另一端。：表的另一端。空栈：没有任何元素的栈。空栈：没有任何元素的栈。特点：先进后出特点：先进后出a4a3a2a1top入栈入栈出栈出栈a1a2a3入栈入栈出栈出栈栈底栈底/栈顶栈顶栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的表示图栈的表示图栈的操作特性：后进先出栈的操作特性：后进先出a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出

3、栈、弹栈删除：出栈、弹栈栈顶栈顶栈的表示图栈的表示图例例3-1：有三个元素按：有三个元素按a、b、c的次序依次进栈，且每的次序依次进栈，且每个元素只允许进一次栈，那么能够的出栈序列有多少个元素只允许进一次栈，那么能够的出栈序列有多少种？种？栈顶栈顶/栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况1：栈顶栈顶/栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a 情况情况1：例例3-1：有三个元素按：有三个元素按a、b、c的次序依次进栈，且每的次序依次进栈，且每个元素只允许进一次栈，那么能够的出栈序列有多少个元素只允许进一次栈，那

4、么能够的出栈序列有多少种？种？栈顶栈顶/栈底栈底栈顶栈顶ab栈顶栈顶出栈序列：出栈序列：b 情况情况2：例例3-1：有三个元素按：有三个元素按a、b、c的次序依次进栈，且每的次序依次进栈，且每个元素只允许进一次栈，那么能够的出栈序列有多少个元素只允许进一次栈，那么能够的出栈序列有多少种？种？栈底栈底a出栈序列：出栈序列：b出栈序列：出栈序列：b、c出栈序列：出栈序列： b、 c、ac栈顶栈顶栈顶栈顶留意：栈只是对表插入和删除操作的位置进展了限留意：栈只是对表插入和删除操作的位置进展了限制，并没有限定插入和删除操作进展的时间。制，并没有限定插入和删除操作进展的时间。 情况情况2：例例3-1：有三

5、个元素按：有三个元素按a、b、c的次序依次进栈，且每的次序依次进栈，且每个元素只允许进一次栈，那么能够的出栈序列有多少个元素只允许进一次栈，那么能够的出栈序列有多少种？种？ADT StackData 栈中元素具有一样类型及后进先出特性，栈中元素具有一样类型及后进先出特性， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitStack 前置条件：栈不存在前置条件：栈不存在 输入：无输入：无 功能：栈的初始化功能：栈的初始化 输出：无输出：无 后置条件：构造一个空栈后置条件：构造一个空栈 DestroyStack 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无

6、 功能：销毁栈功能：销毁栈 输出：无输出：无 后置条件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间Push 前置条件：栈已存在前置条件：栈已存在 输入：元素值输入：元素值x 功能：在栈顶插入一个元素功能：在栈顶插入一个元素x 输出：假设插入不胜利，抛出异常输出：假设插入不胜利，抛出异常 后置条件：假设插入胜利，栈顶添加了一个元素后置条件：假设插入胜利，栈顶添加了一个元素Pop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：删除栈顶元素功能：删除栈顶元素 输出：假设删除胜利，前往被删元素值，否那么，输出：假设删除胜利，前往被删元素值，否那么，抛出异常抛出异常 后置条件

7、：假设删除胜利，栈减少了一个元素后置条件：假设删除胜利，栈减少了一个元素GetTop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：读取当前的栈顶元素功能：读取当前的栈顶元素 输出：假设栈不空，前往当前的栈顶元素值输出：假设栈不空，前往当前的栈顶元素值 后置条件：栈不变后置条件：栈不变Empty 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：判别栈能否为空功能：判别栈能否为空 输出：假设栈为空，前往输出：假设栈为空，前往1，否那么，前往，否那么，前往0 后置条件：栈不变后置条件：栈不变endADT顺序栈顺序栈栈的顺序存储构造栈的顺序存储构造如何改造数组实现栈的顺

8、序存储？如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。 toptop出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top= 0 不能出栈不能出栈栈满：栈满：top= MAX_SIZE 不能进栈不能进栈 0 1 2 3 4 5 6 7 8a1topa2topa3top/顺序栈类的实现顺序栈类的实现const int Max=100;typedef char Data;class SeqStack private: int Ma

9、xSize; int top; Data *s; /栈动态数组指针栈动态数组指针 public: SeqStack(int max); /构造函数构造函数 void ClearStack(void); /清空栈清空栈 void Push(const Data& x); /压栈压栈 Data Pop(void); /弹出栈弹出栈 Data GetTop(void); /取栈顶元素取栈顶元素 bool IsFull(void); /判别栈能否为满判别栈能否为满 bool IsEmpty(void); /判别栈能否为空判别栈能否为空 ;/顺序栈的实现顺序栈的实现SeqStack: SeqSt

10、ack (int max) /构造函数构造函数 s = new Data max; MaxSize = max; top = 0; /指向栈中最后一个元素后一个元指向栈中最后一个元素后一个元素素/顺序栈的实现顺序栈的实现bool SeqStack IsEmpty() /判别能否空判别能否空 return top =0;bool SeqStack :IsFull() /判别能否满判别能否满 return top = MaxSize ;/顺序栈的实现顺序栈的实现Data SeqStack : GetTop() const /取栈顶元素取栈顶元素 if(top=0) cout“栈为空栈为空endl;

11、 exit(0);return stop-1;/顺序栈的实现顺序栈的实现void SeqStack :Push(const Data& x) if (top = MaxSize) /判别栈能否已满判别栈能否已满 cout“栈已满栈已满endl; exit(0); stop = x; /在新的栈顶位置放入要压栈的元素在新的栈顶位置放入要压栈的元素 top+; /top指示上一个存储单元指示上一个存储单元/顺序栈的实现顺序栈的实现Data SeqStack :Pop(void) Data temp; if (top = = 0) /判别栈能否为空判别栈能否为空 cout“栈已空栈已空!ne

12、xt = = NULL) return 1; else return 0;/析构函数析构函数LinkStack:LinkStack() StackNode *p,*q; p = top; while (p!=NULL) q = p; p = p-next; delete q; /压栈操作：在链栈的头结点后面插入一个结点压栈操作：在链栈的头结点后面插入一个结点void LinkStack:Push(const Data& x) StackNode* p; p = new StackNode(x); p-next = top-next; top-next = p;/出栈操作：删除链栈头结点

13、后面的一个结点出栈操作：删除链栈头结点后面的一个结点Data LinkStack:Pop() Data x; StackNode *p = top-next; if (p = = NULL) cout栈已空！栈已空！next = p-next; x = p-data; delete p; return x; 假设采用不带头结点的单链表实现栈，有关假设采用不带头结点的单链表实现栈，有关栈的操作如何调整？包括构造函数、压栈、栈的操作如何调整？包括构造函数、压栈、出栈、判空等操作，他以为这种做法好吗？出栈、判空等操作，他以为这种做法好吗？ 数制转换数制转换 /把一个长整型数把一个长整型数num转换为

14、一个转换为一个r进制数进制数输出输出实现算法思想：把实现算法思想：把num不断地除以不断地除以r取余数，并取余数，并把余数压栈，然后取商除以把余数压栈，然后取商除以r取余，并把余数压栈；取余，并把余数压栈；直到商为直到商为0；把栈中的数弹栈输出。；把栈中的数弹栈输出。数制转换思想：把数制转换思想：把num不断地除以不断地除以r取余数，然取余数，然后取商除以后取商除以r取余，直到商为取余，直到商为0；把余数出现的次；把余数出现的次序，从后到先进展陈列，即为相应的序，从后到先进展陈列，即为相应的r进制数进制数源程序源程序string DecToBin(int n) SeqStack stk; st

15、ring s; char ch; int k = n; while (k!=0) /余数压栈余数压栈 ch = 0+k%2; stk.Push(ch); k /=2; while(!stk.IsEmpty() /余数弹栈余数弹栈 s += stk.Pop(); return s;括号匹配问题括号匹配问题三种括号：三种括号：“(和和“)、“和和“、“和和“，并且这三种括号可以按照恣意的次序嵌套运，并且这三种括号可以按照恣意的次序嵌套运用，但不可交叉。用，但不可交叉。例：匹配：例：匹配： ( ( ) ) 不匹配：不匹配： 怎样判别能否匹配？怎样判别能否匹配？利用栈进展表达式中的括号匹配利用栈进展表

16、达式中的括号匹配 自左至右扫描表达式，假设遇左括号那么将该自左至右扫描表达式，假设遇左括号那么将该左括号入栈，假设遇右括号，那么将其与栈顶的左左括号入栈，假设遇右括号，那么将其与栈顶的左括号进展匹配，假设配对，那么栈顶的左括号出栈。括号进展匹配，假设配对，那么栈顶的左括号出栈。源程序源程序一、队列的根本概念一、队列的根本概念 队列：只允许在一端进展插入操作，而另一队列：只允许在一端进展插入操作，而另一端进展删除操作的线性表。端进展删除操作的线性表。空队列：不含任何数据元素的队列。空队列：不含任何数据元素的队列。 队头：允许删除也称出队的一端。队头：允许删除也称出队的一端。 队尾：允许插入也称入

17、队、进队的一端。队尾：允许插入也称入队、进队的一端。a1, a2, , an队尾队尾队头队头队列的操作特性：先进先出队列的操作特性：先进先出a1a2a3入队入队队尾队尾队头队头出队出队队头队头二、队列的逻辑构造二、队列的逻辑构造三、队列的顺序存储构造及实现三、队列的顺序存储构造及实现 0 1 2 3 4 入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrearrear rear入队操作时间性能为入队操作时间性能为O(1)front rearfront指向队列存储空间的第一个元素指向队列存储空间的第一个元素rear指向队列数据元素的最后一个元素的下一个元素指向队列

18、数据元素的最后一个元素的下一个元素例：例：a1a2依次出队依次出队0 1 2 3 4 入队入队出队出队a1a2a3a4rearfront front front出队操作时间性能为出队操作时间性能为O(1)三、队列的顺序存储构造及实现三、队列的顺序存储构造及实现 队列的挪动有什么特点？队列的挪动有什么特点？单向挪动性：整个队列向数组下标较大方向挪动单向挪动性：整个队列向数组下标较大方向挪动假溢出：当元素被插入到数组中下标最大的位置上之假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，虽然此时数组的低端还有后，队列的空间就用尽了，虽然此时数组的低端还有空闲空间，这种景象叫做假溢

19、出。空闲空间，这种景象叫做假溢出。继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear三、队列的顺序存储构造及实现三、队列的顺序存储构造及实现 循环队列：将存储队列的数组头尾相接。循环队列：将存储队列的数组头尾相接。rear=rear+1 改为改为 rear= (rear+1) % MaxSizefront=front+1 改为改为 front= (front+1) % MaxSize如何处理假溢出？如何处理假溢出？0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6三、队列的顺序存储构造及实现三、

20、队列的顺序存储构造及实现 三、队列的顺序存储构造及实现三、队列的顺序存储构造及实现 ABCDEFfrontrearA012543210BCDEF345frontrearrearrearrearrearrearrear队空：队空：front=rear队满：队满：front=rear怎样区分队空和队满怎样区分队空和队满方法一：附设一个存储队列中元素个数的变量方法一：附设一个存储队列中元素个数的变量num，当当num=0时队空，当时队空，当num=MaxSize时为队满；时为队满；方法二：修正队满条件，浪费一个元素空间，队满时方法二：修正队满条件，浪费一个元素空间，队满时数组中只需一个空闲单元；数组

21、中只需一个空闲单元；队满的条件：队满的条件：(rear+1) %MaxSize=front队空的条件：队空的条件：rear=front方法三：设置标志方法三：设置标志flag，当，当front=rear且且flag=0时为队时为队空，当空，当front=rear且且flag=1时为队满。时为队满。区分队空与队满的方法：区分队空与队满的方法：三、队列的顺序存储构造及实现三、队列的顺序存储构造及实现 循环队列类的定义循环队列类的定义 class SeqQueue private: Data *q; int front,rear; int count; int MaxSize; public: Se

22、qQueue(); /构造函数构造函数 void Clear(void); /清空队列清空队列 void Append(const Data& x); /进队操作进队操作 Data Delete(void); /出队操作出队操作 Data GetFront(void); /取队头元素取队头元素 Data GetRear(void); /取队尾元素取队尾元素 bool IsFull(void); /判满判满 bool IsEmpty(void); /判空判空 ;/初始化操作初始化操作SeqQueue:SeqQueue() q=new DataMaxSize; front = 0; rea

23、r = 0; count=0;/ 队列清空操作队列清空操作void SeqQueue:Clear(void) rear = front; count=0;/判空、判满操作判空、判满操作bool SeqQueue:IsEmpty(void) if(front=rear) return 1; else return 0;bool SeqQueue:IsFull(void) if( (rear+1)%MaxSize=front) return 1; else return 0; /进队操作进队操作void SeqSeqQueue:Append(const Data& x) if (rear+

24、1)%MaxSize = front) cout队列已满队列已满,不能进队！不能进队！endl; exit(0); else qrear = x; rear = (rear+1)%MaxSize; /出队操作出队操作Data SeqQueue:DelQueue(void) if (IsEmpty() cout队列已空！队列已空！endl; exit(0); Data temp= qfront; front = (front+1)%MaxSize; return temp;/ 取队首元素取队首元素Data SeqQueue:GetFront() if(front = rear) cerr队列已空

25、！队列已空！endl; exit(0); else return qfront; /取队尾元素取队尾元素Data SeqQueue:GetRear() if(front = rear) cerr队列已空！队列已空！next; delete q; 四、队列的链式存储构造及实现四、队列的链式存储构造及实现 /进队操作进队操作:在链队列的末尾插入一个结点在链队列的末尾插入一个结点xvoid LinkQueue:Append(const Data& x) Node* p; p = new Node(x); rear-next = p; rear = p; count+;四、队列的链式存储构造及实现四、队列的链式存储构造及实现 /出队操作：删除头结点后面的结点出队操作：删除头结点后面的结点Data LinkQueue:Delete() Node *p; Data x; if (front = rear ) coutnext; x