数据结构-栈与队列解读.ppt

按顺序方式存储的队列，数据元素存储在一系列连续的存储单元中，其结构与顺序表相同。 因此顺序存储的队列也可用一维数组来实现，front和rear指针则转变为队头和队尾元素在数组中的下标。 队列顺序存储 队列顺序存储 顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。 因此在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。 若front和rear指针分别为队头和队尾元素在数组中的下标，则 入队操作： rear=rear+1，再将新元素赋值到rear所指位置 出队操作： 先将下标为front的元素读出，再front+1 这两种操作，移动指针和赋值的顺序相反，不利于编程。 为方便起见，这里规定队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置。这样，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。 对空队列而言，可假定front和rear的值为-1 假溢出 A B C front rear front rear (a) A?B?C入队 (b) A?B出队, D?E入队 (c)队列假溢出 队列假溢出示意图 C D E front rear 随着元素不断入队列、出队列，rear和front指针会不断向后移动（如图(b)所示），最终会指向数组的最大下标位置（如图(c)所示）。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。 循环队列 解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。 循环队列的基本操作方式为： 入队列 先执行rear=(rear+1)%M，再将新元素在rear指示位置加入； 出队列 先执行front=(front+1)%M，再将下标为front的元素取出。 为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。 队空条件为front=rear 队满条件为(rear+1)%M=front 3 0 1 2 4 5 6 7 front rear A B C D 3 0 1 2 4 5 6 7 front rear 3 0 1 2 4 5 6 7 front rear A B C D F G E (a)循环队列空 (b)非空循环队列 (c)循环队列满 循环队列示意图 循环队列描述如下： struct SqQueue{ ElemType *data; // 存放元素的数组 int length; // 数组空间总长度 int front; // 队头指针 int rear; // 队尾指针 }; struct SqQueue q; // 定义队列q front和rear指针取值均为所指数组单元的下标。 由于队头指针所指单元总是空的，length比实际能存储的元素多一。 常用算法 （1）循环队列初始化 初始化过程建立数组空间并将队头、队尾指针设定到0号单元。 void InitQueue(SqQueue Q, int sz ) { Q.length = sz+1; Q.front = Q.rear = 0; Q.data = ( ElemType *)malloc(Q.length*sizeof (ElemType)); } 这里sz为队列最大长度，数组长度length比sz大一。 （2）入队操作 若队列不满，则在队尾插入元素x作为新的队尾。 void EnQueue(SqQueue Q , ElemType x) { if((Q.rear+1)%Q.length==Q.front) printf(“队列已满“); else { Q.rear = (Q.rear+1)%Q.length; Q.data[Q.rear]=x; } } ?（3）出队操作 若队列不空，则删除队头元素并用e取回该元素的值。 void DeQueue(SqQueue Q, ElemType e) { if(Q.rear==Q.front) printf(“队列已空“); else { Q.front = (Q.front +1)% Q.length; e = Q.data[Q.front]; } } （4）取队头元素 若队列不空，则用e取回队头元素的值。 void GetHead(SqQueu