栈与队列 编程初级教程

1、栈与队列1栈的定义栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。如果多个元素依次进栈，则后进栈的元素必然先出栈，所以堆栈又称为后进先出（LIFO）表。堆栈设有一个栈顶指针标志栈顶位置。 栈示意图a1a3a2进栈出栈top2堆栈的主要操作有： 创建空栈。 进栈(push)操作: 在栈顶插入元素。 出栈(pop)操作: 在栈顶删除元素。 读栈顶元素: 只是读出栈顶元素，并不改变栈内元素。 3顺序栈#define STACKSIZE 100/堆栈最大可分配空间数量class SqStackpublic: ElemType dataSTACKSIZ

2、E; /存储元素的数组 int top; /栈顶指针，存储栈顶元素的下标 SqStack() top=-1; /构造函数 void Push(ElemType x);/入栈操作 void Pop(ElemType &result);/出栈操作 void GetTop(ElemType &result);/取栈顶元素;一般将数组的0下标单元作为栈底，将栈顶元素的下标存储在栈顶指针top中，它随着元素进栈出栈而变化。top为-1表示空栈，top等于stacksize-1则表示栈满。 哈罗小说网4（1）进栈操作若栈不满，则在栈顶插入元素x作为新的栈顶。void SqStack:Push(ElemTy

3、pe x)if( top stacksize-1) top+;datatop=x;else cout -1) result= datatop;top-; else cout -1) result= datatop;else coutdata=x;p-next=top;top=p;9（2）出栈操作若栈不空，则删除栈顶元素，用result返回其值。void LinkStack:Pop(ElemType &result);SNode *p;if(top!=NULL)result = top-data;p=top;top=top-next;delete p;10举例 : 后缀表达式求值假定表达式是由加

4、减乘除和数字构成。最简单的表达式为下列形式： (操作数S1)(运算符OP)(操作数S2) 三种不同的表示方法：前缀表示法 OPS1S2 例如6+3写成+63中缀表示法 OPS1S2 例如6+3写成63+后缀表示法 S1S2OP 例如6+3写成63+11同时，任何表达式都可分解为下列形式： (子表达式E1)(运算符OP)(子表达式E2)它的后缀表示法应写成：(E1的后缀表示)(E2的后缀表示)OP只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。例如： 2*(6+3) 2(6+3)* 263+*。 (注意：转化为后缀式后括号去掉)12中缀

5、式虽然容易理解，但在求值的时候利用前缀式或后缀式更为简单。用后缀式求值的算法为：首先设立一个堆栈，依此读取后缀式中的字符，若字符是数字，则进栈并继续读取，若字符是运算符（记为OP），则连续出栈两次得到数字S1和S2，计算表达式S1OPS2并将结果入栈，继续读取后缀式。当读到结束符时停止读操作，这时堆栈中只应该有一个数据，即结果数据。13例如后缀式263+*的计算过程为2、6、3依次入栈，读+号则令3和6依次出栈，计算6+3后将结果9入栈，读*号则令9和2依次出栈，计算2*9后将结果18入栈。这时18就是最终结果。【例2-3】假定表达式是由不超过四个实数进行四则运算构成的算式，要编写一个程序来求

6、解该算式的结果。 14中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。15步骤栈中元素 输出结果 说明1(（进栈2(1输出13( +1+进栈4( +1 2输出2

7、51 2 +退栈输出，退栈到（止6*1 2 +*进栈7* (1 2 +（进栈8* ( (1 2 +（进栈9* ( (1 2 + 8输出810* ( ( -1 2 + 8 - 进栈将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下：1611* ( ( -1 2 + 8 2输出212* (1 2 + 8 2 -退栈输出，退栈到（止13* ( /1 2 + 8 2 -/ 进栈14* ( / (1 2 + 8 2 -（ 进栈15* ( / (1 2 + 8 2 - 7输出716* ( / ( -1 2 + 8 2 - 7- 进栈17* (

8、/ ( -1 2 + 8 2 - 7 4输出418* ( /1 2 + 8 2 - 7 4 -退栈输出，退栈到（止19*1 2 + 8 2 - 7 4 - /退栈输出，退栈到（止201 2 + 8 2 - 7 4 - / * *退栈并输出17队列定义 队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。显然不论元素按何种顺序进入队列，也必然按这种顺序出队列，所以队列又称为先进先出（FIFO）表。队列有两个活动端，所以设置了对头和队尾两个位置指针。一般队头指针记作front，队尾指针记作rear。 abcfrontrear入队出队队

9、列示意图18循环队列队列顺序存储 顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。因此在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。 19为方便起见，这里规定队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置。这样，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。对空队列而言，可假定front和rear的值为-1 20假溢出ABCfrontrearfrontrear (a) ABC入队 (b) AB出队, DE入队 (c)队列假溢出队列假

10、溢出示意图CDEfrontrear 随着元素不断入队列、出队列，rear和front指针会不断向后移动（如图(b)所示），最终会指向数组的最大下标位置（如图(c)所示）。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。 21循环队列解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。循环队列的基本操作方式为：入队列时先执行rear=(rear+1)%M，再将新元素在rear指示位置加入；出队列时先执行front=(front+1)%M，再将下标为front的元素取出。 22为了将队空和对满的条件加以区分，一般不使用f

11、ront指针所指的位置。队空条件为front=rear队满条件为(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE (a)循环队列空 (b)非空循环队列 (c)循环队列满 循环队列示意图 23循环队列描述如下：#define MAXSIZE 100/队列最大可分配空间数量class SqQueuepublic: ElemType dataMAXSIZE;/ 存放元素的数组 int front; / 队头指针 int rear; / 队尾指针 void EnQueue(ElemType x)

12、; /入队操作 void DeQueue(ElemType &e); /出队操作 void GetHead(ElemType &e); /取队头元素;front和rear指针取值均为所指数组单元的下标。由于队头指针所指单元总是空的，length比实际能存储的元素多一。 24（1）入队操作若队列不满，则在队尾插入元素x作为新的队尾。void SqQueue:EnQueue(ElemType x) if(rear+1)% MAXSIZE= front) cout队列已满;else rear = (rear+1)%MAXSIZE;datarear=x; 常用算法 25（2）出队操作 若队列不空，则删

13、除队头元素并用e取回该元素的值。void SqQueue:DeQueue(ElemType &e) if(rear=front) cout队列已空;else front = (front +1)% MAXSIZE;e= datafront;26（3）取队头元素 若队列不空，则用e取回队头元素的值。void SqQueue:GetHead(ElemType &e)if(rear=front) coutnext=NULL; rear = front;/尾指针也指向头结点 int Length(); /求队列长度void EnQueue(ElemType x); /入队操作void DeQueue

14、(ElemType &e); /出队操作void GetHead(ElemType &e); /求队头元素;30（1）求队列的长度返回队列的元素个数，即队列的长度。 int LinkQueue:Length() QNode * p=front;int len=0;while(p!=rear)len+;p= p-next;return len;31（2）入队列操作 插入元素x为队列新的队尾元素。void LinkQueue:EnQueue(ElemType x) QNode *s=new QNode;/建立新结点s s-data = x; s-next =NULL; rear -next = s;/在队尾插入结点s rear = s;/修改队尾指针32（3）出队列操作若队列不空，则删除队头元素，用e返回其值。void LinkQueue:DeQueue (ElemType &e) QNode *p;if( front= rear) coutnext;e=p-data;front-next=p-next;if(rear=p) rear=front; delete p;删除最后一个元素时，需要修改尾指针，使其指向头结点33（4）取队头元素若队列不空，则用e返回队头元素；void L