数据结构之队列(C实现)

?

?

??? 队列是一种可以实现“先进先出”的存储结构。其实，说简单点，队列就是排队，跟我们日常生活中到银行取钱排队，排队打饭在道理上是一样的。

??? 队列通常可以分为两种类型：
?????? ①链式队列（由链表实现）。
?????? ②静态队列（由数组实现），静态队列通常都必须是循环队列。
??? 由于链式队列跟链表差不多，所以在这里只针对循环队列来说明并实践。
??? 循环队列的两个参数：
?????? ①front,front指向队列的第一个元素。
????? ?②rear,rear指向队列的最后一个有效元素的下一元素。
??? 队列的两个基本操作：出队和入队。

??? 下面是一个循环队列（基于数组实现）的结构图：

???

????? 入队（尾部入队）
??????????? ①将值存入rear所代表的位置。
??????????? ②rear = (rear+1)%数组的长度。
????? 出队（头部出队）
??????????? front = (front+1)%数组的长度。
????? 队列是否为空??
??????????? front和rear的值相等，则该队列就一定为空。
????? 队列是否已满
??????????? 注意：循环队列中，有n个位置，通常放n-1个值，空1个
??????????????????? 在循环队列中，front和rear指向的值不相关，无规律。front可能比rear指向的值大，也可能比rear指向的值小，也可能两者相等。
??????????? 算法：
??????????? ①多增加一个标识参数。
??????????? ②少用一个元素，rear和front指向的值紧挨着，则队列已满。

??? 基于数组的循环队列的具体实现

???

#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值均为0pQueue->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){//如果队列为空,则返回falseif(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;elsereturn false;}/* *判断队列是否为空函数的实现 */bool isEmpty(QUEUE * pQueue){if(pQueue->front == pQueue->rear)return true;elsereturn false;}

?

?

?????在我们去打饭的时候总要排队，排队是与时间有关的，排在前面的人多，我们打到饭用的时间就比较长，相反，如果前面的排队的人相对较少，我们能打到饭的用的时间也就相对较短，所以说，队列总是与时间相关的。可以肯定地说：任何与时间相关的操作，基本上都会牵扯到队列。

????? 最后再声明一下：附件中的工程是在Visual Studio 2010 中建的。

?