首页 > 代码库 > 数据结构之队列
数据结构之队列
队列(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=http://www.mamicode.com/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("\nQueue: "); p=Q.front->next; while (p) { printf("%d\t",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\n",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正常工作。
数据结构之队列