队列是线性表的一种特殊形式‌，所有排队场景都是一个队列，记录访问顺序时也经常用到队列。
栈也是线性表的一种特殊形式‌，递归函数的运行过程、算术表达式的处理过程都会用到栈。

队列(queue)是线性表的一种特殊形式‌，其遵循先进先出(FirstInFirstOut，FIFO)的原则。
与顺序表不同，队列的插入和删除操作是固定在队尾与队头进行的，顺序队列实际上是运算受限的顺序表。
队列有两个关键位置:队尾和队头。队尾是允许执行插入操作的位置，而队头是允许执行删除操作的位置。刚开始时，队列是空的，没有任何元素。
例如，在超市购物时，需要结账的顾客加入队列的队尾，也就是新插入的元素成为队尾元素。一个顾客结完账就离开了，排在最前面的顾客就可以开始结账，该顾客就是当前队头元素。这种方式保证了先来的顾客先离开队列，体现了先进先出的原则。队列不允许“插队”因此不允许在队尾以外的其他地方插入元素，也不允许删除其他位置的元素。队列中排队的人数称为队列的长度，当队列中没有顾客时，称为空队列。

这种先进先出的特性使得队列非常适合用来管理需要按照顺序处理的任务，例如打印机的打印任务、消息传递系统中的消息处理任务等。

队列的基本操作

• 创建队列。create()：创建一个空队列。
• 入队。push(x)：将元素x插入队尾，使之成为队尾元素。
• 出队。pop()：删除队头元素并返回队头元素值。
• 读取队头元素。top()：返回队头元素值。
• 获取队列长度。getSize()：
• 判队列空。isEmpty()：若队列为空，返回true，否则返回false。

根据队列的基本操作，可以得到队列抽象类的定义。

Queue.h

//
// 队列抽象类
//

#ifndef DS_QUEUE_H
#define DS_QUEUE_H

template <class T>
class Queue {
    public:
        virtual ~Queue() = default;
        virtual void push(const T& x) = 0;  //入队
        virtual void pop() = 0;             //出队
        virtual T top() const = 0;         //读取队头元素
        virtual bool isEmpty() const = 0;  //判断队列是否为空
        virtual int getSize() const = 0;  //获取队列长度

};

#endif //DS_QUEUE_H

队列的存储方式也分为顺序存储和链式存储

下面分别基于顺序表和链表来实现队列模板。

基于之前实现的顺序表(SequentialQueue)来实现顺序队列

SequentialQueue.h

//
// 基于SequentialList的顺序队列
//

#ifndef DS_SEQUENTIALQUEUE_H
#define DS_SEQUENTIALQUEUE_H

#include "SequentialList.h"
#include "Queue.h"

template <class T>
class SequentialQueue : public Queue<T>{
    private:
        SequentialList<T> sl;
    public:

        ~SequentialQueue() override = default;

        void pop() override {
            sl.remove(0);
        }

        void push(const T& x) override {
            auto size = sl.getSize();
            sl.insert(size,x);
        }

        T top() const override {
            return sl.getElement(0);
        }


        bool isEmpty() const override {
            return this->getSize() == 0;
        }
        int getSize() const override {
            return sl.getSize();
        }

};
#endif //DS_SEQUENTIALQUEUE_H

main.cpp测试

//
// SequentialQueue的测试
//

#include <iostream>

using namespace std;
#include "SequentialQueue.h"
int main() {

    SequentialQueue<int> sq;
    sq.push(1);
    sq.push(2);
    sq.push(3);
    cout << sq.top() << endl;
    cout << sq.isEmpty() << endl;
    cout << sq.getSize() << endl;
    sq.pop();
    cout << sq.top() << endl;

    return 0;
}

假溢出问题：传统顺序队列在尾部指针到达数组末尾时，即使前端有空闲空间也无法插入新元素（假溢出）。循环队列将数组视为环形结构，尾部指针可绕回起始位置继续储存，从而充分利用所有空闲单元。

队列的链式存储结构称为链式队列(Linked Queue)。根据队列先进先出的特性，链式队列是仅在表头删除元素和表尾插入元素的单链表。为了操作方便，链式队列用有头结点的链表表示，并设置队头指针指向链式队列的头结点，队尾指针指向终端结点，如图(a)所示。链式队列加上头结点，能够使空队列和非空队列的操作一致，链式队列的具体判定和操作如下。
(1)当链式队列为空时，头指针和尾指针均指向头结点，如图(b)所示。
(2)一个结点s入队时，将s插入到链表表尾，并将rear指针指向s，如图(c)所示。
(3)一个结点出队时，如果该链式队列只有一个结点，则将头结点的next指针置为NULL，并将rear指针指向头结点，此时链式队列为一个空队列;否则将头结点的next指向第一个结点的后一个结点b，如图(d)所示。

链式队列的基本操作的实现本质上也是单链表操作的简化，插入操作只考虑在链式队列的队尾进行删除操作只考虑在链式队列的队头进行。

和队列一样，栈(stack)也是一种常见的线性表。在中，插入和删除操作被限定在表的某一端进行。假设每天晚上要把火车停在一条轨道上轨道的尽头是封闭的，那么这个轨道就是一个栈。允许进行插入和删除操作的一端称为“栈顶”，另一端称为“栈底”。也就是说，火车只能从一个方向离开，且一列火车要离开的时候，需要把在它之后进入轨道的火车都先移开。栈顶位置的元素称为栈顶元素，若栈中没有元素，则称为“空栈”当需要让一列火车进入轨道时，可以将它放在栈顶，也就是当前空的位置这个过程称为“进栈”(或入栈)。而当需要让一列火车驶离轨道时，则从栈顶取出一列火车，这个过程被称为“出栈”。栈也被叫作“后进先出”的线性表

C++标准库中的队列
std::queue是C++标准库中的单端队列实现。

//
// C++标准库中的单端队列
//

#include <iostream>
using namespace std;

int main() {

    std::queue<int> queue;

    queue.push(1);//元素入队
    queue.push(2);
    queue.push(3);
    queue.push(4);
    
    queue.pop();//元素出队
    int front = queue.front();//访问队首元素

    int size = queue.size();//获取队列的长度
    bool empty = queue.empty();//判断队列是否为空

    cout << front << " " << size << " " << empty << endl;
    return 0;
}

std::deque是C++标准库中的双端队列实现，允许在队列的两端进行插入和删除操作，支持随机访问（通过[]或at()方法），性能接近数组。

栈有三个主要操作

• 压栈。push(x)：将元素x插入栈中，使之成为栈顶元素
• 弹栈。pop()：删除栈顶元素
• 顶栈。top()：返回栈顶元素

除了这些主要操作，还需要用到创建空栈的构造函数

C++标准库中的栈
std::stack是C++标准库中的栈实现。

//
// C++标准库中的栈
//

#include <iostream>
using namespace std;

int main() {

    std::stack<int> stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    cout << stack.top() << endl;

    int size = stack.size();
    bool empty = stack.empty();

    cout << " " << size << " " << empty << endl;
    return 0;
}