文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【C++初阶】6.C++ 栈和队列详解（含模拟实现及其代码）

【C++初阶】6.C++ 栈和队列详解（含模拟实现及其代码）

作者头像
用户11952558
发布于 2026-01-09 14:10:15
发布于 2026-01-09 14:10:15
1690
举报
一、相关题目

由于相关使用和之前的容器欻不多，因此先看几个题目

1. 最小栈 (LeetCode 155)

题目链接：https://leetcode.cn/problems/min-stack/

大意：设计一个栈，支持快速返回当前栈中的元素最小值。

思路：用两个栈，一个模拟标准栈操作 (st)，另一个记录并同步当前的最小值 (min_st)。

代码实现：

代码语言：javascript
复制
class MinStack {
public:
    MinStack() {}

    void push(int val) {
        if(min_st.empty() || val <= min_st.top()) {
            min_st.push(val);
        }
        st.push(val);
    }

    void pop() {
        if(st.top() == min_st.top()) {
            min_st.pop();
        }
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return min_st.top();
    }
private:
    stack<int> st;
    stack<int> min_st;
};
2. 栈的压入、弹出序列 (Nowcoder)

题目链接：栈的压入、弹出序列_牛客题霸_牛客网

大意：判断给定的一组压入序列，是否能通过栈操作得到指定的弹出序列。

思路：简单模拟。将压入序列依次入栈，每次入栈后，循环判断栈顶是否与弹出序列的当前元素相同，若相同则弹出。最终判断弹出序列是否被全部匹配。

代码实现：

代码语言：javascript
复制
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
    stack<int> st;
    int c1 = 0, c2 = 0;
    for(c1 = 0; c1 < pushV.size(); c1++) {
        st.push(pushV[c1]);
        while(!st.empty() && popV[c2] == st.top()) {
            st.pop();
            c2++;
        }
    }
    return c2 == popV.size();
}
3. 二叉树的层序遍历 (LeetCode 102)

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

题目大意：返回二叉树每层的节点值，装在一个二维数组里。

代码实现：

代码语言：javascript
复制
vector<vector<int>> levelOrder(TreeNode* root) {
    if(!root) {
        vector<vector<int>> vvv;
        return vvv;
    }
    queue<TreeNode*> qu;
    qu.push(root);
    int sz = qu.size();
    vector<int> v;
    vector<vector<int>> vv;
    while(!qu.empty()) {
        while(sz--) {
            auto e = qu.front();
            qu.pop();
            v.push_back(e->val);
            if(e->left) {
                qu.push(e->left);
            }
            if(e->right) {
                qu.push(e->right);
            }
        }
        vv.push_back(v);
        sz = qu.size();
        v.clear();
    }
    return vv;
}
二、栈模拟实现（vector版本）
1. 适配器

首先，栈和之前的 vector、list 等容器一个很大的区别就是，用范围 for 遍历栈的每一个元素没有意义（破坏了栈的LIFO特性）。因此，严格意义上讲，它不是一个标准容器，STL 将其称为：容器适配器。其本质为将其它容器（如 vector, deque, list）进行包装，实现栈的接口。由于不是完整容器，它也没有自己的迭代器。

2. 模拟实现

即复用底层容器（此处选用 vector）的各个接口。

代码语言：javascript
复制
template<class T, class Container = std::vector<T>>
class stack {
public:
    void push(const T& val) {
        _con.push_back(val);
    }

    void pop() {
        _con.pop_back();
    }

    const T& top() const {
        return _con.back();
    }

    size_t size() const {
        return _con.size();
    }

    bool empty() const {
        return _con.empty();
    }
private:
    Container _con;
};
3. 模板按需实例化

如果我们在栈的模板实现中，错误地调用一个底层容器不存在的函数：

代码语言：javascript
复制
void pop() {
    _con.f1(); // vector 并没有 f1() 这个成员函数
}

如果我们 不使用 pop 这个接口，那么程序编译时 不会报错。但一旦调用了 pop，编译器就会报错："f1": 不是 "std::vector<T,std::allocator<T>>" 的成员。 这是因为模板在 不被调用时，编译器不会进行实例化检查，只会扫描最基础的语法错误。因此，模板代码需要全面测试才能确保没有问题。

三、队列模拟实现（list版本）

由于 vector 的头删效率低，而 list 头尾插删效率都高，因此队列的底层容器适配器选用 list。

代码语言：javascript
复制
template<class T, class Container = std::list<T>>
class queue {
public:
    void push(const T& val) {
        _con.push_back(val);
    }

    void pop() {
        _con.pop_front(); // 注意：队列是 pop_front
    }

    const T& front() const { // 注意：队列是 front
        return _con.front();
    }

    size_t size() const {
        return _con.size();
    }

    bool empty() const {
        return _con.empty();
    }
private:
    Container _con;
};
四、Deque 介绍

在 STL 文档中，stack 和 queue 的默认底层容器是 deque。 为什么是 deque？

  1. 先分析 vector 和 list 的优缺点：
    • Vector:
      • 优：尾插尾删效率高，支持下标随机访问。物理空间连续，CPU高速缓存命中率高。
      • 缺：空间需扩容，有性能代价和空间浪费。头部、中间插入删除效率低。
    • List:
      • 优：按需申请空间，不用扩容。任意位置插入删除效率高。
      • 缺：不支持下标随机访问。缓存不友好。
  2. deque 是 vector 和 list 的融合： 它试图既能高效头尾插删，又能支持随机访问。但这是一种“中庸”的融合，在特定场景下好用，并非所有方面都最优。
  3. deque 大致原理： 结合了两者，deque 由多个固定大小的连续“缓冲区”(buff)组成。这些缓冲区的指针由一个“中控数组” (map) 统领。最开始的 buff 数组的指针存在中控数组中间，以便进行快速的头尾插入。当我们要访问第 i 个元素时，会去定位第 i / N 个 buff 数组的第 i % N 个元素，即 *(*(ptr + x) + y)。
  1. 迭代器实现： deque 迭代器由 4 个指针构成：cur (当前位置), first (当前缓冲区头), last (当前缓冲区尾), node (指向中控数组中当前缓冲区指针的指针)。
  2. 快速头尾插：
    • 头插：在最左边新开一个 buff 数组，插到末尾；或直接插到第一个 buff 数组的第一个元素前面。
    • 尾插：插到最后一个 buff 数组的最后一个元素后面；或最右边新开一个 buff 数组。
  3. 中间插入/删除： 效率低下，因为可能需要移动大量元素。
  4. Deque 特点总结：
    1. 头尾插删效率高（理论上比 vector、list 都高），因为不用频繁开空间（list），扩容代价小（vector）。
    2. 下标随机访问略慢于 vector。
    3. 中间插入删除远慢于 list。
  5. 用 deque 作为 stack/queue 默认容器的原因： 栈和队列的操作只涉及头部和尾部的插入删除，因此 deque 是非常合适的选择。
五、Priority_queue (优先队列) 使用
1. 与 queue 区别

push 没要求，但 top() 和 pop() 总是取出当前队列中 优先级最高 的元素。其本质就是一个 堆。默认情况下是大根堆。

2. 仿函数

写法：

代码语言：javascript
复制
template<class T>
struct cmp {
    bool operator()(const T& a, const T& b) const {
        return a < b; // 定义比较规则
    }
};
cmp<int> lessfunc; // 实例化一个比较器对象

它重载了 () 运算符，可以像函数一样被调用，故称“仿函数”。

与排序结合的例子（冒泡排序泛化）：

代码语言：javascript
复制
// 原始的冒泡排序，只能从小到大
void bubble_sort(int* a, int n) {
    for (int i = 0; i < n; i++) {
        int fl = 0;
        for (int j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) { // 比较逻辑写死
                swap(a[j - 1], a[j]);
                fl = 1;
            }
        }
        if (fl == 0) break;
    }
}

使用仿函数，可以灵活定义排序规则：

代码语言：javascript
复制
template<class T>
struct cmp1 {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

template<class Compare = cmp1<int>>
void bubble_sort(int* a, int n, Compare cmp = cmp1<int>()) {
    for (int i = 0; i < n; i++) {
        int fl = 0;
        for (int j = 1; j < n - i; j++) {
            if (cmp(a[j], a[j - 1])) { // 使用传入的比较器
                swap(a[j - 1], a[j]);
                fl = 1;
            }
        }
        if (fl == 0) break;
    }
}

使用方式：

  • 有名对象：bubble_sort(a, 10, cmp);
  • 匿名对象：bubble_sort(a, 10, cmp1<int>());

标准库仿函数： C++ 标准库提供了类似的仿函数（如 less, greater）。

  • 从小到大（升序）：bubble_sort(a, 10, less<int>());
  • 从大到小（降序）：bubble_sort(a, 10, greater<int>());
六、优先队列（堆）模拟实现
1. 向上调整 (adjustup)
代码语言：javascript
复制
void adjustup(int c) {
    compare com; // 比较器
    int p = (c - 1) / 2;
    while (c > 0) {
        if (com(_con[p], _con[c])) { // 父节点不满足堆性质
            std::swap(_con[p], _con[c]);
            c = p;
            p = (c - 1) / 2;
        } else {
            break;
        }
    }
}
2. 向下调整 (adjustdown)
代码语言：javascript
复制
void adjustdown(int p) {
    int c = p * 2 + 1;
    compare com;
    while (c < _con.size()) {
        if (c < _con.size() - 1 && com(_con[c], _con[c + 1])) {
            ++c; // 取左右孩子中更大（或更小）的那个
        }
        if (com(_con[p], _con[c])) { // 父节点不满足堆性质
            std::swap(_con[p], _con[c]);
            p = c;
            c = 2 * p + 1;
        } else {
            break;
        }
    }
}
3. 插入 (push)

在底层容器（vector）最后插入，再向上调整。

代码语言：javascript
复制
void push(const T& val) {
    _con.push_back(val);
    adjustup(_con.size() - 1);
}
4. 删除 (pop)

交换堆顶与堆底元素，尾删堆底，再从堆顶向下调整。

代码语言：javascript
复制
void pop() {
    std::swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    adjustdown(0);
}
5. top, size, empty

调用底层容器 vector 的接口即可。

代码语言：javascript
复制
const T& top() {
    return _con[0];
}

size_t size() const {
    return _con.size();
}

bool empty() const {
    return _con.empty();
}
七、堆相关算法库

STL 提供了 <algorithm> 中的堆操作函数：

  1. make_heap: 在普通数组或容器上建堆。
  2. sort_heap: 对一个已建好的堆进行堆排序。
  3. is_heap: 判断一个序列是否满足堆结构。

注意：sort_heap 必须在已经建好的堆（例如通过 make_heap 生成）上使用。

代码语言：javascript
复制
int num[5] = {3, 1, 2, 4, 5};
make_heap(num, num + 5); // 将数组建成堆
sort_heap(num, num + 5); // 对堆进行排序
代码
队列
代码语言：javascript
复制
#include<iostream>
#include<list>
#include<deque>
namespace bit
{
	
	template<class T, class container = std::deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& front() const
		{
			return _con.front();
		}

		const T& back() const
		{
			return _con.back();
		}
		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		container _con;
	};
}
栈
代码语言：javascript
复制
#include<iostream>
#include<vector>
#include<deque>
//using namespace std;

namespace bit
{
	template<class T,class container=std::deque<T>>
	class stack
	{
	public:
		void push(const T&val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& top()const
		{
			return _con.back();
		}
		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		container _con;
	};
}
堆
代码语言：javascript
复制
#include<iostream>
#include<vector>
#include<queue>

namespace bit
{
	template<class T, class container = std::vector<T>,class compare=std::less<int>>
	class priority_queue
	{
	public:
		void adjustup(int c)
		{
			compare com;
			int p = (c - 1) / 2;
			while (c > 0)
			{
				if (com(_con[p], _con[c]))
				{
					std::swap(_con[p], _con[c]);
					c = p;
					p = (c - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T&val)
		{
			_con.push_back(val);
			adjustup(_con.size() - 1);
		}
		void adjustdown(int p)
		{
			int c = p * 2 + 1;
			compare com;
			while (c < _con.size())
			{
				if (c < _con.size() - 1 && com(_con[c], _con[c + 1]))
				{
					++c;
				}
				if (com(_con[p], _con[c]))
				{
					std::swap(_con[p], _con[c]);
					p = c;
					c = 2 * p + 1;

				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjustdown(0);
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size() const
		{
			return _con.size();
		}
		bool empty() const
		{
			return _con.empty();
		}

	private:
		container _con;
	};
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-13，如有侵权请联系 cloudcommunity@tencent.com 删除
数组
c++
容器
队列
函数

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数组
c++
容器
队列
函数
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、相关题目
    • 1. 最小栈 (LeetCode 155)
    • 2. 栈的压入、弹出序列 (Nowcoder)
    • 3. 二叉树的层序遍历 (LeetCode 102)
  • 二、栈模拟实现（vector版本）
    • 1. 适配器
    • 2. 模拟实现
    • 3. 模板按需实例化
  • 三、队列模拟实现（list版本）
  • 四、Deque 介绍
  • 五、Priority_queue (优先队列) 使用
    • 1. 与 queue 区别
    • 2. 仿函数
  • 六、优先队列（堆）模拟实现
    • 1. 向上调整 (adjustup)
    • 2. 向下调整 (adjustdown)
    • 3. 插入 (push)
    • 4. 删除 (pop)
    • 5. top, size, empty
  • 七、堆相关算法库
  • 代码
    • 队列
    • 栈
    • 堆
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论