队列的顺序实现.docx

队列的顺序存储结构及实现和顺序栈相类似，在队列的顺序存储结构中，除了利用一组连续的存储单元依次存放从队列头到队列尾的数据元素之外，还需要附设两个指针front和队尾指针rear,分别指示队列头元素和队列尾元素的位置。1．队列的顺序存储表示#define MAXQSIZE 100; ?? ??//最大队列长度 ?? ?? ?? ??typedef struct{?? QelemType *base; ?? ?? //初始化的动态分配存储空间的基础?? Int front; ?? ?? ?? ?? ?? //队头指针?? int rear; ?? ?? ?? ?? ?? ??//队尾指针}SqQueue; ?? ?? ?? ?? ?? ?? ??//顺序队列的类型名其中：front ?? ?? 若队列不空，指向队列头元素rear ?? ?? ??若队列不空，指向队列尾元素的下一个位置2．队列的初始化操作?? ??初始化构建空队列时，令front=rear=0;每当插入新的队列尾元素时，先将新元素插入到队尾指针所指位置，再使队尾指针rear加1；每当删除旧的队列头元素时，先使队头指针所指位置的元素取出，再使队头指针front加工厂。因此，在非空队列中，队头指针始终指向队列头元素，而队尾指针始终指向队列尾元素的下一个位置。3循环队列队列用顺序结构表示时，除了用一组地址连续的存储单元(最大容量为MAXQSIZE)依次存储先后入队的数据元素外，还需要两个指针:队头指针指向队头元素的位置，队尾指针指向队尾元素的位置。循环队列的存储结构可描述如下。typedef struct{??ETp * base; ??//指向循环队列数组??int ??front; ??//队头指针??int ??rear; ??//队尾指针??int ??size; ??//队列最大容量} CQueue我们约定：队尾指针总是指向刚入队的数据元素(队尾元素)的下一个位置，而队头指针总指向队头元素。空队列用Q.front=Q.rear表示。如图3(a)所示。因为插入操作总在队尾进行，删除操作总在队头进行，因此队尾将越来越接近数组的高端，当队尾指针指向数组高端后一个位置时，若要插入元素就会引起数组越界，但这时数组未必已满，因为队头处可能已删除了一些数据元素。?? ?? 为解决队列看起来似乎已满但实际仍有存储空间空闲的情况,可将顺序队列视作一个环状的空间，即数组的第一个(下标为0的)分量被视为数组的上界分量的下一个元素。如此，当队尾元素已达数组高端,但队列并未真满,而又要插入数据元素时,则可将新数据元素插入到数组的第一个分量，如图4(a)所示。这样处理的队列称之为循环队列。对于循环队列，如仍规定队头指针指向队头元素，队尾指针指向队尾元素的后一个位置，则当数组被数据元素充满时，Q.rear将同Q.front一样，指向队头元素，即Q.rear=Q.front,如图4(b)所示。但按原来的规定，Q.front=Q.rear时表示队列为空。由此可见，在循环队列中不能简单地用条件Q.front=Q.rear来判别队列是否为空(或满)。为解决此问题，我们约定：在循环队列中少用一个数组分量，即若(Q.rear+1)%Q.size=Q.front,则表示循环队列已满，而仍用条件Q.front=Q.rear表示空队列，如图4(c)(d)所示。由于将数组各分量视作首尾相连的，因此当Q.front(或Q.rear)指向下标为(MAXQSIZE-1)的分量时，其下一个分量就是下标为0的分量。一般地，指针增1操作可用(Q.front+1)%Q.size表示，其中Q.size存储循环队列的最大容量(MAXQSIZE)。/* ======================================== *//* ?? ??使用数组来构建队列 ?? ?? ?? ?? ?? ?? ?? ?? ?? ??*//* ======================================== */#define MAXQUEUE 10 ?? ?? ?? ?? ?? ?? ?? /* 队列的最大容量 ?? */int queue[MAXQUEUE]; ?? ?? ?? ?? ?? ?? ??/* 队列的数组宣告 ?? */int front = -1; ?? ?? ?? ?? ?? ?? ?? ?? ?? /* 队列的前端 ?? ?? ?? */int rear = -1; ?? ?? ?? ?? ?? ?? ?? ?? ?? ??/* 队列的后端 ?? ?? ?? *//* ---------------------------------------- *//* ??队列资料的存入 ?? ?? ??