队列

队列的定义

队列简称（queue）队，是一种受限的线性表

只允许在表的一端插入，在另一端删除

队头(Front)：允许删除一端

队尾(Rear)：允许插入的一端

空队列： 不含任何数据元素的空表

插入简称入队，删除称为出队，遵循先进先出原则（First In First Out，FIFO）

队列的基本操作

方法 作用
InitQueue( &q) 构造一个队列
QueueEnpty(q) 判断队列是否为空，是返回TRUE,否则FALSE
EnQueue(q, &x) 入队，若q未满，加入新的x作为队尾
DeQueue(q, &x) 出队，若q非空，删除队头元素，返回x
GetHead(q, &x) 读取队头元素，若q非空，则把队头元素赋给x

注意：队列和栈作为受限的线性表，不能任意读取队列或栈中的元素

偷懒，截取的网页原文

队列的链式存储结构

队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称为链队列。

1
2
3
4
typedef struct QNode {
ElemType data;
struct QNode *next;
} QNode, *QueuePrt;

将队头指针指向链队列的头结点，而队尾指针指向终端结点。（注：头结点不是必要的，但为了方便操作，我们加上了。）

队列的链式存储结构

空队列时，front和rear都指向头结点。

创建一个队列

创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列。

1
2
3
4
5
6
7
initQueue(LinkQueue *q)
{
    q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
    if( !q->front )
        exit(0);
    q->front->next = NULL;
}

入队列操作

1
2
3
4
5
6
7
8
9
10
11
12
13
//入队列操作 
InsertQueue(LinkQueue *q, ElemType e){
QueuePtr p;
 
p = (QueuePtr)malloc(sizeof(QNode));
if( p == NULL )
exit(0);
 
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}

出队列操作

出队列操作是将队列中的第一个元素移出，队头指针不发生改变，改变头结点的next指针即可。

如果原队列只有一个元素，那么我们就应该处理一下队尾指针。

出队列操作

1
2
3
4
5
6
7
8
9
10
DeleteQueue(LinkQueue *q, ELemType *e)
{
QueuePtr p;
if( q->front == q->rear )
return; 
p = q->front->next;
*e = p->data;q->front->next = p->next;
if( q->rear == p )q->rear = q->front;
free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它及时销毁掉，以免过多地占用内存空间。

1
2
3
4
5
6
7
8
sDestroyQueue(LinkQueue *q){
while( q->front ) 
{
q->rear = q->front->next;
free( q->front );
q->front = q->rear;
}
}

队列的顺序存储结构

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的存储单元，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端则是队头。

入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。

出队列则不同，因为我们已经架设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。

在现实中也是如此，一群人在排队买火车票，前边的人买好了离开，后面的人就要全部向前一步补上空位。

可是我们研究数据结构和算法的一个根本目的就是要想方设法提高我们的程序的效率，按刚才的方式，出队列的时间复杂度是O(n)，效率大打折扣！

如果我们不去限制队头一定要在下标为0的位置，那么出队列的操作就不需要移动全体元素。

但是这样也会出现一些问题，例如按下边的情形继续入队列，就会出现数组越界的错误。

可事实上我们有0和1两个下标还空着，这叫假溢出。

循环队列

我们再想想，要解决假溢出的办法就是如果后面满了，就再从头开始，也就是头尾相接的循环。

循环队列它的容量是固定的，并且它的队头和队尾指针都可以随着元素入、出队列而发生改变，这样循环队列逻辑上就好像是一个环形存储空间。

但要注意的是，在实际的内存当中，不可能有真正的环形存储区，我们只是用顺序表模拟出来的逻辑上的循环。

于是我们发觉了，似乎循环队列的实现只需要灵活改变front和rear指针即可。

也就是让front或rear指针不断加1，即使超出了地址范围，也会自动从头开始。我们可以采取取模运算处理：（这个运算在数据结构中特别常见，也特别重要！）

(rear+1) % QueueSize

(front+1) % QueueSize

取模就是取余数的意思，他取到的值永远不会大于除数。

定义一个循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MAXSIZE 100
typedef struct
{
    ElemType *base; // 用于存放内存分配基地址，这里你也可以用数组存放
int front;int rear;
}
初始化一个循环队列
    initQueue(cycleQueue *q){
    q->base = (ElemType *) malloc (MAXSIZE * sizeof(ElemType));
       if( !q->base )  
           exit(0); 
    q->front = q->rear = 0;
}
入队列操作
    InsertQueue(cycleQueue *q, ElemType e)
{
    if( (q->rear+1)%MAXSIZE == q->front )
        return; // 队列已满 
    q->base[q->rear] = e;
    q->rear = (q->rear+1) % MAXSIZE;
}
出队列操作
    DeleteQueue(cycleQueue *q, ElemType *e)
{
    if( q->front == q->rear )
        return ; // 队列为空 
    *e = q->base[q->front];
    q->front = (q->front+1) % MAXSIZE;
}