【C++篇】栈的层叠与队列的流动：在 STL 的韵律中探寻数据结构的优雅之舞

在这里插入图片描述

文章目录

C++ 栈与队列详解：基础与进阶应用
- 前言
- 第一章：栈的介绍与使用
- - 1.1 栈的介绍
  - 1.2 栈的使用
  - - 1.2.1 最小栈
    - 1.2.2 示例与输出
  - 1.3 栈的模拟实现
- 第二章：队列的介绍与使用
- - 2.1 队列的介绍
  - 2.2 队列的使用
  - - 2.2.1 示例与输出
  - 2.3 队列的模拟实现
  - - 2.3.1 示例与输出
- 第三章：优先队列的介绍与使用
- - 3.1 优先队列的介绍
  - 3.2 优先队列的使用
  - - 3.2.1 示例：默认大顶堆
    - 3.2.2 示例与输出
    - 3.2.3 示例：小顶堆
  - 3.3 优先队列的模拟实现
  - - 3.3.1 示例与输出
- 第四章：容器适配器
- - 4.1 什么是容器适配器
  - 4.2 deque 的简单介绍
  - - 4.2.1 deque 的原理介绍
    - 4.2.2 deque 的缺陷
    - 4.2.3 deque 的常见操作
  - 4.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器
  - 4.4 STL 标准库中 stack 和 queue 的模拟实现
  - - 4.4.1 stack 的模拟实现
    - 4.4.2 queue 的模拟实现
- 第五章：总结
- - 5.1 核心要点回顾

C++ 栈与队列详解：基础与进阶应用

💬 欢迎讨论：在学习过程中，如果有任何疑问或想法，欢迎在评论区留言一起讨论。

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？记得点赞、收藏并分享给更多的朋友吧！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对 C++ 感兴趣的朋友，一起学习进步！

前言

栈与队列是常见的数据结构，常被用于不同的算法场景。在本文中，我们将详细探讨栈与队列的基本概念、实际应用及其模拟实现。栈和队列在日常开发中的重要性不言而喻，通过对这两种数据结构的深入理解，将助你更加灵活地应对算法题目和工程开发。

在阅读本篇之前，可以先看看stl最基础的部分：

【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化

第一章：栈的介绍与使用

1.1 栈的介绍

栈 (Stack) 是一种 后进先出 (LIFO, Last In First Out) 的数据结构。这意味着栈中最后一个被插入的元素会第一个被移出。这种特性使得栈在实现某些算法时非常有用，例如函数调用栈、表达式求值以及括号匹配等。

栈提供的基本操作包括：

push()：将元素压入栈顶。
pop()：将栈顶元素弹出。
top()：获取栈顶元素。
empty()：检查栈是否为空。
size()：获取栈中元素的数量。

常见的栈使用场景有表达式求值、深度优先搜索（DFS）以及回溯法。

1.2 栈的使用

1.2.1 最小栈

最小栈 (Min Stack) 是栈的扩展应用，除了提供基本的栈操作外，还能够在常量时间内返回栈中的最小值。下面展示一个最小栈的具体实现。

#include <stack>
using namespace std;

class MinStack {
public:
    // 构造函数
    MinStack() {}

    // 将元素 x 压入栈中
    void push(int x) {    
        _elem.push(x);  // 元素入栈
        if (_min.empty() || x <= _min.top()) {  
            _min.push(x);  // 如果 x 小于等于当前最小值，则将 x 也压入 _min 栈
        }
    }
    
    // 移除栈顶元素
    void pop() {
        if (_min.top() == _elem.top()) {
            _min.pop();  // 如果当前栈顶元素是最小值，将其从 _min 栈中移除
        }
        _elem.pop();
    }

    // 获取栈顶元素
    int top() { return _elem.top(); }

    // 获取当前栈中的最小值
    int getMin() { return _min.top(); }

private:
    stack<int> _elem;  // 存储栈中的所有元素
    stack<int> _min;   // 存储栈中的最小值
};

1.2.2 示例与输出

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << "Current Min: " << minStack.getMin() << endl;  // 输出 -3
    minStack.pop();
    cout << "Top: " << minStack.top() << endl;             // 输出 0
    cout << "Current Min: " << minStack.getMin() << endl;  // 输出 -2
    return 0;
}

输出结果：

Current Min: -3
Top: 0
Current Min: -2

在这个例子中，我们实现了一个最小栈，可以在常量时间内获取栈中的最小值。在压栈和弹栈操作时，我们同步更新 _min 栈以维护最小值。

1.3 栈的模拟实现

栈的标准实现使用 std::stack 容器，但在某些场景下，可以使用 std::vector 来模拟栈的功能。由于栈的所有操作都围绕末端进行，因此 vector 的尾插操作与 stack 类似。

#include <vector>
using namespace std;

template <typename T>
class SimulatedStack {
public:
    // 向栈中压入元素
    void push(const T& x) {
        _data.push_back(x);
    }
    
    // 弹出栈顶元素
    void pop() {
        _data.pop_back();
    }
    
    // 获取栈顶元素
    T& top() {
        return _data.back();
    }
    
    // 检查栈是否为空
    bool empty() const {
        return _data.empty();
    }
    
    // 获取栈的大小
    size_t size() const {
        return _data.size();
    }

private:
    vector<T> _data;  // 用于存储栈元素的容器
};

这种模拟实现使用了 vector 的尾插操作，可以高效地模拟栈的行为。

第二章：队列的介绍与使用

2.1 队列的介绍

队列 (Queue) 是一种 先进先出 (FIFO, First In First Out) 的数据结构。这意味着第一个进入队列的元素会第一个被移出。队列通常用于任务调度、广度优先搜索 (BFS) 等场景。

队列的基本操作包括：

push()：将元素插入队尾。
pop()：移除队头元素。
front()：获取队头元素。
back()：获取队尾元素。
empty()：检查队列是否为空。
size()：获取队列中的元素数量。

2.2 队列的使用

以下是队列的基本用法展示，包括插入和删除元素。

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);  // 向队尾插入元素1
    q.push(2);  // 向队尾插入元素2
    
    cout << "Front: " << q.front() << endl;  // 输出队头元素 1
    cout << "Back: " << q.back() << endl;    // 输出队尾元素 2
    
    q.pop();  // 移除队头元素
    
    cout << "After pop, Front: " << q.front() << endl;  // 输出新的队头元素 2
    
    return 0;
}

2.2.1 示例与输出

输出结果：

Front: 1
Back: 2
After pop, Front: 2

在这个例子中，我们展示了队列的 push()、pop()、front() 和 back() 操作。

2.3 队列的模拟实现

在一些场景中，标准库中的 std::queue 可能无法满足特定需求，我们可以通过其他容器类来模拟实现队列。由于队列需要支持在头部删除和尾部插入的操作，使用 std::list 会比 std::vector 更为高效。list 允许在常数时间内进行头部和尾部的插入与删除操作，因此非常适合用于队列的实现。

下面是一个基于 list 的队列模拟实现：

#include <list>
using namespace std;

template <typename T>
class SimulatedQueue {
public:
    // 向队尾插入元素
    void push(const T& x) {
        _data.push_back(x);
    }
    
    // 移除队头元素
    void pop() {
        _data.pop_front();
    }
    
    // 获取队头元素
    T& front() {
        return _data.front();
    }
    
    // 获取队尾元素
    T& back() {
        return _data.back();
    }
    
    // 检查队列是否为空
    bool empty() const {
        return _data.empty();
    }
    
    // 获取队列的大小
    size_t size() const {
        return _data.size();
    }

private:
    list<T> _data;  // 用于存储队列元素的容器
};

2.3.1 示例与输出

int main() {
    SimulatedQueue<int> q;
    q.push(10);  // 向队尾插入元素
    q.push(20);
    
    cout << "队头: " << q.front() << endl;  // 输出队头元素 10
    cout << "队尾: " << q.back() << endl;  // 输出队尾元素 20
    
    q.pop();  // 移除队头元素
    
    cout << "新的队头: " << q.front() << endl;  // 输出新的队头元素 20
    
    return 0;
}

输出结果：

队头: 10
队尾: 20
新的队头: 20

在这个例子中，SimulatedQueue 模拟了队列的基本功能，包括在队尾插入元素和移除队头元素。

第三章：优先队列的介绍与使用

3.1 优先队列的介绍

优先队列 (Priority Queue) 是一种特殊类型的队列，其中每个元素都关联有一个优先级。优先队列的特点是元素的弹出顺序不再是按照先进先出，而是按照元素的优先级来决定。通常优先队列可以用来模拟堆结构。

在默认情况下，C++ 标准库中的 std::priority_queue 是一个大顶堆，即优先队列中的最大元素会优先弹出。我们也可以通过自定义比较函数来实现小顶堆，从而使得最小元素优先弹出。

优先队列的常见操作包括：

push()：向优先队列中插入元素。
pop()：移除优先级最高的元素。
top()：获取优先级最高的元素。
empty()：检查优先队列是否为空。
size()：获取优先队列中的元素数量。

3.2 优先队列的使用

下面展示了如何使用 std::priority_queue 进行优先队列操作。

3.2.1 示例：默认大顶堆

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int> pq;  // 默认大顶堆
    
    pq.push(10);
    pq.push(5);
    pq.push(20);
    
    cout << "优先级最高的元素: " << pq.top() << endl;  // 输出 20
    
    pq.pop();  // 移除优先级最高的元素
    
    cout << "新的优先级最高的元素: " << pq.top() << endl;  // 输出 10
    
    return 0;
}

3.2.2 示例与输出

输出结果：

优先级最高的元素: 20
新的优先级最高的元素: 10

在这个例子中，priority_queue<int> 实现了一个大顶堆，插入元素后，优先级最高的元素（值最大的元素）会优先弹出。

3.2.3 示例：小顶堆

我们也可以使用 std::greater<T> 来改变默认的比较方式，从而实现小顶堆。下面是一个小顶堆的例子：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;  // 小顶堆
    
    pq.push(10);
    pq.push(5);
    pq.push(20);
    
    cout << "优先级最高的元素（最小值）: " << pq.top() << endl;  // 输出 5
    
    pq.pop();  // 移除优先级最高的元素
    
    cout << "新的优先级最高的元素: " << pq.top() << endl;  // 输出 10
    
    return 0;
}

输出结果：

优先级最高的元素（最小值）: 5
新的优先级最高的元素: 10

在这个例子中，priority_queue<int, vector<int>, greater<int>> 实现了一个小顶堆，其中优先级最高的元素是值最小的元素。

3.3 优先队列的模拟实现

优先队列通常是基于堆实现的。在 C++ 中，标准库中的 priority_queue 使用 std::vector 作为底层存储，并通过堆算法管理优先级。在需要自定义优先队列行为时，可以自己实现一个简单的优先队列，利用堆的概念来操作。

下面是一个基于 std::vector 实现的简单优先队列：

#pragma once

#include <iostream>
#include <vector>
using namespace std;

// priority_queue--->堆
namespace W {
    // 默认的比较函数为 less，实现大顶堆
	template<class T>
	struct less {
		bool operator()(const T& left, const T& right) {
			return left < right;
		}
	};

    // greater 实现小顶堆
	template<class T>
	struct greater {
		bool operator()(const T& left, const T& right) {
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue {
	public:
		// 创造空的优先级队列
		priority_queue() : c() {}

		// 构造函数支持从迭代器范围初始化
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last) {
			// 将 c 中的元素调整成堆的结构
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		// 向队列中插入元素
		void push(const T& data) {
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		// 移除优先级最高的元素
		void pop() {
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		// 获取优先队列的大小
		size_t size() const {
			return c.size();
		}

		// 检查优先队列是否为空
		bool empty() const {
			return c.empty();
		}

		// 返回优先级最高的元素（不允许修改）
		const T& top() const {
			return c.front();
		}

	private:
		// 向上调整，维护堆的性质
		void AdjustUP(int child) {
		// 计算父节点的索引，等同于 (child - 1) / 2，移位操作符效率更快
			int parent = ((child - 1) >> 1);
			while (child) {
				if (Compare()(c[parent], c[child])) {
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				} else {
					return;
				}
			}
		}

		// 向下调整，维护堆的性质
		void AdjustDown(int parent) {
			size_t child = parent * 2 + 1;
			while (child < c.size()) {
				// 找到父节点较大的孩子
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1])) {
					child += 1;
				}

				// 检查双亲是否满足堆的条件
				if (Compare()(c[parent], c[child])) {
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				} else {
					return;
				}
			}
		}

	private:
		Container c;  // 底层容器，默认为 vector
	};
}

3.3.1 示例与输出

void TestQueuePriority() {
    W::priority_queue<int> q1;
    
    // 向大顶堆中插入元素
    q1.push(5);
    q1.push(1);
    q1.push(4);
    q1.push(2);
    q1.push(3);
    q1.push(6);
    
    // 输出堆顶元素
    cout << "优先级最高的元素: " << q1.top() << endl;  // 输出 6

    // 弹出两个元素
    q1.pop();
    q1.pop();
    
    // 再次输出堆顶元素
    cout << "新的优先级最高的元素: " << q1.top() << endl;  // 输出 4

    // 使用 greater 创建小顶堆
    vector<int> v{5, 1, 4, 2, 3, 6};
    W::priority_queue<int, vector<int>, W::greater<int>> q2(v.begin(), v.end());
    
    // 输出小顶堆的堆顶元素
    cout << "优先级最高的元素(最小值): " << q2.top() << endl;  // 输出 1

    // 弹出两个元素
    q2.pop();
    q2.pop();
    
    // 再次输出小顶堆的堆顶元素
    cout << "新的优先级最高的元素(最小值): " << q2.top() << endl;  // 输出 3
}

输出结果：

优先级最高的元素: 6
新的优先级最高的元素: 4
优先级最高的元素(最小值): 1
新的优先级最高的元素(最小值): 3

在这个模拟实现中，我们使用 std::vector 作为底层容器，并且通过堆排序算法来维护优先队列的顺序。通过 less 和 greater 函数对象，我们可以分别实现大顶堆和小顶堆。

第四章：容器适配器

4.1 什么是容器适配器

容器适配器 (Container Adapter) 是一种设计模式，目的是将一种容器包装为另一种接口形式。容器适配器提供了一组特定的成员函数来访问底层的容器。C++ 标准库中，stack、queue 和 priority_queue 都是容器适配器，它们对容器的操作进行了限制，并定义了特定的访问规则。

在这里插入图片描述

容器适配器本质上是对基础容器的封装，它们可以使用 vector、deque、list 等作为底层实现，而具体使用哪种容器可以根据需求进行调整。容器适配器只暴露了某些特定的操作，而底层容器的更多操作则被隐藏。

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque

常见的容器适配器：

stack：实现后进先出（LIFO）原则。
queue：实现先进先出（FIFO）原则。

在这里插入图片描述

priority_queue：基于优先级进行元素的弹出，通常是大顶堆。

4.2 deque 的简单介绍

双端队列 (deque, Double-Ended Queue) 是一种可以在头尾两端进行高效插入和删除操作的序列式容器。与 vector 类似，deque 提供了动态数组的功能，但它比 vector 更加灵活，允许在头尾两端都进行元素的添加和删除。

在这里插入图片描述

4.2.1 deque 的原理介绍

双端操作：deque 提供了双端操作，即允许在容器的两端进行插入和删除操作。其时间复杂度为常数时间 $O (1)$ ，这使得它比 vector 更适合需要频繁在两端插入或删除元素的场景。
非连续存储：虽然 deque 表面上看起来像是一个连续的数组，但它的底层实现并非真正连续，而是由多块小的连续内存块组合而成，这就允许 deque 在进行元素插入或删除时，不需要像 vector 一样移动大量元素。

下面是一张简化的 deque 的内存布局示意图：

--------------------------------
| Block 1 | Block 2 | Block 3  |
--------------------------------

每个块表示 deque 底层的一部分内存，插入或删除元素时，只需要操作相应块中的数据，而不需要重新分配整个数组的内存。

在这里插入图片描述

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问
的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

在这里插入图片描述

那deque是如何借助其迭代器维护其假想连续的结构呢？

在这里插入图片描述

了解一下即可

4.2.2 deque 的缺陷

虽然 deque 在插入和删除操作上比 vector 更高效，但它也有一些缺点：

遍历性能较低：由于 deque 的存储结构不是一个连续的内存块，所以在遍历 deque 时，迭代器需要处理内存块之间的跳转，导致遍历性能不如 vector。
内存利用率稍低：因为 deque 是由多个小内存块组成的，所以它的内存利用率相比 vector 稍差。不过与 list 比较，deque 的内存效率还是更高。

4.2.3 deque 的常见操作

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<int> d;
    
    // 在队列的两端插入元素
    d.push_back(10);
    d.push_back(20);
    d.push_front(5);
    
    cout << "队头: " << d.front() << endl;  // 输出 5
    cout << "队尾: " << d.back() << endl;   // 输出 20
    
    // 删除队列的两端元素
    d.pop_front();
    d.pop_back();
    
    cout << "新的队头: " << d.front() << endl;  // 输出 10
    
    return 0;
}

输出结果：

队头: 5
队尾: 20
新的队头: 10

这个示例展示了 deque 如何进行两端的插入和删除操作。可以看到，deque 支持同时在队头和队尾进行高效的操作。

4.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器

C++ 标准库中，stack 和 queue 的底层容器默认使用 deque，这是因为 deque 在元素插入和删除时的性能优势以及空间利用率较高的特点，正好符合 stack 和 queue 对容器的需求。

高效的尾部插入和删除：对于 stack，只需要支持在容器的尾部插入和删除元素，deque 的 push_back() 和 pop_back() 操作可以在常数时间内完成，比 vector 在扩容时效率更高。
高效的头部插入和删除：对于 queue，需要在尾部插入元素、在头部删除元素，deque 同时支持 push_back() 和 pop_front() 操作，效率比 list 高，且不需要存储额外的指针信息。

虽然 vector 也可以作为 stack 的底层容器，但它在尾部插入元素时需要在扩容时移动大量元素，因此效率不如 deque。而 list 虽然也支持两端插入删除操作，但由于需要存储额外的指针信息，空间利用率不如 deque 高。因此，deque 被认为是 stack 和 queue 的默认最佳选择。

4.4 STL 标准库中 stack 和 queue 的模拟实现

4.4.1 stack 的模拟实现

stack 的模拟实现只需要封装一个可以支持末端插入和删除操作的容器，默认情况下，使用 deque 作为底层容器。

#include <deque>

namespace W {

template <typename T, typename Container = deque<T>>
class stack {
public:
    stack() {}

    // 向栈中压入元素
    void push(const T& x) {
        _c.push_back(x);
    }
    
    // 弹出栈顶元素
    void pop() {
        _c.pop_back();
    }
    
    // 获取栈顶元素
    T& top() {
        return _c.back();
    }
    
    // 检查栈是否为空
    bool empty() const {
        return _c.empty();
    }
    
    // 获取栈的大小
    size_t size() const {
        return _c.size();
    }

private:
    Container _c;  // 底层容器，默认使用 deque
};
}

4.4.2 queue 的模拟实现

queue 的实现需要支持队尾插入元素、队头删除元素的操作。类似 stack，queue 默认使用 deque 作为底层容器。

#include <deque>

namespace W {

template <typename T, typename Container = deque<T>>
class queue {
public:
    queue() {}

    // 向队尾插入元素
    void push(const T& x) {
        _c.push_back(x);
    }
    
    // 移除队头元素
    void pop() {
        _c.pop_front();
    }
    
    // 获取队头元素
    T& front() {
        return _c.front();
    }
    
    // 获取队尾元素
    T& back() {
        return _c.back();
    }
    
    // 检查队列是否为空
    bool empty() const {
        return _c.empty();
    }
    
    // 获取队列的大小
    size_t size() const {
        return _c.size();
    }

private:
    Container _c;  // 底层容器，默认使用 deque
};
}