/*
=====================================================================
作者：rerli
时间：2004-02-11
目的：学习队列
=====================================================================
*/
/*
队列是从日常排队现象抽象出来的一种数学模型。当然数据结构中的队列
远没有生活中的排队灵活。数据结构中的队列规定：数据只能从队尾进，从队
首出来。已经进入队列的数据次序不能再做改变。这就叫做“先进先出”(FIFO)
或者说“后进后出”(LILO)。允许插入的一端称为队尾，通常用一个称为尾指针
（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删
除的一端称为队首，通常也用一个队首指针（front）指向队首元素的前一个位
置（当然也可以直接指向队首元素，只是许多数据结构的书上都习惯这么定义）。
与队列类似，我们可以用一维数组来模拟队列这种数据结构，也可以用链表
来模拟。
根据以上描述，队列可以整理出以下基本操作：
1、创建初始化：按约定置队列为空状态。
2、入队列：在队尾加入一个新数据项。
3、出队列：从队首取出一个数据项，并使余下诸项向队首移动。
4、队列空：判断队列是否为空。
5、队列满：判断队列是否已满。
从概念上说，队列不存在“满”状态，其长度可以任意增加，
但实现（不论静态或动态）中总有空间限制的。
下面我就来讨论用数组实现队列结构。
假定队列中元素的类型为T,队列的最大长度为queue_size,在任何一刻队列
首、尾位置分别用下标head、tail指向。
队列初始状态应为：head=0,tail=-1。根据队列定义，head值应恒为0，
那么每当出队一个数据项，则必须执行多次移动操作（余下诸项向队首移动）。
显然不能直接采用这种结构实现队列。解决这个问题，可以从数学取模运算联想
到一个解决办法。比如x=(x+1) mod 100 ，则x的变化范围在[0，99]之间，
超过100的又从0，1开始。这不就是我们所需要的嘛！许多书上把它叫作“循环
数组”技术。即当入队列时先移动tail(即tail=(tail+1) mod queue_size)，
出队列时先移动head(即head=(head+1) mod queue_size)。
在移动中，若head(或tail)值为queue_size-1,则移动后head(或tail)的值
就变成0了，对这种特征就是一个环，只要数组有空间，就可以入队列。
用“循环数组”实现队列，必须注意怎样判断队列的空与满的状态。除起始状态
外。任何时刻tail所指为最后一个进入队列的元素，而head所指的是刚刚出队列的
那个元素原先所占的位置。因此(head+1) mod queue_size才是真正当前队列中首元
素位置。
采用条件：(tail+1) mod queue_size == head 作为“队列满”的判断条件。
实际上此时队列中还有一个空位置，这样队列的利用空间比定义的最大空间少一个
单元。假如把这个单元也利用上，则就不好判断“满”或“空”了（当head==tail）
，必须根据是tail追上了head,还是head追上了tail才能区分，这样给处理带来了
不便。
*/
#include <stdlib.h>
#include <stdio.h>
#define NULL 0
typedef struct node
{
int data;
}NODE;
#define LEN sizeof(NODE)
/*队列的需要变量*/
typedef enum {false,true}bool; /*定义bool类型*/
unsigned int head; /*定义队首下标变量*/
unsigned int tail; /*定义队尾下标变量*/
static NODE *queue=NULL; /*定义一个队列*/
static unsigned int queue_size=0;/*队列的大小*/
/*
========================
功能：初始化队列的大小
返回：true or false
========================
*/
bool InitQueue(unsigned int size)
{
queue=(NODE *)malloc(size*LEN); /*开辟空间*/
if (queue==NULL) /*开辟空间失败，则返回false*/
{
return false;
}
queue_size = size; /*保存队列空间大小值*/
head = queue_size-1;/*队首下标赋初值*/
tail = queue_size-1;/*队尾下标赋初值*/
return true; /*初始化成功，返回true*/
}
/*
======================
功能：释放队列的内存
返回：void
======================
*/
void FreeQueue()
{
free(queue);
/*
注意：这一点很重要。free()之后并不能将queue
置为NULL,所以我们一定要自己做。这样能防止产生
“野指针”,即地址不确定的指针。
*/
queue = NULL;
}
/*
==========================
功能：判断队列是否已满
返回：true or false
==========================
*/
bool Full()
{
return (((tail+1)%queue_size)==head);
}
/*
===========================
功能：判断队列是否为空
返回：true or false
===========================
*/
bool Empty(){
return (head==tail);
}
/*
========================
功能：入队列
返回：true or false
========================
*/
bool Push(NODE p)
{
if (!Full()) /*队列不满，则入队列；队尾下标要加1*/
{
tail = (tail+1)%queue_size;
queue[tail] = p;
return true;
}
else
{
printf("queue is overflow !\n");
return false;
}
}
/*
===================
功能：出队列
返回：出队列元素指针
===================
*/
NODE *Pop()
{
if (!Empty()) /*队列不空，则出队列；队首下标要加1*/
{
head = (head+1)%queue_size;
return (&queue[head]);
}
else
{
printf("queue is empty !\n");
return NULL;
}
}
void main(void)
{
NODE node1 = {3};
NODE *p;
if (!InitQueue(3)) /*初始化不成功，则退出*/
{
exit(0);
}
Push(node1);
/*去掉下面的注释，你可以验证讲解中空间利用问题*/
/*
Push(node1);
Push(node1);
Push(node1);
*/
p =Pop();
printf("%d",p->data);
FreeQueue(); /*注意程序退出时释放队列内存*/
printf("\n");
system("pause");
}
