队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 实现如下：
#include <iostream> #include <stdlib.h> #define OVERFLOW -3 #define ok 1 #define error -1 #define true 1 #define false - 1 using namespace std; typedef struct QNode { int data; struct QNode *next; } * Queueptr; typedef struct { Queueptr front;//对头指针 Queueptr rear;//队尾指针 } LinkQueue; //构造一个空队列 int InitQueue(LinkQueue &Q) { Q.front = Q.rear = (Queueptr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); Q.front->next = NULL; return ok; } //销毁队列 int DestroyQueue(LinkQueue &Q) { while (Q.front) { Q.rear = Q.front->next; free(Q.front); Q.front = Q.rear; } return ok; } //清空队列 void ClearQueue(LinkQueue &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); } } //队列为空返回1，非空返回-1 int QueueEmpty(LinkQueue Q) { 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; } //队列非空返回队首元素，返回ok否则返回error int GetHead(LinkQueue Q, int &e) { Queueptr p; if (Q.front == Q.rear) return error; p = Q.front->next; e = p->data; return ok; } //队尾插入元素 int EnQueue(LinkQueue &Q, int e) { Queueptr p; p = (Queueptr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return ok; } //队列非空，队首删除元素 int DeQueue(LinkQueue &Q, int &e) { Queueptr p; if (Q.rear == Q.front) 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; } //从首到尾遍历队列 int QueueTraverse(LinkQueue Q) { Queueptr p; p = Q.front->next; while (p) { cout<< p->data<< " "; p = p->next; } cout << "return (1:ok -1:error):"; return ok; cout << endl; } int main() { int i, d; LinkQueue q; InitQueue(q); cout << "init queue successfully" << endl; cout << "whether queue is empty(1:empty -1:not empty):" << QueueEmpty(q) << endl; cout << "the length of queue is:" << QueueLength(q) << endl; EnQueue(q, -5); EnQueue(q, 8); EnQueue(q, 88); cout << "after insert numbers the length of queue is:" << QueueLength(q) << endl; cout << "whether queue is empty(1:empty -1:not empty):" << QueueEmpty(q) << endl; cout << "the elem of queue is:"; cout << QueueTraverse(q) << endl; i = GetHead(q, d); if (i == ok) cout << "the head of queue is:" << d << endl; DeQueue(q, d); cout << "deleted the head elem" << endl; i = GetHead(q, d); if (i == ok) cout << "the head of queue is:" << d << endl; ClearQueue(q); cout << "after clear up the queue:q.front=" << q.front << " q.rear=" << q.rear << " q.front->next=" << q.front->next << endl; DestroyQueue(q); cout << "after deatroy the queue:q.front=" << q.front << " q.rear=" << q.rear << endl; system("pause"); }结果如下：
