第三章 栈和队列

1、第三章 栈和队列3.1 3.1 栈栈栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。栈栈顶顶( (TopTop) )：允许进行插入、删除：允许进行插入、删除操作操作的的一端，又称为表尾一端，又称为表尾。用用栈顶指针栈顶指针(top)(top)来指示栈顶元素。来指示栈顶元素。栈栈底底( (BottomBottom) )：是固定端，又称为表头。：是固定端，又称为表头。空空栈栈：当表中没有元素时称为空栈。：当表中没有元素时称为空栈。顺序顺序栈示意图栈示意图a1

2、a2aian bottomtop进栈（进栈（push）出栈出栈(pop) 栈的顺序存储栈的顺序存储#defindefine STACK_INIT_SIZE 100;#definedefine STACKINCREMENT 10;typedeftypedef structstruct SElemType *base; SElemType *top; int stacksize;SqStack;.Status Status InitStackInitStack( (SqStackSqStack &s) &s) S.base=(SElemType*)mallocmalloc(STACK_INIT_S

3、IZE*sizeof(SElemType); if(!S.base) exiexit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnreturn OK;栈的顺序栈的顺序存储存储 ( (入入栈和出栈栈和出栈) )Status Push(SqStack &S, SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType *)reallocrealloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); i

4、f(!S.base) exitexit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; returnreturn OK;Status Pop(SqStack &S, SElemType &e) if(S.top=S.base) returnreturn ERROR; e=*-S.top; returnreturn OK;堆栈堆栈变化示意图变化示意图空栈空栈bottomtopTop=11个元素进栈个元素进栈bottomtopaTop=33个元素进栈个元素进栈bottomtopabcTop=4

5、栈满栈满bottomtopabedTop=2元素元素c进栈进栈bottomtopab 当当栈满时做进栈运算必定产生空间溢出，简称栈满时做进栈运算必定产生空间溢出，简称“上溢上溢”。上。上溢是一种出错状态，应设法避免。溢是一种出错状态，应设法避免。 当当栈空时做退栈运算也将产生溢出，简称栈空时做退栈运算也将产生溢出，简称“下溢下溢”。下溢则。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件所以下溢常用来作为控制转移的条件。3.2 3.2 队列队列队列(Queue)：也是运算受限的线性表。是一种先进先

6、出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首(front) ：允许进行删除的一端称为队首。队尾(rear) ：允许进行插入的一端称为队尾。a1 , a2 , , an出队出队入队入队队尾队尾队首队首队列的顺序表示和实现队列的顺序表示和实现 利用利用一组连续的存储单元一组连续的存储单元( (一维数组一维数组) ) 依次存依次存放从队首到队尾的各个元素，称为放从队首到队尾的各个元素，称为顺序队列顺序队列。 其其类型定义如下：类型定义如下：#define MAX_QUEUE_SIZE 100#define MAX_QUEUE_

7、SIZE 100typedeftypedef structstruct queue queue ElemTypeElemType Queue_arrayQueue_arrayMAX_QUEUE_SIZE ;MAX_QUEUE_SIZE ;intint front ; front ;intint rear ; rear ; SqQueueSqQueue; ;队列的顺序队列的顺序存储结构存储结构设立一个设立一个队首指针队首指针frontfront ，一个，一个队尾指针队尾指针rearrear ，分，分别指向队首和队尾元素。别指向队首和队尾元素。 初始化初始化：front=rear=0front=r

8、ear=0。 入队入队：将新元素插入：将新元素插入rearrear所指的位置，然后所指的位置，然后rearrear加加1 1。 出队出队：删去：删去frontfront所指的元素，然后加所指的元素，然后加1 1并返回并返回被删元素。被删元素。 队列为空队列为空：front=rearfront=rear。 队满队满：rear=MAX_QUEUE_SIZE-1rear=MAX_QUEUE_SIZE-1或或front=rearfront=rear。队列的顺序队列的顺序存储结构存储结构顺序队列中存在顺序队列中存在“假溢出假溢出”现象。因为在入队和出队操作现象。因为在入队和出队操作中，头、尾指针只增加不

9、减小，致使被删除元素的空间永中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针巳超出向量空间的上远小于数组大小，但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为界而不能做入队操作。该现象称为假假溢出。溢出。(a) 空队列空队列Q.frontQ.rear(b)入队入队3个元素个元素a3a2a1Q.frontQ.rear(c) 出队出队3个元素个元素Q.frontQ.rear(d) 入队入队2个元素个元素a5a4Q.frontQ.rear队列的链式表示

10、和实现队列的链式表示和实现队列的链式存储结构简称为链队列，它是限制仅在队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。表头进行删除操作和表尾进行插入操作的单链表。 需要需要两类不同的结点：两类不同的结点：数据元素数据元素结点，队列的结点，队列的队队首指针和队尾指针首指针和队尾指针的结点的结点，数据元素结点数据元素结点data指针结点指针结点front rear链链队列结点示意图队列结点示意图队列的链式表示和实现队列的链式表示和实现typedef struct Qnode QElemType data ;struct Qnode *next ;Qnode,

11、 *QueuePtr; typedef struct QueuePtr *front , QueuePtr *rear ;Link_Queue ;链队运算及指针链队运算及指针变化变化 队列操作及指针变化队列操作及指针变化(a) 空队列空队列front rear(b) x入队入队 x front rear(c) y再入队再入队 y front rear x(d) x出队出队 y xfront rear链队列的基本链队列的基本操作操作/链队的初始化StatusStatus InitQueue (LinkQueue &Q) Q.front=Q.rear=(QueuePtr)mallocmalloc(

12、sizeof(QNode); if(!Q.front) exitexit(OVERFLOW); Q.front-next=NULL; returnreturn OK;链队列的基本链队列的基本操作操作/链队销毁Status Status DestroyQueue (LinkQueue &Q) whilewhile(Q.front) Q.rear=Q.front-next; freefree(Q.front); Q.front=Q.rear; returnreturn OK;链队列的基本链队列的基本操作操作/插入元素e为Q的新的队尾元素Status Status EnQueue(LinkQueue

13、 &Q, QElemType e) p=(QueuePtr) mallocmalloc (sizeofsizeof(QNode) )； if(!p) exitexit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; returnreturn OK; 链队列的基本链队列的基本操作操作/删除Q队头元素，用e返回其值。StatusStatus Dequeue(LinkQueue &Q, QElemType &e) if if(Q.frfont=Q.rear) returnreturn ERROR; p=Q.front-next;

14、e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; freefree(p); returnreturn OK; 循环队列为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。J6J5Q.frontQ.rear当队列处于此种情况是不可再继续插入新的队尾元素，否则会因数组越界而被破坏。但此时又不能再分配扩大数组空间，因为队列的实际可用空间并未占满。循环队列在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当

15、队首、队尾指针指向向量上界(MAXSIZE-1)时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if (i+1=MAX_QUEUE_SIZE) i=0;else i+ ;其中： i代表队首指针(front)或队尾指针(rear)01Maxsize-1循环队列例：设有循环队列QU0，5，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图所示。 1 12 23 34 45 50 0(a) (a) 空队列空队列frontfrontrearrear1 12 23 34 45 50 0(b) d, e, b, g(b) d, e, b, g入

16、入队队frontfrontd de eb bg grearrear1 12 23 34 45 50 0(c) d, e(c) d, e出队出队b bg gfrontfrontrearrear循环队列1 12 23 34 45 50 0(d) i, j, k(d) i, j, k入入队队b bg gfrontfronti ij jk krearrear1 12 23 34 45 50 0(e) b, g(e) b, g出队出队i ij jk krearrearfrontfront1 12 23 34 45 50 0(f) r, p, s, t(f) r, p, s, t入队入队i ij jk k

17、frontfrontr rp prearrear循环队列入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过无法通过front=rearfront=rear来判断队列来判断队列“空空”还是还是“满满”。解决此问题的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即： rear所指的单元始终为空。 循环队列为空：front=rear 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front循环队列的操作（定义）#define MAXQSIZE 100t typedefypedef structstr

18、uct QElemTypeQElemType *base; intint front; intint rear;SqQueue;循环队列的操作（初始化）StatusStatus InitQueue(SqQueue &Q) Q.base=(QElemType *)mallocmalloc(MAXQSIZE *sizeofsizeof(QElemType); if(!Q.base) exitexit(OVERFLOW); Q.front=Q.rear=0; returnreturn OK;循环队列的操作StatusStatus InitQueue(SqQueue &Q) Q.base=(QElemType *)mallocmalloc(MAXQSIZE *sizeofsizeof(QElemType); if(!Q.base) exitexit(OVERFLOW); Q.front=Q.rear=0; returnreturn OK;循环队列的操作（求队列长度）int QueueLength(SqQueue Q) returnreturn (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;循环队列的操作（插入）StatusStatus EnQueue(Sq