队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头 (Front)
,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)
队列的基本运算也有六种：
置空队 ：InitQueue(Q)
清空队：ClearQueue（Q)
判队空： QueueEmpty(Q)
入队 ： EnQueue(Q,x)
出队 ： DeQueue(Q)
销毁队列：DestroyQueue（Q)
取队头元素： GetHead(Q),不同与出队，队头元素仍然保留。
取队尾元素：GetBack（Q)
对整个队列进行遍历：QueueTraverse（Q)
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
#include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; typedef int ElemType; typedef struct QNode { ElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if (!(Q->front)) exit(0); Q->front->next=NULL; } void DestroyQueue(LinkQueue *Q) { while (Q->front) { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } } void ClearQueue(LinkQueue *Q) { QueuePtr p; p=Q->front->next; while (p) { Q->front->next=p->next; free(p); } Q->rear=Q->front; } int QueueEmpty(LinkQueue Q) { if (Q.front==Q.rear) return 1; else return 0; } int QueueLength(LinkQueue Q) { QueuePtr p; int n=0; p=Q.front; while (p!=Q.rear) { n++; p=p->next; } return n; } ElemType GetHead(LinkQueue Q) { if (Q.front!=Q.rear) return Q.front->next->data; } ElemType GetBack(LinkQueue Q) { if (Q.front!=Q.rear) return Q.rear->data; } void EnQueue(LinkQueue *Q, ElemType e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if (!p) exit(0); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; } void DeQueue(LinkQueue *Q, ElemType *e) { QueuePtr p; if (Q->front!=Q->rear) { p=Q->front->next; *e=p->data; Q->front->next=p->next; if (Q->rear==p) Q->rear=Q->front; free(p); } } void QueueTraverse(LinkQueue Q) { QueuePtr p; printf(" Queue: "); p=Q.front->next; while (p) { printf("%d ",p->data); p=p->next; } } int main() { LinkQueue Q; int i; ElemType x; InitQueue(&Q); for(i=2; i<=5; i++) EnQueue(&Q,i); printf("len:%d ",QueueLength(Q)); cout<<GetBack(Q)<<endl; cout<<GetHead(Q)<<endl; // while (!QueueEmpty(Q)) // { // DeQueue(&Q,&x); // printf("%d ",x); // } }
队列的应用
【举例1】银行排队
【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例3】CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。