队列原理及C语言实现

一、队列的定义

队列这词源自于生活，例如超市排队、食堂排队等都是一个队列。

二、队列的特征

既然队列来源于生活，那自然也具有生活中这些队列的属性了。

想象一个正在排队的超市队列，那么队列中的成员就是正在排队的人，那么对于这个队列，就得遵守以下的规则：

1、对于新增加的成员，必须在队列尾部。（类比超市队列，就是新来的人必须排在队尾）

2、取出队列中的成员，必须在队列头部。（类比超市队列，正在结账的肯定是当前队列头部的人）

三、队列支持的操作

1、创建一个队列

Queue* createQueue()  

2、队列是否为空

bool  isQueueFull()   3、往队列中新增一个成员 void enQueue()   4、获取队列头部成员 TYPE *queryQueueHead()   // TYPE为队列成员类型   5、从队列中删除一个成员，即删除头部成员 void  deQueue()   提供以上这些方法，一个队列就算完成了。   四、队列的实现 由于C语言没有动态数组，所以队列大小需要考虑，具体实现如下：   typedef struct {     int size; // 队列大小     int number; // 队列中的元素个数     int *queue; // 队列地址     int frontIndex; // 队列头部元素索引值     int rearIndex;  // 队列尾部元素索引值 } MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj)  {     if(obj->number == 0)     {         return true;     }     return false; }
bool myCircularQueueIsFull(MyCircularQueue* obj)  {     if(obj->number == obj->size)     {         return true;     }     return false; }
MyCircularQueue* myCircularQueueCreate(int k)  {     MyCircularQueue *mQueue = malloc(sizeof(MyCircularQueue));     if(mQueue == NULL)     {         return NULL;     }     mQueue->queue = malloc(sizeof(int) * k);     if(mQueue->queue == NULL)     {         free(mQueue);         return NULL;     }     mQueue->size = k;     mQueue->number = 0;     mQueue->frontIndex = -1;     mQueue->rearIndex = -1;     return mQueue; }
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)  {     if(myCircularQueueIsFull(obj))     {         return false;     }     if(myCircularQueueIsEmpty(obj))     {         obj->queue[0] = value;         obj->number++;         obj->frontIndex = 0;         obj->rearIndex = 0;         return true;     }     obj->rearIndex = (obj->rearIndex + 1) % obj->size;     obj->queue[obj->rearIndex] = value;     obj->number++;     return true; }
bool myCircularQueueDeQueue(MyCircularQueue* obj)  {     if(myCircularQueueIsEmpty(obj))     {         return false;     }     obj->frontIndex = (obj->frontIndex + 1) % obj->size;     obj->number--;     return true; }
int myCircularQueueFront(MyCircularQueue* obj)  {     if(myCircularQueueIsEmpty(obj))     {         return -1;     }     return obj->queue[obj->frontIndex]; }
int myCircularQueueRear(MyCircularQueue* obj)  {     if(myCircularQueueIsEmpty(obj))     {         return -1;     }     return obj->queue[obj->rearIndex]; }
void myCircularQueueFree(MyCircularQueue* obj)  {     free(obj->queue);     free(obj); }