$\Huge\color{orchid}{点击此处获取更多干货}$

两种方式实现

队列的存取点限制在了线性表的头端和尾端，虽然分散在了两处，但是队列的插入和删除都是仅限一端的（插入在尾端，删除在头端），访问内部元素一般来说只能访问头端（STL中的queue可以访问尾端）。和栈相反，如果将元素$\{1,2,3,4,5\}$插入队列，完毕后按序删除，则删除序列和插入序列是相同的$\{1,2,3,4,5\}$，因此队列是一种先进先出（FIFO）型数据结构。

队列还有个和栈不同的地方就是，如果允许一边插入一边删除，那么对于某入栈序列来说，其产生的出栈序列有多种可能性（如$\{1,2,3\}$的入栈序列，会产生$\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,2,1\}$五种出栈序列，不同出栈序列的总数叫做卡特兰数），但是同样的入队序列，只有可能产生与其相同的$\{1,2,3\}$一种出队序列（以上两点可自行推导验证）

以上所说队列都仅限尾端插入头端删除的普通队列，实际上“队列”这个概念是个总称，包含上述的普通队列，两端都可自由插入删除的双端队列（也就是STL的deque），并在双端队列的基础上还有输入受限（两端输出一端输入）和输出受限（两端输入一段输出）的特殊双端队列。除此以外，还有能按照优先级自动排序的优先队列（这个之后会提到）

C++ 代码

普通队列和栈一样，也可以用顺序存储和链式存储两种方式实现，下面给出模板类，原理和细节见注释

//顺序结构
template<class Elem>
class SequenceQueue {
private:
    Elem* base;
    //队列有队头(head)和队尾(tail)两个指针作为存取控制点
    size_t head, tail;
public:
    SequenceQueue() {
        base = new Elem[cntCmd];
        tail = head = 0ull;//初始都为0
    }

    ~SequenceQueue() {
        delete[] base;
    }

    //插入
    void push(Elem e) {
        //tail指向当前可插入的位置，插入之后要后移tail
        base[tail++] = e;
    }

    //判空
    bool empty() {
        //头尾相遇则为空
        return head == tail;
    }

    //删除和取队头都需要保证非空，否则抛出异常

    //删除
    void pop() {
        if (empty()) {
            throw logic_error("front() called on an empty deque");
        }
        //直接后移head即可
        head++;
    }

    //取队头
    Elem front() {
        if (empty()) {
            throw logic_error("front() called on an empty deque");
        }
        //head处可直接取得队头元素
        return base[head];
    }
};

//链式结构
template<class Elem>
class LinkedQueue {
private:
    //使用双向循环链表，表头固定tail指针，head指针的val就是队头元素，规定tail->next = head
    Node<Elem>* head, * tail, * del;
public:
    LinkedQueue() {
        //先有一个tail，前驱后继都指向自己
        tail = new Node<Elem>(Elem(-1e9));
        tail->next = tail->prev = tail;
        //head初始指向tail（空队列）
        head = tail;
        del = nullptr;
    }

    ~LinkedQueue() {
        if (head != nullptr) {
            del = head;
            head = head->next;
            head->prev = nullptr;
            del->next = nullptr;
            delete del;
            del = nullptr;
        }
    }

    //插入
    void push(Elem e) {
        //具有固定的队尾节点，只需要在此之前插入节点即可
        Node<Elem>* cur = new Node<Elem>(e, tail->prev, tail);
        tail->prev->next = cur;
        tail->prev = cur;
        //如果原先是空队列，那么需要将head移到当前插入的节点处
        if (head == tail) {
            head = tail->prev;
        }
    }

    //判空
    bool empty() {
        //同样头尾相遇为空
        return head == tail;
    }

    //删除
    void pop() {
        if (empty()) {
            throw logic_error("front() called on an empty list");
        }
        del = head;
        //后移head
        head = head->next;
        //按照双向链表的方式删除原队头节点
        Node<Elem>* pr = del->prev, * nx = del->next;
        pr->next = nx;
        nx->prev = pr;
        del->next = del->prev = nullptr;
        delete del;
        del = nullptr;
    }

    //取队头
    Elem front() {
        if (empty()) {
            throw logic_error("front() called on an empty list");
        }
        return head->val;
    }
};