C语言数据结构之队列篇

定义 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性

先进先出(FIFO, First In First Out)

ADT Queue { //对象:由数据类型为QueueData的元素构成    int EnQueue (Queue *Q, QueueData x);   //进队    int DeQueue (Queue *Q, QueueData &x);//出队    int GetFront (Queue *Q, QueueData &x);//取队头    void InitQueue (Queue *Q);        //置空队    int QueueEmpty (Queue *Q);      //判队空否    int QueueFull (Queue *Q);          //判队满否 }

队列的进队和出队原则

进队时队尾指针先进一  rear = rear + 1，再将新元素按 rear 指示位置加入。  出队时队头指针先进一 front = front + 1，再将下标为 front 的元素取出。  队满时再进队将溢出出错；  队空时再出队将队空处理。  解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。 

循环队列

队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从QueueSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1:  front = (front+1) % QueueSize; 队尾指针进1:  rear = (rear+1) % QueueSize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear+1) % QueueSize == front 

队列的链接表示——链式队列

队头在链头，队尾在链尾。 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front == NULL

下面是关于链式队列的一些基本操作

#include "LinkQueue.h" #include <stdlib.h> Queue* Create_Queue() { Queue * q = (Queue*)malloc(sizeof(Queue)/sizeof(char)); if (q == NULL) { errno = MALLOC_ERROR; return NULL; } // 置空队 q->front = NULL; q->rear  = NULL; return q; } int QueueEmpty (Queue *q) { if (q == NULL) { return FALSE; } return q->front == NULL; } int EnQueue (Queue *q, QueueData x) { if (q == NULL) { errno = ERROR; return FALSE; } Node * node = (Node*)malloc(sizeof(Node)/sizeof(char)); if (node == NULL) { errno = MALLOC_ERROR; return FALSE; } node->data = x; node->next = NULL; if (q->front == NULL) { q->front = node; q->rear  = node; } else { q->rear->next = node; q->rear = node; } return TRUE; } int DeQueue (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } Node *p = q->front; *x = p->data; q->front = p->next; free(p); if (q->front == NULL) q->rear = NULL; return TRUE; } int GetFront (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } *x = q->front->data; return TRUE; } int Destroy_Queue (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } int x; while (QueueEmpty(q) != TRUE) { DeQueue(q, &x); } free(q); return TRUE; }