队列

队列的基本概念

队列是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除；向队列中插入元素称为入队或者进队，删除元素称为出队或者离队；队列的操作特性是先进先出

队头：允许删除的一端，又称为队首
队尾：允许插入的一段
空队列：不含任何元素的空表

队列常见的基本操作

队列常见的基本操作主要有构造一个空队列InitQueue(&Q)、判断队列为空QueueEmpty(Q)、入队EnQueue(&Q,x)、出队DeQueue(&Q,&x)、读队头元素GetHead(Q,&x)

需要注意的是，队列是操作受限的线性表，因此不是所有对线性表的操作都可以作为队列的操作，比如，不可以随便读取队列中间的某个数据

队列的顺序存储结构

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

#define MaxSize 50      //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];
    int front,rear;     //定义队头指针和队尾指针
} SqQueue;

初始条件（队空条件）：Q.front = 0,Q.rear = 0（队尾的下一个位置等于0，即队尾位置等于-1，队列为空
进队操作：队列不满时，先送值到队尾元素，再将队尾指针加一
出队操作：队列不为空时，先弹出队头元素值，再将队头指针加一

d注意：Q.rear == MaxSize并不能作为队列已满的条件，因为即使经过多次的进队、出队，即使队尾指针Q.rear已经达到了MaxSize的位置，但是队头指针同样可能变化，使队头发生后移，导致data数组中仍然存在可以存放元素的空位置，实际上是一种“假溢出”，这也是顺序队列的一种缺点。

循环队列

前面说，顺序队列的缺点是对队头元素的删除操作会导致data数组中仍然存在未被利用的队头空间，甚至出现“假溢出现象”，循环队列解决了这种问题；将顺序队列臆造成为一个环状的空间，即把存储队列的线性表从逻辑上视为一个环，称为循环队列。

在循环队列中，当队首指针为MaxSize-1时，其下一个位置为0；循环队列依靠除法的取余操作实现。

初始时：头结点的位置指针Q.front=0，指向尾结点下一个元素位置的指针Q.rear=0
队首指针进1：Q.front=(Q.front+1)%MaxSize
队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
队列长度：(Q.rear+MaxSize-Q.front)%MaxSize (保证正数？？？)
出队入队时，指针都向顺时针方向加1

判断循环队列队满或者队空时会发现，循环队列队空的条件为Q.front==Q.rear，和普通队列一致；但循环队列队满时，由于Q.rear指向队末元素的下一个位置，条件仍然是Q.front==Q.rear，因此为了区分队空还是队满，有几种处理方式；

1.牺牲一个单元来区分队空和队满，入队时少用一个队列单元；约定以队头指针指向队尾指针指向的下一个位置作为队满的标志；

队满条件：（Q.rear+1)%MaxSize==Q.front
队空条件：Q.rear==Q.front
队列中元素的个数Q.rear-Q.front+MaxSize)%MaxSize(当Q.rear-Q.front为正数时，和Q.rear-Q.front等价；当Q.rear越过0的位置，变成一个小于Q.front的值时，加上MaxSize使整个值非负，便于取余数)

2.类型中新增表示元素个数的数据成员Q.size，无视Q.rear==Q.front这一判别条件；这样循环队列的判空条件为Q.size==0，队满的判定条件为Q.size==MaxSize-1；对于这两种情况，都有Q.rear==Q.front

3.类型中增加Q.tag成员，通过记录导致Q.rear==Q.front的原因区分队满还是队空；若因删除导致Q.rear==Q.front，则为队空，记录为tag等于0；若因插入导致Q.rear==Q.front，则为队满，记录为tag等于1

循环队列的操作

初始化

void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;  //初始化队首、队尾指针为0
}

判队空

bool isEmpty(SqQueue Q){
    if (Q.rear == Q.front)  //队空条件
        return true;
    else
        return false;
}

入队

bool EnQueue(SqQueue &Q,ElemType x){
    if ((Q.rear + 1)%MaxSize == MaxSize)
        return false;
    Q.data[Q.rear] = x; //原指针指向的是下一个应该填充的位置
    Q.rear = (Q.rear + 1)%MaxSize;  //为了防止进入下个周期而大于MaxSize
    return true；
}

出队

bool DeQueue(SqQueue &Q,ElemType x){
    if(Q.rear == Q.front)
        return true;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

队列的链式存储结构

队列的链式表示称为链队列，它实际上是一个带有头指针和尾指针的单链表；头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点

注意：在队列的顺序存储中，尾指针指向队尾元素的下一个结点；而在队列的链式存储结构中，尾指针指向的是队尾元素所在的结点

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

typedef struct{     //链式队列的结点
    ElemData data;
    struct LinkNode *next;
}LinkNode;

typedef struct{     //链式队列本身
    LinkNode *front,*next;  //队列的队头和队尾指针
}LinkQueue;

当队列的队头指针Q.front == NULL和队尾指针Q.next == NULL时，链式队列为空

出队时，首先判断队是否为空；如果不为空，则将其从链表中摘除，并且使Q.front指向下一个结点（若该结点为最后一个结点，则将Q.front和Q.next都设为NULL；入队时，建立一个新结点，将新结点插入链表的尾部，并让Q.rear指向这个新插入的结点（若原队列为空，则令Q.front也指向这个结点）

因此，不带头节点的链式队列由于存在为空的可能，因此操作上比较麻烦；因此通常将链式队列设计成带头结点的单链表，这样插入和删除操作能得到统一

用单链表表示的链式队列适合数据元素变动比较大的情形，而且不存在队列满产生溢出的问题；而且如果程序中需要使用多个队列，最好使用链式队列，这样不会出现存储分配不合理和“溢出”的情形

链式队列的操作

链式队列的初始化

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear=(LinkNode *)malloc(sizeof(LinkNode));  //建立头结点
    Q.front->next = NULL;   //初始为空
}

判链式队列为空

bool IsEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

入队操作

void EnQueue(LinkQueue &Q,Elemtype x){
    //不用判断是否为满，因为链式队列不会满
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

出队操作

bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;   //判断链式队列是否为空
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;   //如果原队列只有一个结点，则删除后队列为空
    free(p);
    return true;
}

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列；其元素的结构仍然是线性结构，将队列的两端分别称为前端和后端；两端都可以出队或者入队

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许进行插入

输入受限的双端队列：允许在一段进行插入和删除，但在另一端只允许进行删除

若限定双端队列从某个端点插入的元素只能从该端点进行删除，则该双端队列退化成两个栈底相临接的栈

考研数据结构笔记——3.队列