3.3 队列的类定义及其实现队列的类定义及其实现 队队列列（（Queue））也也是是线线性性表表的的特特例例它它将将元元素素排排列列成成队队，，有有入入口口（（队队尾尾））和和出出口口（（队队头头）），，数数据据元元素素只只能能从从队队尾尾入入队队，，从从队队头头离离队队所所以以，，队队列列具具有有先先进进先先出出（（First In First Out，，FIFO））或或后后进进后后出出（（Last In Last Out，，LILO）的特点 在在现现实实生生活活中中，，有有许许多多问问题题可可以以用用队队列列描描述述例例如如银银行行、、车车站站等等顾顾客客服服务务部部门门的的工工作作就就是是按按队队列列方方式式进进行行的的，，下下图图为为一一个个排排队队示示意意图图在在程程序序设设计计中中，，也也经经常常使使用用队队列列记记录录一一些些需需要要按按照照先先进进先先出出方方式式处处理理的数据，例如键盘缓冲区、操作系统中的作业调度等的数据，例如键盘缓冲区、操作系统中的作业调度等 队列的顺序存储结构称为队列的顺序存储结构称为顺序队列顺序队列（（Sequential Queue）。
在顺序队）在顺序队列中，需要用一组地址连续的存储单元依次存放从队头到队尾的元素，由列中，需要用一组地址连续的存储单元依次存放从队头到队尾的元素，由于队列的队头和队尾的位置是变化的，因而还需要两个指针于队列的队头和队尾的位置是变化的，因而还需要两个指针front和和rear作作为队头指针和队尾指针来分别指示队头和队尾元素在队列中的位置为队头指针和队尾指针来分别指示队头和队尾元素在队列中的位置 下图为元素入队、出队的变化情况： 下图为元素入队、出队的变化情况： 1.循环队列循环队列 如果仅仅简单地将顺序队列如此定义，则会出现如果仅仅简单地将顺序队列如此定义，则会出现“假溢假溢”现象，如现象，如上上图图中中（（d）所示，当）所示，当rear大于等于容量时，新元素将无法入队，但事实上队列大于等于容量时，新元素将无法入队，但事实上队列的低端仍有空闲的存储单元，这种现象称为的低端仍有空闲的存储单元，这种现象称为“假溢假溢”因此为充分利用存储因此为充分利用存储空间，对队列的存储方式进行一定的改进解决空间，对队列的存储方式进行一定的改进解决“假溢假溢”现象，由此产生了循现象，由此产生了循环队列。
环队列 解决解决“假溢假溢”现象的方法是将存储队列的数组看成是头尾相接的圆环，现象的方法是将存储队列的数组看成是头尾相接的圆环，并成为循环存储空间，即允许队列直接从数组中下标最大的位置延续到下并成为循环存储空间，即允许队列直接从数组中下标最大的位置延续到下标最小的位置，这个操作可以通过取模运算实现队列的这种头尾相接的标最小的位置，这个操作可以通过取模运算实现队列的这种头尾相接的顺序存储结构称为循环队列（顺序存储结构称为循环队列（Circular Queue）） 在循环队列中进行入队、出队操作时，头尾指针仍要加在循环队列中进行入队、出队操作时，头尾指针仍要加1，朝前移动朝前移动只不过当头尾指针指向存储空间上界（只不过当头尾指针指向存储空间上界（QueueSize-1）时，其加）时，其加1操作的结操作的结果是指向存储空间的下界果是指向存储空间的下界0这种循环意义下的加这种循环意义下的加1操作利用模运算可简化操作利用模运算可简化为为i=(i+1)%QueueSize其中，QueueSize表示存储循环队列的数组的长度，表示存储循环队列的数组的长度，则循环队列的长度为（则循环队列的长度为（rear-front+QueueSize））%QueueSize。
如如下图下图所示便所示便是一个循环队列的结构示意图是一个循环队列的结构示意图 循环队列的类定义：循环队列的类定义： #define MaxSize 100 class CQueue { private:int *base;// 存储空间基址存储空间基址int front;// 队头指针队头指针int rear;// 队尾指针队尾指针 public: CQueue(){base=new int[MaxSize]; front=rear=0;}//构造空队列构造空队列 ~CQueue();// 析构函数，释放链队各结点的存储空间析构函数，释放链队各结点的存储空间void EnQueue(int e);// 元素元素e入队入队void DeQueue(int &e);// 队队列列元素出队元素出队 int emptyQueue();//队列判空队列判空int GetHead();// 取队头元素取队头元素int GetLast();//取队尾元素取队尾元素void QueueDisplay();//遍历队，输出队列元素遍历队，输出队列元素 }; （（1））入队算法入队算法 void CQueue ::EnQueue(int e){ if((rear+1)%(MaxSize) ==front) { cout<<"上溢，无法上溢，无法入队入队"; return; } base[rear]=e; rear=(rear+1)%queuesize; }(2) (2) 出队算法出队算法void DeQueue(int &e){void DeQueue(int &e){ if(front==rear) { if(front==rear) { cout<<" cout<<"下溢，不能出队下溢，不能出队";"; return ; return ; } } e=base[front]; e=base[front]; front=(front+1)%queuesize;front=(front+1)%queuesize; } }(3) (3) 队列判空队列判空 int emptyQueue(){ int emptyQueue(){ if(rear==front)retuif(rear==front)return 1;rn 1; else else return 0;return 0; } } ２２ 链队列链队列 队列的链式存储结构称为链队列（队列的链式存储结构称为链队列（Linked Queue）。
根据队列先进先）根据队列先进先出的特性，链队列是仅在表头删除元素和表尾插入元素的单链表为了操出的特性，链队列是仅在表头删除元素和表尾插入元素的单链表为了操作方便，链队列用有头结点的链表表示，并设置队头指针指向链队列的头作方便，链队列用有头结点的链表表示，并设置队头指针指向链队列的头结点，队尾指针指向终端结点，如结点，队尾指针指向终端结点，如下下图所示链队列加上头结点，能够使图所示链队列加上头结点，能够使空队列和非空队列的操作一致，链队列的具体判定和操作如下：空队列和非空队列的操作一致，链队列的具体判定和操作如下： 链链队列的类定义和基本操作队列的类定义和基本操作 struct Node{ int data; Node *next; }; class LinkQueue{ private: Node *front;//队头指针，链表头为队头队头指针，链表头为队头 Node *rear;//队尾指针，链表尾为队尾队尾指针，链表尾为队尾 public: LinkQueue(){front=rear=new Node;front->next=NULL;}//构造空队列构造空队列 ~LinkQueue();// 析构函数，释放链队各结点的存储空间析构函数，释放链队各结点的存储空间 void EnQueue(int e);// 元素元素x入队入队 void DeQueue(int &e);// 队顶元素出队队顶元素出队 int emptyQueue(){if(front==rear)return 1;else return 0;}//队列判空队列判空 int GetHead();// 取队头元素取队头元素 int GetLast();//取队尾元素取队尾元素 void QueueDisplay(); }; 链队列入队算法链队列入队算法 void LinkQueue::EnQueue(int e){ Node *s; s=new Node; s->data=e; s->next=rear->next; rear->next=s; rear=s; }链队列出队算法链队列出队算法void LinkQueue::DeQueue(int void LinkQueue::DeQueue(int &e){&e){ Node *p; Node *p; if(rear==front){ if(rear==front){ cout<<" cout<<"下溢下溢";return;";return; }// }//队空，则下溢队空，则下溢 p=front->next; p=front->next; e=p->data; e=p->data; front->next=p->next; front->next=p->next; if(p- if(p->next==NULL)rear=front;>next==NULL)rear=front; delete p; delete p; } } 。