维基百科
队列
佇列，又稱為伫列（queue），计算机科學中的一種抽象資料型別，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
单链队列
单链队列使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高
存储结构
/* c3-2.h 单链队列－－队列的链式存储结构 */ typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; /* 队头、队尾指针 */ }LinkQueue; 基本操作
/* bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) */ void InitQueue(LinkQueue *Q) { /* 构造一个空队列Q */ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; } void DestroyQueue(LinkQueue *Q) { /* 销毁队列Q(无论空否均可) */ while((*Q).front) { (*Q).rear=(*Q).front->next; free((*Q).front); (*Q).front=(*Q).rear; } } void ClearQueue(LinkQueue *Q) { /* 将Q清为空队列 */ QueuePtr p,q; (*Q).rear=(*Q).front; p=(*Q).front->next; (*Q).front->next=NULL; while(p) { q=p; p=p->next; free(q); } } Status QueueEmpty(LinkQueue Q) { /* 若Q为空队列，则返回TRUE，否则返回FALSE */ if(Q.front->next==NULL) return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { /* 求队列的长度 */ int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) { i++; p=p->next; } return i; } Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */ { /* 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR */ QueuePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; *e=p->data; return OK; } void EnQueue(LinkQueue *Q,QElemType e) { /* 插入元素e为Q的新的队尾元素 */ QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p) /* 存储分配失败 */ exit(OVERFLOW); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; } Status DeQueue(LinkQueue *Q,QElemType *e) { /* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */ QueuePtr p; if((*Q).front==(*Q).rear) return ERROR; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return OK; } void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)) { /* 从队头到队尾依次对队列Q中每个元素调用函数vi() */ QueuePtr p; p=Q.front->next; while(p) { vi(p->data); p=p->next; } printf("\n"); } 循环队列
循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
// 队列的顺序存储结构(循环队列) #define MAX_QSIZE 5 // 最大队列长度+1 typedef struct { int *base; // 初始化的动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 } SqQueue; // 构造一个空队列Q SqQueue* Q_Init() { SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue)); // 存储分配失败 if (!Q){ exit(OVERFLOW); } Q->base = (int *)malloc(MAX_QSIZE * sizeof(int)); // 存储分配失败 if (!Q->base){ exit(OVERFLOW); } Q->front = Q->rear = 0; return Q; } // 销毁队列Q，Q不再存在 void Q_Destroy(SqQueue *Q) { if (Q->base) free(Q->base); Q->base = NULL; Q->front = Q->rear = 0; free(Q); } // 将Q清为空队列 void Q_Clear(SqQueue *Q) { Q->front = Q->rear = 0; } // 若队列Q为空队列，则返回1；否则返回-1 int Q_Empty(SqQueue Q) { if (Q.front == Q.rear) // 队列空的标志 return 1; else return -1; } // 返回Q的元素个数，即队列的长度 int Q_Length(SqQueue Q) { return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE; } // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR int Q_GetHead(SqQueue Q, int &e) { if (Q.front == Q.rear) // 队列空 return -1; e = Q.base[Q.front]; return 1; } // 打印队列中的内容 void Q_Print(SqQueue Q) { int p = Q.front; while (Q.rear != p) { cout << Q.base[p] << endl; p = (p + 1) % MAX_QSIZE; } } // 插入元素e为Q的新的队尾元素 int Q_Put(SqQueue *Q, int e) { if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满 return -1; Q->base[Q->rear] = e; Q->rear = (Q->rear + 1) % MAX_QSIZE; return 1; } // 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1 int Q_Poll(SqQueue *Q, int &e) { if (Q->front == Q->rear) // 队列空 return -1; e = Q->base[Q->front]; Q->front = (Q->front + 1) % MAX_QSIZE; return 1; } 陣列佇列
#define MAX_QSIZE 10 // 最大队列长度+1 // 阵列队列的存储结构 struct Queue { int Array[MAX_QSIZE]; // 阵列空间大小 int front; // 队头 int rear; // 队尾 int length; // 队列长度 }; // 构造一个空队列Q Queue* Q_Init() { Queue *Q = (Queue*)malloc(sizeof(Queue)); if (!Q){ // 存储分配失败 exit(OVERFLOW); } //初始化 Q->front = Q->rear = Q->length = 0; return Q; } // 将Q清为空队列 void Q_Clear(Queue *Q) { //清除头尾下标和长度 Q->front = Q->rear = Q->length = 0; } // 入列 int Q_Put(Queue *Q, int x) { //如果当前元素数量等于最大数量 返回 -1 if (Q->rear + 1 == MAX_QSIZE) { return -1; } Q->Array[Q->rear] = x; Q->rear = Q->rear + 1; //length + 1 Q->length = Q->length + 1; return 1; } // 出列 int Q_Poll(Queue *Q) { //如果当前元素数量等于最大数量 返回 -1 if (Q->front + 1 == MAX_QSIZE) return -1; int x = Q->Array[Q->front]; Q->front = Q->front + 1; // 移出后減少1 Q->length = Q->length - 1; return x; } 参考文献
- ^ 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安电子科技大学出版社. ISBN 9787560611761 （中文）.