1、1、栈2、队列3、优先队列4、栈和队列的应用第三章第三章 栈和队列栈和队列 栈的定义栈的定义限定只能在表尾端进行插入和删除的线性表。限定只能在表尾端进行插入和删除的线性表。栈顶：表尾端被称之为栈顶。栈顶：表尾端被称之为栈顶。栈底：和表尾相对应的另一端，称之为栈底。栈底：和表尾相对应的另一端，称之为栈底。时间有序表：时间有序表：LIFO 特征的线性结构。特征的线性结构。AB初态初态AB出栈出栈ABCC进栈进栈栈的栈的 ADT(Abstract Data Type)template class AbsStack public:AbsStack()/默认构造函数virtual AbsStack()/
2、析构函数virtual int IsEmpty()const=0;/判栈空吗？virtual int IsFull()const=0;/判栈满吗？virtual void MakeEmpty()=0;/将栈清空。virtual void Push(const ElemType&X)=0;/新结点进栈。virtual void Pop()=0;/栈顶结点出栈。virtual const ElemType&Top()const=0;/取栈顶结点数据值。private:AbsStack(const AbsStack&)/冻结复制另一堆栈的构造函数。；顺序表示的堆栈顺序表示的堆栈top空栈空栈top=
3、-1 是栈空标志是栈空标志stacksize=4 topAtopABABCtoptopABCD注意注意：因为因为 top=-1是栈空标志，所以是栈空标志，所以 top 指针指示真正的栈顶元素的下指针指示真正的栈顶元素的下标地址。标地址。栈满时的处理方法：栈满时的处理方法：1、报错。返回操作系统。、报错。返回操作系统。2、分配更大的空间，作为栈的存、分配更大的空间，作为栈的存储空间。将储空间。将 原栈的内容移入新栈。原栈的内容移入新栈。3120顺序表示的堆栈的实现顺序表示的堆栈的实现static const int InitStackSize=10;template class Stack:pu
4、blic AbsStack private:ElemType*Array;/存放结点的数组名。存放结点的数组名。int top;/top-栈顶指针。栈顶指针。int MaxSize;/栈内能够存放结点的最大个数，即栈的容量。栈内能够存放结点的最大个数，即栈的容量。void DoubleArray(int Max);/更新数组的容量。更新数组的容量。public:Stack();/构造函数构造函数,初始时构造大小为初始时构造大小为InitStackSize的栈。的栈。Stack()delete Array;/析构函数，释放占用的连续空间。析构函数，释放占用的连续空间。void MakeEmpty
5、()top=-1;/将栈清空。将栈清空。int IsEmpty()const return top=-1;/栈空为栈空为True,否则为否则为False。int IsFull()const return top=MaxSize-1;/栈满为栈满为True,否则为否则为False。const ElemType&Top()const;/读取栈顶结点。读取栈顶结点。void Push(const ElemType&X);/将将X的值进栈。的值进栈。void Pop();/栈顶结点出栈。栈顶结点出栈。const Stack&operator=(const Stack&R);；顺序表示的堆栈的实现顺序表
6、示的堆栈的实现template Stack:Stack():top(-1),MaxSize(InitStackSize)/构造函数构造函数,空间大小为空间大小为MaxSize Array=new ElemTypeMaxSize;template const ElemType&Stack:Top()const/对非空栈，读取栈顶结点并返回结点的值。对非空栈，读取栈顶结点并返回结点的值。Exception(IsEmpty(),”Underflow:Satck is Empty!”);return Arraytop;template void Stack:Push(const ElemType&X)
7、if (top+1=MaxSize)DoubleArray(2*MaxSize);Array+top=X;/新结点放入新的栈顶位置。新结点放入新的栈顶位置。template void Stack:Pop()/对非空栈对非空栈,将栈顶结点出栈将栈顶结点出栈Exception(IsEmpty(),”Stack is underflow!”);top-;顺序表示的堆栈的实现顺序表示的堆栈的实现template const Stack&Stack:operator=(const Stack&R)if(this=&R)return*this;delete Array;Array=new ElemType
8、R.MaxSize;/分配存储单元。分配存储单元。top=R.top;for(int j=0;j=top;j+)Arrayj=R.Arrayj;/逐个复制结点。逐个复制结点。return*this;template void Stack:DoubleArray(int Max)ElemType*oldarr=Array;Exception(MaxSizeMax,“New size is too small!”);Array=new ElemTypeMax;for(int k=0;k=top;k+)Arrayk=oldarrk;/逐个复制结点。逐个复制结点。MaxSize=Max;delete
9、oldarr;return;多栈共享一块顺序存储空间多栈共享一块顺序存储空间 栈顶指针指向实际栈顶的下一个单元。栈顶指针指向实际栈顶的下一个单元。二个栈共享一块顺序存储空间二个栈共享一块顺序存储空间栈顶指针指向实际栈顶的下一个单元。指针相遇时，栈满。栈顶指针指向实际栈顶的下一个单元。指针相遇时，栈满。链接表示的栈链接表示的栈 top 是栈顶指针。栈顶和栈底如图所示。是栈顶指针。栈顶和栈底如图所示。Element Next 栈顶栈顶栈底栈底toptop初始化初始化栈底栈底 栈顶栈顶top Element Next链接表示的栈链接表示的栈(ADT)template class Stack:publ
10、ic AbsStack private:ListNode*top;/top 栈顶指针。栈顶指针。public:Stack():top(NULL)/构造函数构造函数:栈顶指针初始化。栈顶指针初始化。Stack()MakeEmpty();/析构函数，释放占用的连续空间。析构函数，释放占用的连续空间。void MakeEmpty();/将栈清空。将栈清空。int IsEmpty()const return top=NULL;/栈空为栈空为True,否则为否则为False。int IsFull()const return 0;/总认为栈不会满。总认为栈不会满。const ElemType&Top()c
11、onst;/读取栈顶结点。读取栈顶结点。void Push(const ElemType&X);/将将X的值进栈。的值进栈。void Pop();/栈顶结点出栈。栈顶结点出栈。const Stack&operator=(const Stack&R);；进栈操作进栈操作 链接表示的栈的链接表示的栈的 Push 操作：操作：栈顶栈顶 栈底栈底toptoptemplate void Stack:Push(const ElemType&X)top=new ListNode(X,top);Element Next Element Next Element NextX进栈操作进栈操作 链接表示的栈的链接表
12、示的栈的 Push 操作：操作：栈顶栈顶 栈底栈底toptoptemplate void Stack:Push(const ElemType&X)top=new ListNode(X,top);Element Next Element Next Element NextX出栈操作出栈操作 链接表示的栈的链接表示的栈的 Pop 操作：操作：栈顶栈顶 栈底栈底toptoptemplate void Stack:Pop()/对非空栈，将栈顶结点出栈。对非空栈，将栈顶结点出栈。Exception(IsEmpty(),”Stack is underflow!”);ListNode*q=top;top=t
13、op-Next;delete q;Element Next Element Next Element Nextq出栈操作出栈操作 链接表示的栈的链接表示的栈的 Pop 操作：操作：栈顶栈顶 栈底栈底toptop Element Next Element Next Element Nexttemplate void Stack:Pop()/对非空栈，将栈顶结点出栈。对非空栈，将栈顶结点出栈。Exception(IsEmpty(),”Stack is underflow!”);ListNode*q=top;top=top-Next;delete q;q出栈操作出栈操作 链接表示的栈的链接表示的栈的
14、 Pop 操作：操作：栈顶栈顶 栈底栈底toptop Element Next Element Nexttemplate void Stack:Pop()/对非空栈，将栈顶结点出栈。对非空栈，将栈顶结点出栈。Exception(IsEmpty(),”Stack is underflow!”);ListNode*q=top;top=top-Next;delete q;队列的定义队列的定义在表的一端进行插入，而在另一端进行删除的线性表。在表的一端进行插入，而在另一端进行删除的线性表。队尾：进行插入的一端。队尾：进行插入的一端。队首：进行删除的一端。队首：进行删除的一端。时间有序表：时间有序表：FI
15、FO 特征的线性结构特征的线性结构。a1，a2，a3，a4，a5，a6，a7，a8，a9，a10进队进队出队出队队首队首队尾队尾队列的队列的ADTtemplate class AbsQueue public:AbsQueue()/默认构造函数virtual AbsQueue()/析构函数virtual int IsEmpty()const=0;/判队空吗？virtual int IsFull()const=0;/判队满吗？virtual void MakeEmpty()=0;/将队清空。virtual void EnQueue(const ElemType&X)=0;/新结点进队。virtua
16、l void DeQueue()=0;/队首结点出队。virtual const ElemType&Front()const=0;/取队首结点数据值。private:AbsQueue(const AbsQueue&)/冻结复制另一队列的构造函数。；顺序表示的队列顺序表示的队列 循环队列循环队列 frontrearmaxSize=4 front=rear 是队空标志是队空标志AABABCrear 当当 A 进队时，如仍设队首指针进队时，如仍设队首指针 front 和队尾指针和队尾指针 rear 指向真正的队指向真正的队首和队尾，则首和队尾，则 front=rear和队空标志矛盾。和队空标志矛盾。
17、因此，使因此，使 front 指向真正的队首指向真正的队首,rear指向真正队尾指向真正队尾的后一单元，是一的后一单元，是一种解决方案种解决方案。Arearfrontrearfrontrearfront3120front顺序表示的队列顺序表示的队列空队空队maxSize=4 front=rear 是队空标志是队空标志当当 A 进队时，如仍设队首指进队时，如仍设队首指针针 front 和队尾指针和队尾指针 rear 指指向真正的队首和队尾，则向真正的队首和队尾，则 front=rear和队空标志矛盾。和队空标志矛盾。因此，使因此，使 front 指向真正指向真正的队首的队首的前一结点的前一结点而
18、而 rear指指向真正队尾向真正队尾(其它方案？其它方案？)。当当 D 进队时，进队时，队尾指针队尾指针 rear 要指向真正的队尾的后要指向真正的队尾的后1单元单元，由于此时，由于此时 0 号单元已可以号单元已可以使用，所以使用，所以 rear=0这就是所谓循环队列。认为具这就是所谓循环队列。认为具有最大下标的单元后面是最小有最大下标的单元后面是最小下标的单元。下标的单元。ABCrearfrontABCrearfrontABCrearfrontABCrearfrontD顺序表示的队列顺序表示的队列空队空队maxSize=4 front=rear 是队空标志是队空标志当当 A 进队时，如仍设队
19、首指进队时，如仍设队首指针针 front 和队尾指针和队尾指针 rear 指指向真正的队首和队尾，则向真正的队首和队尾，则 front=rear和队空标志矛盾。和队空标志矛盾。因此，使因此，使 front 指向真正指向真正的队首的队首的前一结点的前一结点而而 rear指指向真正队尾向真正队尾(其它方案？其它方案？)。当当 D 进队时，进队时，队尾指针队尾指针 rear 指向真正的队尾，由于指向真正的队尾，由于此时此时 0 号单元已可以使用，号单元已可以使用，所以所以 rear=0这就是所谓循环队列。认为具这就是所谓循环队列。认为具有最大下标的单元后面是最小有最大下标的单元后面是最小下标的单元。
20、下标的单元。ABCrearfrontABCrearfrontABCrearfrontABCrearfrontD顺序表示的队列顺序表示的队列 出队时应先判队是否空：条件出队时应先判队是否空：条件 rear=front 不空则出队，注意不空则出队，注意 front 是否会由最高下标跳是否会由最高下标跳 至最低下标至最低下标(循环循环)。进队时应先判队是否满：条件进队时应先判队是否满：条件 (rear+1)%maxSize)=front 不满则进队，注意不满则进队，注意 rear 是否会由最高下标跳是否会由最高下标跳 至最低下标至最低下标(循环循环)。基本操作的实现基本操作的实现:进队进队Crear
21、frontDECrearfrontDECrearfront3120再进队满再进队满再进队循环、满再进队循环、满再进队循环、不满再进队循环、不满template void Queue:EnQueue(const ElemType&x)/值为值为x的结点进队。的结点进队。if(IsFull()DoubleQueue();Arrayrear=x;/若队满，则数组容量扩大一倍。若队满，则数组容量扩大一倍。Increment(rear);/rear 加加 1;若为若为 MaxSize，则，则rear取取0。int IsFull()const return(rear+1)%MaxSize=front;Cr
22、earfront再进队、不满再进队、不满D基本操作的实现基本操作的实现:进队进队基本操作进队的实现程序：扩大数组容量，基本操作进队的实现程序：扩大数组容量，“分期付款式分期付款式”内存使用法。内存使用法。template void Queue:EnQueue(const ElemType&x)/值为值为x的结点进队。的结点进队。if(IsFull()DoubleQueue();Arrayrear=x;Increment(rear);template void Queue:DoubleQueue()/重新创建数组单元个数多一倍的新数组，复制原队列中的结点。重新创建数组单元个数多一倍的新数组，复制
23、原队列中的结点。int NewSize=2*MaxSize;ElemType*old=Array;Array=new ElemTypeNewSize;for(int j=0,k=front;k rear;j+,Increment(k)Arrayj=oldk;front=0;/新的队首指针。新的队首指针。rear=j;/新的队尾指针。新的队尾指针。MaxSize=NewSize;delete old;CrearfrontDE3120CDF要进队要进队满！满！Efrontrear基本操作的实现基本操作的实现:出队出队template void Queue:DeQueue()/对于非空队列，将队首结
24、点出队。对于非空队列，将队首结点出队。Exception(IsEmpty(),”Queue is underflow!”);Increment(front);int IsEmpty()const return front=rear;/判断队列是否空判断队列是否空.。为空返回。为空返回True,否则返回否则返回False。链接表示的队列链接表示的队列 参照参照下下图所示。其中图所示。其中 front 和和 rear 分别是队首和队尾指针。分别是队首和队尾指针。它们指示着它们指示着真正的真正的队首和队首和真正的真正的队尾结点。队尾结点。Element Next 队首结点队首结点front 队尾结点
25、队尾结点rear链接表示的队列链接表示的队列 初始化：初始化：队尾结点队尾结点(队首结点队首结点)rear 队首结点队首结点 队尾结点队尾结点rearfrontfrontfront=rear=NULL链接表示的队列链接表示的队列 链接表示的队列：链接表示的队列：front、rear 分别是队列的队首和对尾指针。分别是队列的队首和对尾指针。template class Queue:public AbsQueue private:ListNode*front;/队首指针。ListNode*rear;/队尾指针。public:Queue():front(NULL),rear(NULL)/构造函数:队
26、首指针和队尾指针初始化。Queue()MakeEmpty();/析构函数，释放占用的连续空间。void MakeEmpty();/将队列清空。int IsEmpty()const return front=NULL;/队空为True,否则为False。int IsFull()const return 0;/总认为为False。const ElemType&Front()const;/读取队首结点数据值。void EnQueue(const ElemType&X);/将X的值进队。void DeQueue();/将队首结点出队。const Queue&operator=(const Queue&
27、R);；基本操作的实现基本操作的实现:进队进队 链接表示的队列：进队操作，链接表示的队列：进队操作，front、rear 分别是队列的队首和对尾指针。分别是队列的队首和对尾指针。frontreartemplate void Queue:EnQueue(const ElemType&X)if(IsEmpty()front=rear=new ListNode (X);else rear=rear-Next=new ListNode(X);front初始化初始化rearfrontrearXNULL优先队列优先队列优先权有序表优先权有序表：具有：具有特征高优先权的结点将先离开的线性结构。和到达时刻无关
28、。特征高优先权的结点将先离开的线性结构。和到达时刻无关。实现方法：结点实现方法：结点中除包含数据场外，还有本结点的优先权数。中除包含数据场外，还有本结点的优先权数。优先权数越小（如课本）优先权数越小（如课本），优先级越高。或者：，优先级越高。或者：优先权数越大，优先级越高。优先权数越大，优先级越高。419312056顺序存储的优先队列顺序存储的优先队列用数组：队空：用数组：队空：front=rear=0;队满：队满：rear=MaxSize-1c.具有最高优先数具有最高优先数15的结点出队。用最后一个结点覆盖它。的结点出队。用最后一个结点覆盖它。fronta.具有优先数为具有优先数为20、15
29、、30、19的结点依次进队之后。的结点依次进队之后。302015 frontrearb.具有优先数为具有优先数为26、24的结点依次进队后。的结点依次进队后。193020152426 frontrear193020 frontrear302024242626 d.剩余结点中剩余结点中具有最高优先数为具有最高优先数为1919的结点出队之后，用最后一个结点结点覆盖它之后。的结点出队之后，用最后一个结点结点覆盖它之后。19rear进队时到进队时到队尾去排队尾去排队。队。出队时必出队时必须进行查须进行查找，然后找，然后用最后一用最后一个结点覆个结点覆盖刚刚出盖刚刚出队的结点队的结点，代价为，代价为O（
30、n）。）。栈的应用：数制转换栈的应用：数制转换 例如：例如：10 进制和进制和 8 进制之间的数的转换。进制之间的数的转换。(1348)10 =83*a3+82*a2+8*a1+80*a0 /两边同除以两边同除以 8 168 余余 4 =(82*a3+81*a2+a1)余余 4 即即 a0 4 168 =82*a3+81*a2+a1 /两边同除以两边同除以 8 21 余余 0 =(8*a3+a2 )余余 0 即即 a1 0 21 =8*a3+a2 /两边同除以两边同除以 8 2 余余 5 =(a3 )余余 5 即即 a2 5 a3 2 4052 数制转换：数制转换：栈的应用：数制转换栈的应用：
31、数制转换 数制转换：数制转换：顺便提一句，顺便提一句，10 进制小数如何变成进制小数如何变成 2 进制小数：进制小数：例如：例如：(0.4)10 =(?)2 0.4 2 =0.8 (0.0)2 0.8 2 =1.6 (0.01)2 0.6 2 =1.2 (0.011)2 栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*372-35*15 解：解：(*/+-)#/#为表达式结束标志，即书上的为表达式结束标志，即书上的
32、EOL 符号。符号。栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如
33、中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack
34、 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：
35、解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器
36、的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(3.7.如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.栈的应用：简单计算器栈的应
37、用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(-如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(-如中缀式：如中缀式：3 (7-2)相应的后
38、缀式：相应的后缀式：3.7.2.-.*3.7.2.栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(-如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行
39、过程：执行过程：#3 (7-2)#(-)如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#(-)如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值
40、；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#()如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#()如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算
41、器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后
42、缀式：3.7.2.-.*3.7.2.-栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过程：#3 (7-2)#如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-*栈的应用：简单计算器栈的应用：简单计算器简单计算器的实现：重点为计算表达式的值；如：简单计算器的实现：重点为计算表达式的值；如：x=3 (7-2)。解：解：(*/+-)#。运算符栈运算符栈 OpStack 执行过程：执行过
43、程：#3 (7-2)#算法：算法：1.将将#压入到运算符栈压入到运算符栈 OpStack。2 扫描中遇到操作数，将操作数压入到操作数扫描中遇到操作数，将操作数压入到操作数 栈栈 PostFixStack。3.遇到遇到(时立刻强制进时立刻强制进 OpStack 栈。遇到运算栈。遇到运算符时，在同一符时，在同一()表达式中（在主表达式中，同表达式中（在主表达式中，同样这样处理），运算符进栈时，必须保持栈顶的样这样处理），运算符进栈时，必须保持栈顶的运算符的优先级最高，否则应将运算符的优先级最高，否则应将OpStack 栈中栈中的的运算符自运算符自 OpStack 栈中弹出，并使得操作数栈中弹出，并
44、使得操作数栈栈 PostFixStack 中的二个处于栈顶的操作数完中的二个处于栈顶的操作数完成该运算符相应的运算。如此反复执行，成该运算符相应的运算。如此反复执行，直至运直至运算符栈算符栈 OpStack 中的栈顶算符的优先级最高为中的栈顶算符的优先级最高为止。止。4.遇到，将运算符栈遇到，将运算符栈 OpStack中运算符依次中运算符依次弹出，弹出，并使得操作数栈并使得操作数栈 PostFixStack 中的二个中的二个处于栈顶的操作数完成该运算符相应的运算。如处于栈顶的操作数完成该运算符相应的运算。如此反复执行，此反复执行，直至遇到运算符栈直至遇到运算符栈 OpStack 中的中的另一号
45、为止。另一号为止。如中缀式：如中缀式：3 (7-2)相应的后缀式：相应的后缀式：3.7.2.-.*3.7.2.-*栈的应用：简单计算器栈的应用：简单计算器实现时的考虑：将所有的算符，都看作为运算符，并且都赋给一定的优先数，优先数实现时的考虑：将所有的算符，都看作为运算符，并且都赋给一定的优先数，优先数 越大，那么该运算符的优先级就越高。当然必须遵守运算符关于优先级的约定。越大，那么该运算符的优先级就越高。当然必须遵守运算符关于优先级的约定。运算符优先数的约定运算符优先数的约定#(/)栈内优先数栈内优先数（左方）（左方）如果表达式转换为后缀表达式，计算将非常简单。但本实例中，不给出后缀表达式的如
46、果表达式转换为后缀表达式，计算将非常简单。但本实例中，不给出后缀表达式的 形式，而直接进行运算，得出结果。形式，而直接进行运算，得出结果。1、3 (7-2)#3 (7-2)#3 72 2、AB(CD)E/F#AB(CD)E/F#ABCDEF/-运算符运算符栈外优先数栈外优先数（右方）（右方）0 100 3 1 0 6-1 0 4 2 99 5Josephus问题问题Josephus问题问题是一个游戏。是一个游戏。N个人坐成环状队列，其编号为个人坐成环状队列，其编号为1到到N。从编。从编号为号为1 的人开始，的人开始，传递一只烫手的土豆。在经过传递一只烫手的土豆。在经过M(如：如：M2)次传递之
47、后，持有土豆的人将离开这个环，而次传递之后，持有土豆的人将离开这个环，而将土豆交给他的下一个人。然后，游戏重新开始。又经过了将土豆交给他的下一个人。然后，游戏重新开始。又经过了M 次传递之后，又将有一个人次传递之后，又将有一个人离开这个环，它同样将土豆交给他的下一个人。如此，循环，直至最后剩下一个人为止，离开这个环，它同样将土豆交给他的下一个人。如此，循环，直至最后剩下一个人为止，这个人就是最后的胜者。参照下图，这个人就是最后的胜者。参照下图，N6，M2的情况。的情况。1234561245612451251511、初态2、3号删除之后。3、6号删除之后。4、4号删除之后。5、2号删除之后。6、
48、5号删除后，1号为最终胜者 Josephus问题问题 Josephus 问题求解时，最自然的想到的数据结构是采用循环链表，但是我们这里采用的是单链问题求解时，最自然的想到的数据结构是采用循环链表，但是我们这里采用的是单链 表，同样完成了求解任务。注意到，尾结点的下一个结点是首结点即可。表，同样完成了求解任务。注意到，尾结点的下一个结点是首结点即可。程序程序3.11:Josephus 问题的解法。问题的解法。#include“List.h”int Josephus(int People,int Passes)List L;ListItr P(L);int k;for(k=1;k=People;k
49、+)P.Insert(k);/构造单链表，用于表示人的环状队列。构造单链表，用于表示人的环状队列。while(People-!=1)/当只剩下一个人时，即得到了最后的胜者。当只剩下一个人时，即得到了最后的胜者。for(k=0;k Passes;k+)/前进前进Passes步后，停在被删结点之前。步后，停在被删结点之前。P+;if(!+P)P.First();/若掠过尾结点，则为空，调整为单链表首结点。若掠过尾结点，则为空，调整为单链表首结点。if(!P.RemoveNext()/删除下一个结点，若当前结点是尾结点，则删除下一个结点，若当前结点是尾结点，则 P.Zeroth();/设置当前结点为头结点。设置当前结点为头结点。P.RemoveNext();/删除首结点。删除首结点。P.First();/设置当前结点为首结点。设置当前结点为首结点。return P();/返回胜者返回胜者(即首结点即首结点)的编号的编号
