栈与队列 编程初级教程.ppt

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

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

3、se cout”栈满”; ,（2）出栈操作 若栈不空，则删除栈顶元素，用result返回其值。 void SqStack:Pop(ElemType ,（3）取栈顶元素 若栈不空，则用result返回栈顶元素。 void SqStack:GetTop(ElemType ,链式栈,栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的单链表。 typedef struct node ElemType data; /数据域 struct node *next; / 指针域 SNode; class LinkStack public: SNode* top; /栈顶指针 LinkStack

4、() top=NULL; /构造函数 void Push(ElemType x);/入栈操作 void Pop(ElemType ,（1）进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。 void LinkStack:Push(ElemType x) SNode *p=new SNode; if(p!=NULL) p-data=x; p-next=top; top=p; ,（2）出栈操作 若栈不空，则删除栈顶元素，用result返回其值。 void LinkStack:Pop(ElemType ,举例 : 后缀表达式求值,假定表达式是由加减乘除和数字构成。最简单的表达式为下列形式： (操作

5、数S1)(运算符OP)(操作数S2) 三种不同的表示方法： 前缀表示法 OPS1S2 例如6+3写成+63 中缀表示法 OPS1S2 例如6+3写成63+ 后缀表示法 S1S2OP 例如6+3写成63+,同时，任何表达式都可分解为下列形式： (子表达式E1)(运算符OP)(子表达式E2) 它的后缀表示法应写成： (E1的后缀表示)(E2的后缀表示)OP 只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。 例如： 2*(6+3) 2(6+3)* 263+*。 (注意：转化为后缀式后括号去掉),中缀式虽然容易理解，但在求值的时候利用前缀式或

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

7、缀表达式,将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。,将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下：,队列定义,队列

8、是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。 显然不论元素按何种顺序进入队列，也必然按这种顺序出队列，所以队列又称为先进先出（FIFO）表。队列有两个活动端，所以设置了对头和队尾两个位置指针。一般队头指针记作front，队尾指针记作rear。,循环队列队列顺序存储,顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。 因此在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。,为方便起见，这里规定队头指针front指向队头元素

9、的前一个位置，队尾指针rear指向队尾元素所在位置。这样，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。 对空队列而言，可假定front和rear的值为-1,假溢出,随着元素不断入队列、出队列，rear和front指针会不断向后移动（如图(b)所示），最终会指向数组的最大下标位置（如图(c)所示）。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。,循环队列,解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。循环队列的基本操作方式为： 入队列时先执行rear=(rear+1)%M，再将新元素在rear

10、指示位置加入； 出队列时先执行front=(front+1)%M，再将下标为front的元素取出。,为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。 队空条件为front=rear 队满条件为(rear+1)%M=front,(a)循环队列空 (b)非空循环队列 (c)循环队列满 循环队列示意图,循环队列描述如下：,#define MAXSIZE 100/队列最大可分配空间数量 class SqQueue public: ElemType dataMAXSIZE;/ 存放元素的数组 int front; / 队头指针 int rear; / 队尾指针 void EnQueu

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

12、DeQueue(ElemType ,（3）取队头元素 若队列不空，则用e取回队头元素的值。 void SqQueue:GetHead(ElemType ,链队列队列链式存储,链队列实质上就是只能在头部删除元素、只能在尾部插入元素的单链表。 队头指针front就是单链表的头指针，队尾指针rear则是指向单链表最后一个结点的指针。,链队列的结点可定义如下： struct QNode ElemType data; struct QNode *next; ; 链队列有两个指针，因此可采用下面定义: class LinkQueue public: QNode *front;/ 队头指针 QNode *r

13、ear; / 队尾指针 ( 下页继续 ),( 接上页 ),LinkQueue() front = new QNode;/建立头结点 front-next=NULL; rear = front;/尾指针也指向头结点 int Length(); /求队列长度 void EnQueue(ElemType x); /入队操作 void DeQueue (ElemType ,（1）求队列的长度 返回队列的元素个数，即队列的长度。 int LinkQueue:Length() QNode * p=front; int len=0; while(p!=rear) len+; p= p-next; return len; ,（2）入队列操作 插入元素x为队列新的队尾元素。 void LinkQueue:EnQueue(ElemType x) QNode *s=new QNode;/建立新结点s s-data = x; s-next =NULL; rear -next = s;/在队尾插入结点s rear = s;/修改队尾指针 ,（3）出队列操作 若队列不空，则删除队头元素，用e返回其值。 void LinkQueue:DeQueue (ElemType 删除最后一个元素时，需要修改尾指针，使其指向头