队列

定义：一种可以实现先进先出的存储结构

分类：

链式队列：链表实现

静态队列：数组实现，静态队列通常必须是循环队列，减少内存浪费。

链式队列：与链表类同，实现略

循环队列：

循环队列需要两个参数来确定：

       1.front（队头）

       2.rear（队尾）

循环队列的几个定义解释：

       1.队列初始化：front和rear均为0

       2.队列非空：front指向队列第一个元素下标，rear指向队列最后一个元素的下一个元素下标

       3.队列为空：front == rear，但是不一定为0

入队伪算法：

       1.将值存入r所代表的位置

       2.将r后移，正确写法：rear=（rear+1）%数组长度  错误写法：rear=rear+1

出队伪算法：

       front=（front+1）%数组长度

判断循环队列为空

       如果front与rear相等，则队列一定为空

判断队列为满

       （rear+1）%数组长度==front

#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #define Maxsize 6 typedef struct Queue { int* pBase; int front; int rear; }QUEUE; void init(QUEUE* q); bool en_queue(QUEUE* q, int val); bool is_full(QUEUE* q); bool is_empty(QUEUE*); void traverse(QUEUE*); bool out_queue(QUEUE*, int*); int main(void) { int val; QUEUE Q; init(&Q); en_queue(&Q, 1); en_queue(&Q, 2); en_queue(&Q, 3); en_queue(&Q, 4); en_queue(&Q, 5); en_queue(&Q, 6); en_queue(&Q, 7); traverse(&Q); out_queue(&Q, &val); printf("出队元素：%d\n", val); out_queue(&Q, &val); printf("出队元素：%d\n", val); traverse(&Q); out_queue(&Q, &val); out_queue(&Q, &val); out_queue(&Q, &val); out_queue(&Q, &val); traverse(&Q); return 0; } void init(QUEUE* q) { q->pBase = (int*)malloc((sizeof(int) * Maxsize)); q->front = 0; q->rear = 0; return; } bool is_full(QUEUE* q) { //这里设定队列中满时有一个元素不用，（rear+1）%size=front时队列满 if ((q->rear + 1) % Maxsize == q->front) return true; else return false; } bool en_queue(QUEUE* q, int val) { if (is_full(q)) { printf("队列已满！入队失败\n"); return false; } q->pBase[q->rear] = val; q->rear++; return true; } bool is_empty(QUEUE* q) { if (q->rear == q->front) return true; else return false; } void traverse(QUEUE* q) { if (is_empty(q)) { printf("队列为空\n"); return; } int i = 0; for (i = q->front; i != q->rear; i = (i+1)%Maxsize) { printf("%d ", q->pBase[i]); } printf("\n"); return; } bool out_queue(QUEUE* q, int* val) { if (is_empty(q)) { printf("队列为空\n"); return false; } *val = q->pBase[q->front]; q->front++; return true; }