一、队列是什么
队列是一种可以实现“先进先出”的存储结构。其实，说简单点，队列就是排队，跟我们日常生活中到银行取钱排队，排队打饭在道理上是一样的。
队列通常可以分为两种类型： ①链式队列（由链表实现）。 ②静态队列（由数组实现），静态队列通常都必须是循环队列。 由于链式队列跟链表差不多，所以在这里只针对循环队列来说明并实践。 循环队列的两个参数： ①front,front指向队列的第一个元素。 ②rear,rear指向队列的最后一个有效元素的下一元素。 队列的两个基本操作：出队和入队。
二、队列的结构
下面是一个循环队列（基于数组实现）的结构图：
三、队列的操作
入队（尾部入队） ①将值存入rear所代表的位置。 ②rear = (rear+1)%数组的长度。 出队（头部出队） front = (front+1)%数组的长度。 队列是否为空 front和rear的值相等，则该队列就一定为空。 队列是否已满 注意：循环队列中，有n个位置，通常放n-1个值，空1个 在循环队列中，front和rear指向的值不相关，无规律。front可能比rear指向的值大，也可能比rear指向的值小，也可能两者相等。 算法： ①多增加一个标识参数。 ②少用一个元素，rear和front指向的值紧挨着，则队列已满。
四、队列的实现
基于数组的循环队列的具体实现
C代码 #include<stdio.h> #include<malloc.h> //包含了malloc函数 /* *循环队列，用数组实现 */ //队列结构体定义 typedef struct Queue { int * pBase; //用于动态分配内存,pBase保存数组的首地址 int front; //指向头结点 int rear; //指向最后一个元素的下一结点 } QUEUE; //函数声明 void initQueue(QUEUE * pQueue); //队列初始化的函数 bool isEmpty(QUEUE * pQueue); //判断队列是否为空的函数 bool isFull(QUEUE * pQueue); //判断队列是否满的函数 bool enQueue(QUEUE * pQueue, int value); //入队的函数 bool outQueue(QUEUE * pQueue, int * pValue); //出队的函数,同时保存出队的元素 void traverseQueue(QUEUE * pQueue); //遍历队列的函数 /* *主程序 */ int main(void) { int value; //用于保存出队的元素 //创建队列对象 QUEUE queue; //调用初始化队列的函数 initQueue(&queue); //调用出队函数 enQueue(&queue, 1); enQueue(&queue, 2); enQueue(&queue, 3); enQueue(&queue, 4); enQueue(&queue, 5); enQueue(&queue, 6); enQueue(&queue, 7); enQueue(&queue, 8); //调用遍历队列的函数 traverseQueue(&queue); //调用出队函数 if(outQueue(&queue, &value)) { printf("出队一次，元素为：%d\n", value); } traverseQueue(&queue); if(outQueue(&queue, &value)) { printf("出队一次，元素为：%d\n", value); } traverseQueue(&queue); getchar(); return 0; } /* *初始化函数的实现 */ void initQueue(QUEUE * pQueue) { //分配内存 pQueue->pBase = (int *)malloc(sizeof(int) * 6); //分配6个int型所占的空间 pQueue->front = 0; //初始化时，front和rear值均为0 pQueue->rear = 0; return; } /* *入队函数的实现 */ bool enQueue(QUEUE * pQueue, int value) { if(isFull(pQueue)) { printf("队列已满,不能再插入元素了!\n"); return false; } else { //向队列中添加新元素 pQueue->pBase[pQueue->rear] = value; //将rear赋予新的合适的值 pQueue->rear = (pQueue->rear+1) % 6; return true; } } /* *出队函数的实现 */ bool outQueue(QUEUE * pQueue, int * pValue) { //如果队列为空,则返回false if(isEmpty(pQueue)) { printf("队列为空，出队失败!\n"); return false; } else { *pValue = pQueue->pBase[pQueue->front]; //先进先出 pQueue->front = (pQueue->front+1) % 6; //移到下一位置 return true; } } /* *遍历队列的函数实现 */ void traverseQueue(QUEUE * pQueue) { int i = pQueue->front; //从头开始遍历 printf("遍历队列：\n"); while(i != pQueue->rear) //如果没有到达rear位置，就循环 { printf("%d ", pQueue->pBase[i]); i = (i+1) % 6; //移到下一位置 } printf("\n"); return; } /* *判断队列是否满的函数的实现 */ bool isFull(QUEUE * pQueue) { if((pQueue->rear+1) % 6 == pQueue->front) //队列满 return true; else return false; } /* *判断队列是否为空函数的实现 */ bool isEmpty(QUEUE * pQueue) { if(pQueue->front == pQueue->rear) return true; else return false; }五、队列的应用
在我们去打饭的时候总要排队，排队是与时间有关的，排在前面的人多，我们打到饭用的时间就比较长，相反，如果前面的排队的人相对较少，我们能打到饭的用的时间也就相对较短，所以说，队列总是与时间相关的。可以肯定地说：任何与时间相关的操作，基本上都会牵扯到队列。
