数据结构之队列 | 柳暗花明来真村

与栈相反，队列是一种先进先出的线性表，它只允许在表的一端进行，而在另一端删除元

素。

在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

1、链队列——队列的链式表示和实现

用链表表示的队列简称为链队列，一个链队列显然需要两个分别指示对头和队尾的指针

（分别称为头指针和尾指针）才能唯一确定。这里，和线性表的单链表一样，为了操作方便起

见，我们也给队列添加一个头结点。

链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。

单链队列——队列的链式存储结构，如下所示。

//单链队列，队列的链式存储结构
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;

2、单链队列的C语言操作

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define OK 1
#define ERROR 0
//单链队列，队列的链式存储结构
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
//构造一个空队列
int InitQueue(LinkQueue *q)
{
//
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
if(q->front == NULL)
{
fprintf(stderr, "malloc() error.\n");
return ERROR;
}
q->front->next = NULL;
q->rear->next = NULL;
return OK;
}
//销毁队列，Q不在存在
int DestroyQueue(LinkQueue *q)
{
//
while(q->front)
{
q->rear = q->front->next;
free(q->front);
q->front = q->rear;
}
return OK;
}
//判断队列是否为空
int IsEmptyQueue(LinkQueue *q)
{
return (q->front->next == NULL && q->rear->next == NULL);
}
//插入元素e为新的队尾元素
int InsertQueue(LinkQueue *q, ElemType e)
{
//
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if(p == NULL)
{
fprintf(stderr, "malloc() error.\n");
return ERROR;
}
p->data = e;
p->next = NULL;
//如果队列为空
if(IsEmptyQueue(q))
{
q->front->next = p;
q->rear = p;
}
else
{
q->rear->next = p;
q->rear = p; //不要忘记这句啊
}
return OK;
}
//若队列不空，则删除队头元素，用e返回其值，并返回OK
int DeQueue(LinkQueue *q, ElemType *e)
{
//
if(IsEmptyQueue(q))
{
fprintf(stdout, "the queue is null.\n");
return ERROR;
}
//注意有队头结点
QueuePtr temp;
temp = q->front->next;
*e = temp->data;
q->front->next = temp->next;
//一个元素
if(q->rear == temp)
{
q->rear = q->front;
}
free(temp);
return OK;
}
//打印队列
void printQueue(LinkQueue *q)
{
QueuePtr temp;
temp = q->front->next;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
int main(int argc, char **argv)
{
LinkQueue *q;
InitQueue(q);
srand(time(NULL));
int i = 0;
for(i = 0; i < 10; i++)
{
InsertQueue(q, i);
}
printf("插入队列的元素为:\n");
printQueue(q);
int e;
DeQueue(q, &e);
printf("队头元素为: %d\n", e);
return 0;
}

3、循环队列定义

单链队列时，当队列为空时，front等于rear，现在循环队列当队列满时，也是front等

rear，那么如何判断此时的队列究竟是空还是满呢？

办法一是设置一个标志变量flag，当front == rear，且flag = 0时为队列空，当front

==rear，且flag = 1时为队列满；

办法二是当队列空时，条件就是front == rear，当队列为满时，我们修改其条件，保留一

个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如下图所示，我们就认为此

队列已经满了，也就是说，我们不允许下图中的右图情况出现。

我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以，尽管它

们只相差一个位置时就说满的情况，但也有可能是相差整整一圈。所以，若队列的最大尺寸为

QueueSize，那么队列满的条件是(rear + 1) % QueueSize == front（取模"%"的目的就说为

了整合rear与front大小为一个问题)。比如上面这个例子，QueueSzie = 5，上图中的左图中

front = 0，而rear = 4，（4 + 1） % 5 = 0，所以，此时队列满。再看右图，front = 2，

而rear = 1，(1 + 1) %5 = 2，所以，此时队列也是满的。但是也有例外的情况。

另外，通用的计算队列长度的公式为：(rear - front + QueueSize) % QueueSize

循环队列的顺序存储结构，如下所示。

#define ElemType int
typedef struct
{
ElemType data[MAXSIZE];
int front; //头指针
int rear; //尾指针，若队列不为空时，rear指向队列尾元素的下一个位置
}SqQueue;

4、循环队列的C操作

#define ElemType int
#define MAXSIZE 100
typedef struct
{
ElemType data[MAXSIZE];
int front; //头指针
int rear; //尾指针，若队列不为空时，rear指向队列尾元素的下一个位置
}SqQueue;
#define OK 1
#define ERROR 0
//初始化一个空队列
int InitQueue(SqQueue *q)
{
q->front = 0;
q->rear = 0;
return OK;
}
//循环队列求队列长度
//返回队列的元素的个数，也就是队列的当前长度
int QueueLength(SqQueue *q)
{
return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
//循环队列的入队操作
//若队列未满，则插入元素e为队列新的队尾元素
int EnQueue(SqQueue *q, ElemType e)
{
if((q->rear + 1) % MAXSIZE == q->front) //队列满的判断
{
return ERROR;
}
q->data[q->rear] = e; //将元素e赋值给队尾
q->rear = (q->rear + 1) MAXSIZE; //rear指向后移一位置，若到最后则转为数组头部
//注意
return OK;
}
//循环队列的出对操作
//若队列不空，则删除q中队头元素，用e返回值
int DeQueue(SqQueue *q, ElemType *e)
{
if(q->rear == q->front) //队列空的判断
{
return ERROR;
}
*e = q->data[q->front]; //将队头元素赋值给e
q->front = (q->front + 1) % MAXSIZE;//front指针向后一位置，若到最后，则转到数组头部
return OK;
}

参数：严蔚敏老师之《数据结构》、《大话数据结构》

梦醒潇湘love

2013-01-12 19:37