栈

栈（Stack）是先进后出的数据结构，我们可以将其想象为一个杯子，入栈就是不断往杯子中放入大小合适的小球，出栈时需要将小球从上至下一个个取出。

由此带来的访问入栈（push）、栈顶元素（top）、弹出栈顶（pop）时间复杂度都是$O(1)$.

栈的常见应用场景

• 程序内存管理：函数栈，用于记录函数的上下文信息；
• 撤销与重做：撤销操作时将操作入栈，重做时将撤销的操作一个个出栈。

栈的两种实现方式

我们可以使用数组或链表来实现栈，两种实现方式可以完成的栈功能都是一致的，但由于两种基本数据结构特性的不同，在部分操作的性能上存在差异。

使用数组实现时，为避免手动处理扩容问题，应使用动态数组实现。

两种实现方式的简单对比：

STL stack

C++STL stack容器提供如下操作：

队列

队列（Queue）是先进先出的数据结构，如同排队一样，我更喜欢将其想象为两端开口的管道，入队便是向管道入口放入小球，出队便是从管道出口取出小球，管道两端分别是只允许入或出的队尾和队首。

由此带来的入队（push）、访问队首（front）、出队（pop）时间复杂度均为$O(1)$.

队列的常见应用场景

• 进程调度：例如，就绪队列中存储着处于就绪状态等待被调度执行的进程，当 CPU 空闲时，操作系统从就绪队列中选择一个进程进行执行；
• 消息队列：在分布式 Web 服务架构中，不同的服务组件之间可以通过消息队列进行通信。例如，订单服务在处理完一个订单后，可以将订单处理完成的消息放入消息队列。

队列的两种实现方式

使用链表实现队列的思路比较常规，初始化头（front）尾（rear）节点，指向队列的头尾，并且规定队尾仅可添加，队首仅可删除，记录出入队记录队列长度（size）即可。

但Hello-algo中使用数组实现就比较妙了，它采用的方式是环形数组，所以这里着重讲一下环形数组实现队列的方法。示例实现这一方法时采用了queCapacity描述队列容量，即数组上限，当然也可采用动态数组的形式进行扩容。

环形数组实现队列

使用数组实现队列时需要考虑解决这两个问题：

• 在数组中删除首元素的时间复杂度为$O(n)$（删除并移动元素），可以使用队首指针front和长度size对队列有效范围进行规定，然后定义队尾rear = front + size，如此数组中队列的有效区间便为$[front, rear - 1]$；
• 在不断的出入队过程中，front和rear移动到数组的尾部时将无法继续移动，解决方案是将数组视为首尾相接的环形数组。具体操作是让front或rear越过数组尾部时回到数组头部继续遍历，方法是取余。

// 基于环形数组实现的队列
class ArrayQueue {
private:
    int* nums;       // 用于存储队列元素的数组
    int front;       // 队首指针，指向队首元素
    int queSize;     // 队列长度
    int queCapacity; // 队列容量

public:
    ArrayQueue(int capacity) {
        // 初始化队列
        nums = new int[capacity];
        front = 0;
        queSize = 0;
        queCapacity = capacity;
    }

    ~ArrayQueue() {
        delete[] nums;
    }

    // 队列容量
    int capacity() {
        return queCapacity;
    }

    // 队列大小
    int size() {
        return queSize;
    }

    // 队列是否为空
    bool empty() {
        if (queSize == 0) return true;
        else return false;
    }

    // 访问队首
    int front() {
        if (empty()) {
            std::cout << "队列为空" << std::endl;
            return;
        }
        return nums[front];
    }

    // 访问队尾
    int back() {
        if (empty()) {
            std::cout << "队列为空" << std::endl;
            return;
        }
        return nums[front + queSize - 1];
    }

    // 入队
    void push(int num) {
        if (queSize == queCapacity) {
            std::cout << "队列已满" << std::endl;
            return;
        }

        int rear = (front + queSize) % queCapacity; // 取余：rear越过数组尾部回到头部
        nums[rear] = num;
        queSize++;
    }

    // 出队
    int pop() {
        if (empty()) {
            std::cout << "队列为空" << std::endl;
            return;
        }

        front = (front + 1) % queCapacity;	// 取余：front越过数组尾部回到头部
        queSize--;
    }
};

STL queue

C++ STL queue容器提供如下操作：

双向队列

不同于队列仅允许单进单出，双向队列（double-ended queue）允许在头部和尾部执行添加或删除操作，提供了更高的灵活性。

双向队列支持在队列的两端执行常数级别的增删操作，即时间复杂度为$O(1)$.

双向队列常见应用场景

• 滑动窗口算法：例如，在求解数组中连续子数组的最大和问题时，可以使用双向队列来存储当前窗口内的元素，通过不断地调整窗口的大小和更新队列中的元素，找到最大的子数组和；
• 设定上限的撤销与重做：考虑到系统资源限制，软件的撤销步数通常是有上限的，即软件需要在撤销队列的最底部（队首、栈底）删除最远的步数，但栈无法做到这一操作，这时便可以使用双向队列替代栈。

双向队列的两种实现方式

对应地，双向队列可以使用双向链表进行实现，在两端同时设计添加和删除节点功能。

数组实现则可参考队列的环形数组实现方案，在单向队列的基础上增加头节点（队尾）的删除和尾节点（队首）的添加功能。

STL deque

C++ STL deque容器提供如下操作：