数据结构之队列(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值均为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;
}

五、队列的应用

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

六、结语

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