第2章第2节队列-数据结构与算法

关于队列的基本定义已经在第2章栈和队列以及串中说到了，与栈类似，同样有使用顺序结构存储的队列（这里简称顺序队列）和链式结构存储的队列（这里简称链队列）。

一. 顺序队列

1.1定义

队列的顺序实现是指分配一块连续的存储单元用于存放队列中的元素，并附设两个指针front和rear分别指示头元素和队尾元素。设队头指针指向队头元素的位置，队尾指针指向队尾元素的下一个位置。

队列的顺序存储类型则可以描述为：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

这里对顺序队列的判断条件进行说明。

队空条件：Q.front==Q.rear==0

队满条件：> ~~Q.rear==MaxSize~~

这里应当注意到，上述判断队满条件实际是不正确的，比如当front指向队尾元素，而rear的值刚好等于MaxSize。
此时从data[0]到data[MaxSize−2]的所有元素中，均没有存储任何元素，但是根据上述判断条件却“已满”，造成“假溢出”。
为了解决这个问题，常见的有两种解决方法。

将队列元素向前“平移”重新占用0至rear-front-1的空间

将队列看成首尾相连的循环队列

因为平移会浪费大量的无用时间，因此一般使用循环队列解决判断是否队满的问题。

二.循环队列

2.1定义

循环队列将一个顺序队列“臆造”成一个环状的空间，即把存储队列元素的表从逻辑上看成一个环，物理上依旧使用顺序存储结构。
在引入循环队列的同时，也引入判断队列是否为空或满的三种常见方法。

1). 牺牲一个单元来区分队空和队满

队空条件：Q.front==Q.rear

队满条件：(Q.rear+1)%MaxSize==Q.front

队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize

2). 增设表示元素个数的数据成员size

队空条件：Q.size==0
队满条件：Q.size=MaxSize
队列中元素的个数：Q.size

3). 增设数据成员标志tag

队空条件：Q.tag==0&&Q.front==Q.rear
队满条件：Q.tag==1&&Q.front==Q.rear

2.2基本操作

初始化操作，完成对队首指针和队尾指针的复位操作。

void InitQueue(SqQueue* Q)
{
    Q->front=0;
    Q->rear=0;
}

入队操作，因为队列中规定队尾指针指向队尾元素的下一个位置，因此在入队后需对队尾指针自增1。

int EnQueue(SqQueue* Q, ElemType x)
{
    if((Q->rear+1)%MaxSize==Q->front){
        return -1;
    }
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MaxSize;
    return 0;
}

出队操作，如果队空则返回-1；否则返回数据元素。

int DeQueue(SqQueue* Q, ElemType* x)
{
    if(Q->rear==Q->front){
        return -1;
    }
    *x=Q->data[Q->front];
    Q->front=(Q->front+1)%MaxSize;
    return 0;   
}

判断队列是否为空，若为空则返回0；否则返回-1。

int QueueEmpty(SqQueue* Q)
{
    if(Q->rear==Q->front){
        return 0;
    }else{
        return  -1;
    }
}

三.链队列

3.1定义

采用单链表结构存储的队列称为链队列。它同时带有指向队头结点的指针点和指向队尾结点的尾结点，一般为了方便在队头取出元素和在队尾中添加元素，故一般采用待有头节点的单链表。
如图所示：

这里对链队列的判断条件进行说明。

队空条件：Q.front==Q.rear

队列的链式存储类型则可以描述为：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
typedef struct{
    LNode *front;
    LNode *rear;
}LinkQueue;

链队特别适合元素数据变化比较大和需要同时使用多个队列的情形，因为不会存在由于队满而溢出的问题。

3.2基本操作

初始化操作。

void InitQueue(LinkQueue *Q)
{
    Q->front=(LNode*)malloc(sizeof(LNode));
    Q->rear=Q->front;
    Q->front->next=NULL;
}

判断队列是否为空，如若为空，则返回0；否则返回-1。

int QueueEmpty(LinkQueue *Q)
{
    if(Q->front==Q->rear){
        return 0;
    }else{
        return -1;
    }
}

入队操作，创建新的结点，然后插入队尾

void EnQueue(LinkQueue *Q, ElemType x)
{
    LNode *s;
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;
    Q->rear->next=s;
    Q->rear=s;
}

出队操作，如果队列为空，则返回-1；若不为空，则返回0。

int DeQueue(LinkQueue *Q, ElemType *x)
{
    LNode *p;
    if(Q->front==Q->rear){
        return -1;
    }
    p=Q->front->next;
    *x=p->data;
    Q->front->next=p->next;
    if(Q->rear==p){
        Q->rear=Q->front;
    }
    free(p);
    return 0;
}

四.双端队列

4.1定义

双端队列是允许两端都可以进行入队和出队操作的队列。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论前端还是后端出队，先出的元素排列在后出的元素的前面。如下图所示：

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。如下图所示：

输出受限的双端队列

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列，而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。如下图所示：

输入受限的双端队列