第三章 堆栈与队列

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,3.,2006,第3章 堆栈与队列,21世纪高等院校规划教材,返回总目录,3.,2006,堆栈与队列,堆栈与队列的基本概念,堆栈的插入与删除,队列的插入与删除,循环队列,堆栈与队列的应用,如何计算后序表达式,3.,2006,堆栈与队列的基本概念,堆栈与队列是数据结构最基本的两个主题，它们的功能却是相,当强，用途相当广。,在计算机算法（,algorithms）,中，堆栈（,stack）,与队列,（,queue）,是常用到的数据结构。,堆栈：,是一有序表（,order list），,其插入（,insert）,和删除（,delete）,操,作都在同一端，此端通常称之为栈顶（,top）。,插入一元素于堆栈，,此操作称为入栈（,push），,与之相反的是从堆栈删除一元素；此操作,称为出栈（,pop）。,由于堆栈具有后进先出的特性，所以又称堆栈是,一种后进先出（,Last In First Out，LIFO）,列表。,队列：,也是属于线性表，与堆栈不同的是插入和删除不在同一端，删除的那,一端为队头（,front），,而插入的一端称为队尾（,rear）。,由于队列,具有先进先出（,First In First Out，FIFO）,的特性，因此也称队列,为先进先出列表。假若队列两端皆可做插入或删除的操作，则称之为,双端队列（,double-ended queue,deque,）。,3.,2006,堆栈与队列的示意图,(,a),堆栈,（,b）,队列,图3-1 堆栈与队列示意图,3.,2006,堆栈的插入与删除,堆栈的插入：,插入一个元素（,push an item,）,到堆栈，主要考虑会不会因为插入此元素而溢出（,overflow,），,亦即插入要考虑不可超出栈的最大容量。若没有超出，则先将,top,插入，再将元素填入,atop,中。,堆栈的删除：,从堆栈删除一个元素等于出栈（,pop,）,一个元素，此时必须注意堆栈是否为空，亦即,top,的值是否为,-1,，若不为空，表示堆栈有元素存在，此时，先将,atop,的元素移除，然后将,top,减,1,。,3.,2006,堆栈的插入示意图,插入元素,10,于堆栈如图,3-2,所示：,（,1,）,top,的起始值,（,2,）,top,加,1,（,3,）,再将元素（假设,10,）填入,图,3-2,插入,10,于堆栈的示意图,3.,2006,插入元素10于堆栈的程序段,void push(void),if(top=MAX-1)/*,当堆栈已满时，显示出错误信息,*/,printf,(The Stack is full n);,else,top+;,printf,(please enter an item to stack:);,scanf,(%d,3.,2006,从堆栈中删除元素40的示意图,如图,3-3,所示，从堆栈中删除元素,40,（,1,）堆栈初始状况,top,值为,3,（,2,）将,a3,，,即,40,删除,（,3,）将,top,减,1,图3-3 删除堆栈中的40,3.,2006,从堆栈中删除元素40的程序段,void pop(void),if(top 0),printf,(The stack is empty n);,else,printf,(pop%d from stack n,atop);,top-;,3.,2006,堆栈的插入和删除程序实例,/*file name:stack.c */,/*,使用堆栈处理数据,新增、删除、输出,*/,#,include,#include,#include,#define MAX 100,void push_f(void);/*,入栈函数,*/,void pop_f(void);/*,出栈函数,*/,void list_f(void);/*,输出函数,*/,char itemMAX20;,int,top=-1;,3.,2006,堆栈的插入和删除程序实例（续1）,void main(void),char option;,while(1),printf,(n*n);,printf,(insert(push)n);,printf,(delete(pop)n);,printf,(listn);,printf,(quitn);,printf,(*n);,printf,(Please enter your choice.);,option=,getche,();,switch(option),3.,2006,堆栈的插入和删除程序实例（续2）,case 1:,push_f();,break;,case 2:,pop_f();,break;,case 3:,list_f();,break;,case 4:,exit(0);,3.,2006,堆栈的插入和删除程序实例（续3）,void push_f(void),if(top=MAX-1)/*,当堆栈已满时，显示错误,*/,printf,(n,nStack,is full!n);,else,top+;,printf,(nn Please enter item to insert:);,gets(itemtop);,3.,2006,堆栈的插入和删除程序实例（续4）,void pop_f(void),if(top 0)/*,当堆栈没有数据存在时，则显示错误,*/,printf,(nn No item,stack is empty!n);,else,printf,(nn Item%s deletedn,itemtop);,top-;,3.,2006,堆栈的插入和删除程序实例（续5）,void list_f(void),int,count=0,i;,if(top 0),printf,(nn No item,stack is emptyn);,else,printf,(nn ITEMn);,printf,(-n);,for(i=0;i=rear,时，表示队列是空的。,上述队列是线性队列（,linear queue,），,表示方式为,Q(0,MAX-1),，,但此线性队列当,rear,到达,MAX-1,时，任何插入都是不允许的，因为上述插入片段程序打印出队列是满的信息，因此它没考虑队列的前面是否还有空的位子，（如图3-5所示）。,3.,2006,队列的插入与删除,示意图,图3-4 队列示意图,图3-5,rear,到达,MAX-1,时，进行插入元素所对应的队列图,3.,2006,队列的插入程序段,void,enqueue,(void),if(rear=MAX-1),printf,(The Queue is full n);,else,rear+;,printf,(please enter an item to queue:);,scanf,(%d,3.,2006,队列的删除程序段,删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当,front=rear,时，表示队列是空的，实现该功能的程序段如下：,void,dequeue,(void),if(front=rear),printf,(The queue is Empty n);,else,front+;,printf,(pop%d from queue n);,3.,2006,循环队列,队列常常以循环队列（,circle queue,）,来表示，即,CQ(0,MAX-1),，,如图,3-6,所示。,图,3-6,循环队列示意图,循环队列的初始值为,front=rear=MAX-1,，,当有元素要插入时，利用,rear=(rear+1)%MAX,语句求出,rear,，,以便能够使,rear,回到前面，看看是否还有空的位置可放。,循环队列的删除，是判断,front,是否和,rear,在同一个位置，若是 则打印出循环队列是满的信息，否则，将,front,往前移，并插入 元素。,3.,2006,循环队列程序实例,/*,file name:,cqueue,.c */,/*,使用环形队列处理数据,新增、删除、输出,*/,#,include,#include,#include,#define MAX 20,void,enqueue,_f(void);/*,新增函数,*/,void,dequeue,_f(void);/*,删除函数,*/,void list_f(void);/*,输出函数,*/,3.,2006,循环队列程序实例（1）,char itemMAX20;,int,front=MAX-1,rear=MAX-1,tag=0;,/*tag,为记忆,front,所在是否已储存数据，,0,时为没有存放数据，,1,时为存放数据,*/,void main(void),char option;,while(1),3.,2006,循环队列程序实例（2）,printf,(n*n);,printf,(insert(,enqueue,)n);,printf,(delete(,dequeue,)n);,printf,(listn);,printf,(quitn);,printf,(*n);,printf,(Please enter your choice.);,option=,getche,();,switch(option),3.,2006,循环队列程序实例（3）,case 1:,enqueue,_f();,break;,case 2:,dequeue,_f();,break;,case 3:,list_f();,break;,case 4:,exit(0);,3.,2006,循环队列程序实例（4）,void,dequeue,_f(void),If(front=rear&tag=0)/*,当队列中没有数据存,在时，显示错误,*/,printf,(nn No item,queue is empty!n);,else,front=(front+1)%MAX;,printf,(nn Item%s deletedn,itemfront);,if(front=rear)tag=0;,3.,2006,循环队列程序实例（5）,void,enqueue,_f(void),if(front=rear&tag=1)/*,当队列已满时，显示错误,*/,printf,(n,nQueue,is full!n);,else,rear=(rear+1)%MAX;,printf,(nn Please enter item to insert:);,gets(itemrear);,if(front=rear)tag=1;,3.,2006,循环队列程序实例（6）,void list_f(void),int,count=0,i;,if(front=rear&tag=0),printf,(nn No item,queue is emptyn);,else,printf,(nn ITEMn);,printf,(-n);,for(i=(front+1)%MAX;i!=rear;i=+i%MAX),printf,(%-20sn,itemi);,count+;,if(count%20=0),getch,();,3.,2006,循环队列程序实例（7）,printf,(%-20sn,itemi);,printf,(-n);,printf,(Total item:%dn,+count);,getch,();,3.,2006,堆栈与队列的应用,由于堆栈具有先进后出的特性，因此凡是具有后来先处理特性的，都可以使用堆栈来解决。,堆栈还有一些很好的用途，就是如何将算术表达式由中序表达式变为后序表达式。,运算符有优先顺序与结合性，以及又有括号先处理的问题，为了避免上述的问题，编译程序将一般的中序表达式先转化为后序表达式。,假如所要解决的问题是有先进先出特性的，则宜用队列来解决，例如操作系统的工作调度（,job scheduling,）,。,3.,2