[[2023.12.29#栈和队列]] 队列只能在一端插入（入队），在另一端删除（出队），遵循先进先出（FIFO）

顺序存储实现

由一个一维数组和记录队头尾元素位置的变量front rear组成。 普通队列： 入队的时候，向数组末尾添加元素，rear++ 出队的时候，数组头部删除元素，front++ 这样的话空间利用效率较低，故使用循环队列改进。

循环队列

由于循环队列的特殊性，队列满和队列空的情况下都满足$rear=front$，这时候可以通过一个技计数变量或者状态标记（记录最后一次操作是插入还是删除）来判断，或者为队列分配$n$个空间但只使用$n-1$个空间来避免出线前后指针相等的情况（如上图，此时认为队列已满）。

入队

void AddQ(Quene PtrQ,ElementType item){
    if((PtrQ->rear+1) % MaxSize == PtrQ->front){
        printf("full");
        return;
    }
    PtrQ->rear = (PtrQ->rear+1) % MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

实现循环队列，需要用到求余运算。例如一个下标0-5的数组，5的下一项就是$5+1mod6=0$。

出队

ElementType DeleteQ(Quene PtrQ){
    if(PtrQ->front == PtrQ->rear){
        printf("empty");
        return ERROR;
    }else{
        PtrQ->front = (PtrQ->front+1) % MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

通过出入队时的取余操作，可以实现前后指针始终指向分配的内存空间。

链式存储实现

通过单链表实现。

数据结构

struct Node{
    ElementType Data;
    struct Node *Next;
};

struct QNode{
    struct Node *rear;
    struct Node *front;
};

typedef struct QNode *Quene;
Quene PtrQ;

front rear永远指向链表的头尾。

出队

ElementType DeleteQ(Quene PtrQ){
    struct Node *FrontCell;
    ElementType FrontElem;
    if(PtrQ->front == NULL){
        printf("empty");
        return ERROR;
    }
    FrontCell = PtrQ->front;
    if(PtrQ->front == PtrQ->rear){//只有一个元素
        PtrQ->front = PtrQ->rear = NULL;
    }else{
        PtrQ->front = PtrQ->front->Next;
    }
    FrontElem = FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}

入队

略

双端队列

STL 提供了双端队列的模板：

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    deque<int> a;
    a.push_back(5);
    a.push_front(1);
    return 0; 
}