栈和队列梁.ppt

《栈和队列梁.ppt》由会员分享，可在线阅读，更多相关《栈和队列梁.ppt（64页珍藏版）》请在三一文库上搜索。

1、第3章 堆栈和队列,主讲：梁宝兰,2,教学要求,三种特殊的线性表栈、队列、优先队列 掌握栈、队列、优先队列的相关概念； 掌握栈、队列、优先队列的顺序存储与链式存储结构 掌握栈和队列的应用，了解优先队列的应用,3,生活中的例子： 羊肉串 子弹夹 食堂吃饭队伍 银行柜台服务,引子,它们都是操作受限的线性表,4,3.1 堆栈,一、栈的基本概念 堆栈(Stack) ：限定仅在表的一端进行插入和删除操作的线性表。 栈顶(top):表的插入和删除端。 栈底(bottom)：表的另一端。 空栈：没有任何元素的栈。 特点：先进后出,top,入栈,出栈,5,a1,a2,a3,入栈,出栈,栈底/栈顶,插入：入栈、

2、进栈、压栈 删除：出栈、弹栈,栈的示意图,3.1 堆栈,6,栈的操作特性：后进先出,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈 删除：出栈、弹栈,栈的示意图,3.1 堆栈,7,例3-1：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,a,b,c,情况1：,3.1 堆栈,8,a,b,c,出栈序列：c,出栈序列：c、b,出栈序列：c、b、a,情况1：,3.1 堆栈,例3-1：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,9,a,b,出栈序列：b,情况2：,3.1 堆栈,例3-1：有三个元素按a、b、

3、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,10,a,出栈序列：b,出栈序列：b、c,出栈序列： b、 c、a,c,注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。,情况2：,3.1 堆栈,例3-1：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,11,ADT Stack Data 栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系 Operation InitStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈,3.1.2 栈的抽象

4、数据类型,12,DestroyStack 前置条件：栈已存在 输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素,13,Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变,14,Empty 前置条件：栈已存在

5、 输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endADT,15,3.1.3 顺序堆栈类,顺序栈栈的顺序存储结构,如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,附设指针top指示栈顶元素在数组中的位置。,16,出栈：top减1,进栈：top加1,栈空：top= 0 不能出栈 栈满：top= MAX_SIZE 不能进栈,a1,a2,a3,3.1.3 顺序堆栈类,17,/顺序栈类的实现 const int Max=100; typedef char Data; class SeqStack private: int MaxSize

6、; int top; Data *s; /栈动态数组指针 public: SeqStack(int max); /构造函数 void ClearStack(void); /清空栈 void Push(const Data,3.1.3 顺序堆栈类,18,/顺序栈的实现 SeqStack: SeqStack (int max) /构造函数 s = new Data max; MaxSize = max; top = 0; /指向栈中最后一个元素后一个元素 ,3.1.3 顺序堆栈类,19,3.1.3 顺序堆栈类,/顺序栈的实现 bool SeqStack IsEmpty() /判断是否空 retur

7、n top =0; bool SeqStack :IsFull() /判断是否满 return top = MaxSize ; ,20,3.1.3 顺序堆栈类,/顺序栈的实现 Data SeqStack : GetTop() const /取栈顶元素 if(top=0) cout“栈为空”endl; exit(0); return stop-1; ,21,3.1.3 顺序堆栈类,/顺序栈的实现 void SeqStack :Push(const Data /top指示上一个存储单元 ,22,3.1.3 顺序堆栈类,/顺序栈的实现 Data SeqStack :Pop(void) Data te

8、mp; if (top = = 0) /判断栈是否为空 cout“栈已空!“endl; exit(0); top- -; /调整栈顶指示器指向下一个存储单元 temp = stop; /将栈顶元素保存在temp中 return temp; /返回原来栈顶元素 ,23,回文判断（程序示例） 算法思想：将一个串s的字符依次压入栈中，然后逐步将栈中元素弹出栈，并将出栈元素放入一个新串t中。如果s和t相等，则s是一个回文串。,顺序栈应用,源程序,24,3.1.4 链式堆栈类,链栈：栈的链接存储结构,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？（线性表的头还是尾？） 链栈需要加头结点吗？,25,定

9、义结点类 class StackNode friend class LinkStack; private: Data data; StackNode * next; public: StackNode() next = NULL; StackNode(const Data,3.1.4 链式堆栈类,26,定义结点类 class LinkStack private: StackNode * top; int size； public: LinkStack(); /构造函数 LinkStack(); /析构函数 void Push(const Data,3.1.4 链式堆栈类,27,3.1.4 链式

10、堆栈类,/链式堆栈类实现 LinkStack:LinkStack() /构造函数 top = new StackNode(); /创建头结点 bool LinkStack:IsEmpty() if ( top-next = = NULL) return 1; else return 0; ,28,/析构函数 LinkStack:LinkStack() StackNode *p,*q; p = top; while (p!=NULL) q = p; p = p-next; delete q; ,3.1.4 链式堆栈类,29,/压栈操作：在链栈的头结点后面插入一个结点 void LinkStack

11、:Push(const Data ,3.1.4 链式堆栈类,30,/出栈操作：删除链栈头结点后面的一个结点 Data LinkStack:Pop() Data x; StackNode *p = top-next; if (p = = NULL) coutnext = p-next; x = p-data; delete p; return x; ,3.1.4 链式堆栈类,31,*思考题,假设采用不带头结点的单链表实现栈，有关栈的操作如何调整？（包括构造函数、压栈、出栈、判空等操作），你认为这种做法好吗？,32,数制转换 /把一个长整型数num转换为一个r进制数输出,3.2 堆栈应用,实现算法

12、思想：把num不断地除以r取余数，并把余数压栈，然后取商除以r取余，并把余数压栈；直到商为0；把栈中的数弹栈输出。,数制转换思想：把num不断地除以r取余数，然后取商除以r取余，直到商为0；把余数出现的次序，从后到先进行排列，即为相应的r进制数,源程序,33,string DecToBin(int n) SeqStack stk; string 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

13、; ,34,括号匹配问题 三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序嵌套使用，但不可交叉。 例：匹配： ( ( ) ) 不匹配：,3.2 堆栈应用,怎样判断是否匹配？,利用栈进行表达式中的括号匹配 自左至右扫描表达式，若遇左括号则将该左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈。,源程序,35,3.3 队列,一、队列的基本概念 队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。 空队列：不含任何数据元素的队列。 队头：允许删除（也称出队）的一端。 队尾：允许插入（也称入队、进队）的一端。,（a1, a2,

14、, an）,36,队列的操作特性：先进先出,a1,a2,a3,入队,队尾,队头,出队,队头,二、队列的逻辑结构,3.3 队列,37,三、队列的顺序存储结构及实现,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能为O(1),3.3 队列,front指向队列存储空间的第一个元素 rear指向队列数据元素的最后一个元素的下一个元素,38,例：a1a2依次出队,a1,a2,a3,a4,出队操作时间性能为O(1),三、队列的顺序存储结构及实现,3.3 队列,队列的移动有什么特点？ 单向移动性：整个队列向数组下标较大方向移动,39,假溢出：当元素被插入到数组中下标最大的位置上之后，队

15、列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,a3,a4,a5,三、队列的顺序存储结构及实现,3.3 队列,40,循环队列：将存储队列的数组头尾相接。 rear=rear+1 改为 rear= (rear+1) % MaxSize front=front+1 改为 front= (front+1) % MaxSize,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,三、队列的顺序存储结构及实现,3.3 队列,41,三、队列的顺序存储结构及实现,3.3 队列,A,B,C,D,E,F,front,rear,A,0,1,2

16、,543210,B,C,D,E,F,3,4,5,队空：front=rear 队满：front=rear,怎样区分队空和队满,42,方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=MaxSize时为队满； 方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元； 队满的条件：(rear+1) %MaxSize=front 队空的条件：rear=front 方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。,区分队空与队满的方法：,三、队列的顺序存储结构及实现,3.3 队列,43,循环队

17、列类的定义 class SeqQueue private: Data *q; int front,rear; int count; int MaxSize; public: SeqQueue(); /构造函数 void Clear(void); /清空队列 void Append(const Data,44,/初始化操作 SeqQueue:SeqQueue() q=new DataMaxSize; front = 0; rear = 0; count=0; ,/ 队列清空操作 void SeqQueue:Clear(void) rear = front; count=0; ,45,/判空、判满

18、操作 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; ,46,/进队操作 void SeqSeqQueue:Append(const Data ,47,/出队操作 Data SeqQueue:DelQueue(void) if (IsEmpty() cout“队列已空！“endl; exit(0); Data temp= qfront; front

19、= (front+1)%MaxSize; return temp; ,48,/ 取队首元素 Data SeqQueue:GetFront() if(front = rear) cerr“队列已空！“endl; exit(0); else return qfront; ,49,/取队尾元素 Data SeqQueue:GetRear() if(front = rear) cerr“队列已空！“endl; exit(0); else return q(rear-1)%MaxSize; ,50,思考,假设采用一个标记量tag来区分循环队列是空是满，则循环队列类又如何实现？ 假设通过记录队列中元素数c

20、ount来确定是循环队列时队空还是队满，则循环队列类又如何实现？,Template实现,51,四、队列的链式存储结构及实现,3.3 队列,如何改造单链表实现队列的链接存储？ 哪边是队首，哪边是队尾,队头指针即为链表的头指针,52,/定义结点类 class Node private: Data data; Node* next; public: Node() next = NULL; Node(Data x) data = x; next = NULL; friend class LinkQueue; ;,四、队列的链式存储结构及实现,53,/定义结点类 class LinkQueue /定义链

21、队列 类的界面 private: Node* front; Node* rear; int count; public: LinkQueue(); /构造函数 LinkQueue(); /析构函数 void Append(const Data,四、队列的链式存储结构及实现,54,/构造函数 LinkQueue:LinkQueue( ) front = new Node(); rear = front; count = 0; ,四、队列的链式存储结构及实现,55,/析构函数 LinkQueue:LinkQueue( ) Node *p,*q; p = front; while (p!=NULL)

22、 q = p; p = p-next; delete q; ,四、队列的链式存储结构及实现,56,/进队操作:在链队列的末尾插入一个结点x void LinkQueue:Append(const Data ,四、队列的链式存储结构及实现,57,/出队操作：删除头结点后面的结点 Data LinkQueue:Delete() Node *p; Data x; if (front = rear ) coutnext; x = p-data; front-next = p-next; if(p-next = NULL) rear = front; /队列已空 delete p; count-; re

23、turn x; ,四、队列的链式存储结构及实现,58,思考题,链队列的判空操作、取队头元素、取队尾元素等操作如何实现？,Template实现,59,六、队列的应用 队列往往起到一个缓冲的作用 CPU资源的竞争问题。 主机与外部设备之间速度不匹配的问题。 舞伴问题 (两资源数量不等的队列匹配问题),女：,男：,60,优先级队列,优先级队列：每次从队列中取出的是具有最高优先权的元素，同等优先级，则按照先进先出的原则出队列。 应用例子：操作系统的进程管理,源程序,61,本章小结,本章主要讲述了操作(插入、删除)受限的线性表，即插入和删除在同一端的堆栈和插入和删除不在同一端的队列。着重讲述了堆栈/队列的相关概念、定义、运算及其在顺序和链式2种不同存储方式下的实现方法和应用。这些要达到熟悉掌握的程度，同时要理解优先级队列并能进行初步的应用。,62,作 业,P87第2、3、6、7题,63,实验练习,P88第15、16、17题。,64,课外阅读,1、什么是共享堆栈(即双端堆栈)？ 2、了解表达式文法。 3、了解算符优先文法。,