队列

单链队列

单链队列使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高
  1 // 定义单链队列的存储结构  2 typedef struct QNode {  3     int data;  4     QNode *next;  5 }QNode,*QNodePtr;  6   7 typedef struct LinkQueue{  8     //队头 队尾 指针  9     QNodePtr front,rear; 10 }LinkQueue; 11  12  13 // 构造一个空队列Q 14 LinkQueue* Q_Init() { 15     //申请内存 16     LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue)); 17     //如果 Q 为 NULL 说明 内存申请失败，结束程序 18     if (!Q) 19         exit(OVERFLOW); 20     //初始化头尾节点 指向相同地址 21     Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode)); 22     //如果 Q->front 为 NULL 说明 内存申请失败，结束程序 23     if (!Q->front) 24         exit(OVERFLOW); 25     Q->front->next = NULL; 26     return Q; 27 } 28  29 // 销毁队列Q(无论空否均可) 30 void Q_Destroy(LinkQueue *Q) { 31     while (Q->front) { 32         //将队尾指向队头下一个节点的地址（第1个节点） 33         Q->rear = Q->front->next; 34         //回收队头 35         free(Q->front); 36         //将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个、、、 37         //直到没有下一个节点，也就是Q->front == NULL 的时候） 38         Q->front = Q->rear; 39     } 40     free(Q); 41 } 42  43 // 将Q清为空队列 44 void Q_Clear(LinkQueue *Q) { 45     QNodePtr p, q; 46     //将队尾指向队头点的地址 47     Q->rear = Q->front; 48     //取出第1个节点 49     p = Q->front->next; 50     //回收第1个节点 51     Q->front->next = NULL; 52     while (p) { 53         //将 q 指向 p（第1个节点） 54         q = p; 55         //将 p 指向 第2个节点 56         p = p->next; 57         //回收第2个节点 58         free(q); 59     } 60 } 61  62 // 若Q为空队列，则返回-1，否则返回1 63 int Q_Empty(LinkQueue Q) { 64     if (Q.front->next == NULL) 65         return 1; 66     else 67         return -1; 68 } 69  70 // 求队列的长度 71 int Q_Length(LinkQueue Q) { 72     int i = 0; 73     QNodePtr p; 74     p = Q.front; 75     //遍历队列中的节点，直到队尾等于队头 76     while (Q.rear != p) { 77         i++; 78         p = p->next; 79     } 80     return i; 81 } 82  83 // 打印队列中的内容 84 void Q_Print(LinkQueue Q) { 85     int i = 0; 86     QNodePtr p; 87     p = Q.front; 88     while (Q.rear != p) { 89         i++; 90         cout << p->next->data << endl; 91         p = p->next; 92     } 93 } 94  95 // 若队列不空，则用e返回Q的队头元素，并返回1，否则返回-1 96 int Q_GetHead(LinkQueue Q, int &e) { 97     QNodePtr p; 98     if (Q.front == Q.rear) 99         return -1;100     p = Q.front->next;101     e = p->data;102     return 1;103 }104 105 // 插入元素e为Q的新的队尾元素106 void Q_Put(LinkQueue *Q, int e) {107     QNodePtr p = (QNodePtr)malloc(sizeof(QNode));108     if (!p) // 存储分配失败109         exit(OVERFLOW);110     p->data = e;111     p->next = NULL;112     //FIFO，将新节点追加到尾节点后面113     Q->rear->next = p;114     //将新的节点变成尾节点115     Q->rear = p;116 }117 118 119 // 若队列不空，删除Q的队头元素，用e返回其值，并返回1，否则返回-1120 int Q_Poll(LinkQueue *Q,int &e) {121     QNodePtr p;122     if (Q->front == Q->rear)123         return -1;124     //取出头节点125     p = Q->front->next;126     //取出头节点的数据127     e = p->data;128     cout << e << endl;129     Q->front->next = p->next;130     if (Q->rear == p)131         Q->rear = Q->front;132     free(p);133     cout << e << endl;134     return 1;135 }

循环队列

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
 1 // 队列的顺序存储结构(循环队列) 2 #define MAX_QSIZE 5 // 最大队列长度+1 3 typedef struct { 4     int *base; // 初始化的动态分配存储空间 5     int front; // 头指针，若队列不空，指向队列头元素 6     int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 7 } SqQueue; 8  9 10 // 构造一个空队列Q11 SqQueue* Q_Init() {12     SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));13     // 存储分配失败14     if (!Q){15         exit(OVERFLOW);16     }17     Q->base = (int *)malloc(MAX_QSIZE * sizeof(int));18     // 存储分配失败19     if (!Q->base){20         exit(OVERFLOW);21     }22     Q->front = Q->rear = 0;23     return Q;24 }25 26 // 销毁队列Q，Q不再存在27 void Q_Destroy(SqQueue *Q) {28     if (Q->base)29         free(Q->base);30     Q->base = NULL;31     Q->front = Q->rear = 0;32     free(Q);33 }34 35 // 将Q清为空队列36 void Q_Clear(SqQueue *Q) {37     Q->front = Q->rear = 0;38 }39 40 // 若队列Q为空队列，则返回1；否则返回-141 int Q_Empty(SqQueue Q) {42     if (Q.front == Q.rear) // 队列空的标志43         return 1;44     else45         return -1;46 }47 48 // 返回Q的元素个数，即队列的长度49 int Q_Length(SqQueue Q) {50     return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;51 }52 53 // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR54 int Q_GetHead(SqQueue Q, int &e) {55     if (Q.front == Q.rear) // 队列空56         return -1;57     e = Q.base[Q.front];58     return 1;59 }60 61 // 打印队列中的内容62 void Q_Print(SqQueue Q) {63     int p = Q.front;64     while (Q.rear != p) {65         cout << Q.base[p] << endl;66         p = (p + 1) % MAX_QSIZE;67     }68 }69 70 // 插入元素e为Q的新的队尾元素71 int Q_Put(SqQueue *Q, int e) {72     if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满73         return -1;74     Q->base[Q->rear] = e;75     Q->rear = (Q->rear + 1) % MAX_QSIZE;76     return 1;77 }78 79 // 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-180 int Q_Poll(SqQueue *Q, int &e) {81     if (Q->front == Q->rear) // 队列空82         return -1;83     e = Q->base[Q->front];84     Q->front = (Q->front + 1) % MAX_QSIZE;85     return 1;86 }

阵列队列

1 #define MAX_QSIZE 10 // 最大队列长度+1 2 // 阵列队列的存储结构 3 struct Queue { 4     int Array[MAX_QSIZE]; // 阵列空间大小 5     int front; // 队头 6     int rear; // 队尾 7     int length; // 队列长度 8 }; 9 10 // 构造一个空队列Q11 Queue* Q_Init() {12     Queue *Q = (Queue*)malloc(sizeof(Queue));13     if (!Q){14         // 存储分配失败15         exit(OVERFLOW);16     }17     //初始化18     Q->front = Q->rear = Q->length = 0;19     return Q;20 }21 22 // 将Q清为空队列23 void Q_Clear(Queue *Q) {24     //清除头尾下标和长度25     Q->front = Q->rear = Q->length = 0;26 }27 28 // 入列29 int Q_Put(Queue *Q, int x) {30     //如果当前元素数量等于最大数量 返回-131     if (Q->rear + 1 == MAX_QSIZE) {32         return -1;33     }34     Q->Array[Q->rear] = x;35     Q->rear = Q->rear + 1;36     //length + 137     Q->length = Q->length + 1;38     return 1;39 }40 41 // 出列42 int Q_Poll(Queue *Q) {43     //如果当前元素数量等于最大数量 返回-144     if (Q->front + 1 == MAX_QSIZE)45         return -1;46     int x = Q->Array[Q->front];47     Q->front = Q->front + 1;48     // 移出后減少149     Q->length = Q->length - 1;50     return x;51 }