当前位置：首页 > news >正文

【C++/STL深度剖析】stack和queue的详细概念和使用（图文详解，初学者必看！！）

news 来源：原创 2024/7/7 7:29:47

一、前言

二、stack 的详细解析

🔥 stack的介绍🔥

🔥 stack的构造🔥

🔥 stack的常用接口🔥

💧push

💧top

💧pop

💧empty

💧size

💧swap

三、queue 的详细解析

🔥 queue的介绍🔥

🔥 queue的构造🔥

🔥 queue的常用接口🔥

💧push

💧size

💧front

💧back

💧pop

💧empty

💧swap

四、容器适配器

🥝 什么是适配器？

🍍stack 和 queue 的底层结构

🍇deque的原理介绍

🍑deque 的底层结构

🍉deque 的优缺点

🍈 选择 deque 的原因

六、模拟实现【stack】和【queue】

🔥 stack 的模拟实现🔥

🔥 queue 的模拟实现🔥

七、总结

八、共勉

一、前言

最近在刷 leetcode 的时候，发现 stack和queue 都还没弄明白😖，但是 STL 的强大是众所周知滴，早晚都是要解决滴，因此专门写下这篇文章，以供自己复习和各位老铁使用，快速的回忆 stack和queue 的用法，让你找回自信，不用再竞赛的时候颜面尽失。
本次博客主要讲解 stack和queue 的常用接口，由于篇幅过长，stack和queue 的常考面试题，下一篇博客来阐述，请大家持续关注我O！！

二、stack 的详细解析

🔥 stack的介绍🔥

栈 【stack】是一种特殊的数据结构，也是一种容器适配器，主要特点为：【先进后出】，主要操作有：入栈、出栈、查看栈顶元素、判断栈空等；栈在原则上是不允许进行 中部或底部操作的，这样会破坏栈结构的完整性。

从下图，可以看到 栈【stack】是作为容器适配器被实现，容器适配器是对特定类封装作为其底层容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层，元素特定容器的尾部（即栈顶）被压入和弹出。（容器适配器本文的后面会详细讲解，这里先了解一下它和栈的关系）

可以看出，栈有两个模板参数

参数1：T 栈中的元素类型，同时也是底层容器中的元素类型
参数2：Container 实现栈时用到的底层容器，这里为缺省参数，缺省结构为双端队列 deque

也就是说，【stack】的底层容器可以是任何标准的容器类模板或者一些其特定的容器类，这些容器应该支持一下操作：

empty ：判空操作
back ：获取尾部元素操作
push_back ：尾部插入元素操作
pop_back ：尾部删除元素操作

标准容器 vector、deque、list 均符合上面的这些要求，默认情况下，如果没有为【stack】指定特定的顶层容器，默认情况下使用 deque (这一点会在本文，后下容器适配器，详细讲解)

🔥 stack的构造🔥

它的构造方式如下：

（1）使用默认的容器适配器构造一个空栈

stack<int> s; // 默认底层容器为 deque

（2）使用其它的容器适配器构造一个空栈

stack<int, vector<int>> sv;   // 显示实例化 底层容器为 vector
stack<int, list<int>> sl;     // 显示实例化，底层容器为 list

代码测试：

#include <iostream>
#include <stack>
#include <vector>
#include <list>using namespace std;int main()
{stack<int> s;	//默认底层容器为 dequestack<int, vector<int>> sv;	//显示实例化底层容器为 vectorstack<char, list<char>> sl;	//显示实例化底层容器为 listcout << typeid(s).name() << endl;	//查看具体类型cout << typeid(sv).name() << endl;cout << typeid(sl).name() << endl;return 0;
}

注意： 关于参数3 allocator 是空间配置器，这里先不作讲解，后续再学习

🔥 stack的常用接口🔥

相对于前面学习的容器（vector、list、string），【stack】的接口更简单也更少，基本的使用函数如下：

💧push

在栈【stack】顶部插入一个新元素，位于其当前顶部元素之上。

代码示例：

void test_stack()
{stack<int> st;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest.push(1);st.push(2);st.push(3);     // 向 栈 中插入 元素 【1，2，3，4，5】st.push(4);st.push(5);
}

💧top

返回栈【stack】的顶部元素

代码示例：

void test_stack()
{stack<int> st;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest.push(1);st.push(2);st.push(3);     // 向 栈 中插入 元素 【1，2，3，4，5】st.push(4);st.push(5);cout << st.top() << endl; // 返回栈的 顶部元素  -- 【5】
}

运行结果展示：

💧pop

删除栈【stack】顶部的元素，有效的将其空间大小 -- 减少 1

代码示例：

void test_stack()
{stack<int> st;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest.push(1);st.push(2);st.push(3);     // 向 栈 中插入 元素 【1，2，3，4，5】st.push(4);st.push(5);cout << st.top() << endl; // 返回栈的 顶部元素  -- 【5】st.pop();                 // 删除栈顶元素 -- [5]cout << st.top() << endl; // 返回栈的 顶部元素  -- 【4】
}

运行结果展示：

💧empty

返回栈【stack】是否为空，即它的空间大小是否为 0

因为栈【stack】是不支持遍历的，所以这个接口可以用来实现栈的遍历

代码示例：

void test_stack()
{stack<int> st;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest.push(1);st.push(2);st.push(3);     // 向 栈 中插入 元素 【1，2，3，4，5】st.push(4);st.push(5);while(!st.empty()){cout << st.top() << " ";st.pop();        }
}

运行结果展示：

💧size

返回栈【stack】中元素个数

代码示例：

void test_stack()
{stack<int> st;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest.push(1);st.push(2);st.push(3);     // 向 栈 中插入 元素 【1，2，3，4，5】st.push(4);st.push(5);cout << st.size() << endl;  // 返回 栈 中的元素个数 -- 5个
}

💧swap

将容器适配器（*this）的内容与 x 的内容进行交换，其实就是交换两个栈的元素数据

代码示例：

void test_stack()
{stack<int> st1;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest1.push(1);st1.push(2);st1.push(3);     // 向 栈 中插入 元素 【1，2，3】stack<int> st2;  // 构造一个栈 对象 --- 此时为空栈，底层为 dequest2.push(4);st2.push(5);st2.push(6);     // 向 栈 中插入 元素 【4，5，6】st1.swap(st2)   // 交换两个 栈 的数据// 遍历两个栈 while(!st1.empty()){cout << st1.top() << " ";    // 【6，5，4】st1.pop();  }while(!st2.empty()){cout << st2.top() << " ";    // 【3，2，1】st2.pop();  }}

运行结果展示：

三、queue 的详细解析

🔥 queue的介绍🔥

队列 【queue】是一种特殊的数结构，同时也是一种 容器适配器，遵循先进先出FIFO原则，其中从容器一端插入元素，另一端提取元素。主要操作：入队、出队、判断队空、查看队头队尾元素等；队列在原则上是不允许进行中部的操作，这样会破坏队列的完整性。

从下图，可以看到 队列【queue】也是作为容器适配器被实现，容器适配器是对特定类封装作为其底层容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层。元素从队尾入列，从队头出列。（容器适配器本文的后面会详细讲解，这里先了解一下它和队列的关系）

可以看出，队列也有两个模板参数

参数1：T 栈中的元素类型，同时也是底层容器中的元素类型
参数2：Container 实现栈时用到的底层容器，这里为缺省参数，缺省结构为双端队列 deque

也就是说，【queue】的底层容器可以是任何标准的容器类模板或者一些其特定的容器类，这些容器应该支持一下操作：

empty ：检查队列是否为空
size ：返回队列中的有效元素个数
front ：返回队头元素的引用
back ：返回队尾元素的引用
psuh_back ：在队列尾部入队列
pop_front ：在队列头部出队列

标准容器 vector、deque、list 均符合上面的这些要求，默认情况下，如果没有为【queue】指定特定的顶层容器，默认情况下使用 deque (这一点会在本文，后下容器适配器，详细讲解)

🔥 queue的构造🔥

它的构造方式如下：

（1）使用默认的容器适配器构造一个空队列

queue<int> q1;  // 默认底层容器为 deque

（2）使用其它的容器适配器构造一个空队列

queue<int, vector<int>> q2;   // 显示实例化 底层容器为 vector
queue<int, list<int>> q2;     // 显示实例化，底层容器为 list

代码示例：

#include <iostream>
#include<queue>
#include <vector>
#include <list>using namespace std;int main()
{queue<int> qDeque;	//默认使用 dequequeue<double, vector<double>> qVector;	//指定使用 vectorqueue<char, list<char>> qList;	//指定使用 listcout << typeid(qDeque).name() << endl;	//查看具体类型cout << typeid(qVector).name() << endl;cout << typeid(qList).name() << endl;return 0;
}

运行结果展示：

🔥 queue的常用接口🔥

相对于前面学习的内容，队列【queue】的接口更简单也更少，基本的使用函数如下：

💧push

在队列末尾插入一个新元素，位于当前最后一个元素之后

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);
}

💧size

返回队列中元素的数量

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.size() << endl;
}

运行结果展示：

💧front

返回队列的队头元素

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.front() << endl;
}

运行结果展示：

💧back

返回队列中最后一个元素，也就是获取队尾元素

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.back() << endl;
}

运行结果展示：

💧pop

删除队列中的下一个元素，有效地将其大小减少 1，也就是删除队头元素

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.pop(); // 删除队头元素cout << q.size() << endl;cout << q.front() << endl;
}

运行结果展示：

💧empty

返回队列是否为空，即队列大小是否为 0

因为队列是先进先出，不支持遍历，所以这个接口可以用来实现队列遍历

代码示例：

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);while (!q.empty()) {cout << q.front() << " ";q.pop();}}

运行结果展示：

💧swap

将容器适配器（*this）的内容与 x 的内容切换，其实就是交换两个队列中的元素数据

代码示例：

void test_queue()
{queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);q1.push(5);q1.push(6);queue<int> q2;q2.push(8);q2.push(9);q2.push(10);q1.swap(q2);while (!q1.empty()) {cout << q1.front() << " ";q1.pop();}while (!q2.empty()) {cout << q2.front() << " ";q2.pop();}
}

运行结果展示：

四、容器适配器

🥝 什么是适配器？

适配器是一种设计模式（设计模式是一套被反复使用的、多人知晓的、经过分类编目的、代码设计经验的总结），该设计模式是将一个类的接口转换成客户希望的另一个接口

从应用角度出发，STL 中的适配器可以分为三类：

容器适配器 container adapters
迭代器适配器 iterator adapters
仿函数适配器 functor adapters

其中，容器适配器 可修改底层为指定容器，如由 vector 构成的栈、由 list 构成的队列；迭代器适配器可以 实现其他容器的反向迭代器（后续介绍）；最后的仿函数适配器就厉害了，几乎可以 无限制的创造出各种可能的表达式

本文介绍的是容器适配器，即 栈 和 队列，最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列

🍍stack 和 queue 的底层结构

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

注意： 容器支持迭代器，但是容器适配器不支持迭代器，因为栈和队列这种数据结构不能随便去遍历，不然会导致发生变化，不易维护

🍇deque的原理介绍

双端队列【deque】：是一种双开口 ”连续“ 空间的数据结构，双开口的含义：可以在头尾端进行插入和删除操作，且时间复杂度为：O(1) ,与【vector】比较，头插效率高，不需要移动元素；与【list】比较，空间利用率比较高

🍑deque 的底层结构

deque（双端队列）的底层结构通常由多个固定大小的缓冲区组成，每个缓冲区是一个连续的存储块。这些缓冲区通过一个指向前一个缓冲区和一个指向后一个缓冲区的指针进行连接，形成了一个双向链表。

deque的内部缓冲区以分块的形式存储元素。每个缓冲区有一个固定的大小，它通常是2的幂次方，例如512、1024等。缓冲区中的元素被存储在数组中，以保持元素的连续性。

deque的双向链表由一个或多个缓冲区组成，每个缓冲区都包含一个指向前一个缓冲区和一个指向后一个缓冲区的指针。第一个缓冲区的指向前一个缓冲区的指针为空指针，最后一个缓冲区的指向后一个缓冲区的指针也为空指针。

当需要在deque的头部或尾部插入或删除元素时，只涉及到相关缓冲区的操作，而不会涉及其他缓冲区。这种设计使得deque的插入和删除操作时间复杂度为常数级别（O(1)）。

🍉deque 的优缺点

⭕deque（双端队列）在大多数情况下是非常高效且灵活的数据结构，但它也有一些缺点需要注意。

【vector】的优缺点：

优点：适合尾插尾删，随机访问
缺点：不适合头部或者中部插入删除，效率低，需要挪动数据；扩容有一定性能消耗，还可能存在一定程度的空间浪费。

【list】的优缺点：

优点：在任意位置插入删除效率高；按需申请释放空间
缺点：不支持随机访问；CPU高速缓存命中率低

【deque】就结合了【vector】和【list】的优缺点而为之发明！！！

【deque】与【vector】相比较的优势：头部插入和删除时，不需要搬移元素，效率特别高，而且效率特别高，而且在扩容时，也不需要移动大量元素，因此其效率是比【vector】高。

【deque】与【list】相比较的优势：其底层是连续空间，空间利用率较高，不需要存储额外字段

【deque】的致命缺陷：不适合遍历！！！ 因为在遍历时，【deque】的迭代器要频繁的去检查其是否移动到某段空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑【vector】和【list】。

🍈 选择 deque 的原因

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

【stack】是一种，后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为【stack】的底层容器，比如【vector】和【list】都可以

【queue】是一种，先进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为【queue】的底层容器，比如【list】

注意：string 、vector 不支持头删，因此无法适配 queue

但是在 STL 中对【stack】和【queue】默认选择【queue】作为其底层容器，原因为：

【stack】和【queue】不需要遍历（因此stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。

在【satck】中元素增长时，【deque】比【vector】的效率更高（扩容时不需要移动大量元素）

在【queue】中元素增长时，【deque】不仅效率高，而且内存使用率高

总结来说：【deque】结合了所有【stack】和【queue】所需要的优点，而完美的避开了其缺陷

六、模拟实现【stack】和【queue】

🔥 stack 的模拟实现🔥

关于 stack 的模拟实现很简单，主要就是针对一些常用的接口，具体代码如下：

namespace xas
{template<class T, class Container = deque<T>>class Stack{public:// 入栈void push(const T& x){_con.push_back(x);}// 出栈void pop(){_con.pop_back();}// 获取栈顶元素T& top(){return _con.back();}const T& top() const{return _con.back();}//获取栈中有效元素个数size_t size() const{return _con.size();}//判断栈是否为空bool empty() const{return _con.empty();}//交换两个栈中的数据void swap(Stack<T, Container>& st){_con.swap(st._con);}private:Container _con;};// 测试函数void test_stack(){Stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);st.push(6);cout << "栈中元素个数：" << st.size() << endl;cout << "出栈顺序：";while (!st.empty()) {cout << st.top() << " ";st.pop();}}
}

测试结果：

适配器的厉害之处就在于 只要底层容器有我需要的函数接口，那么我就可以为其适配出一个容器适配器，比如 vector 构成的栈、list 构成的栈、deque 构成的栈，甚至是 string 也能适配出一个栈，只要符合条件，都可以作为栈的底层容器，当然不同结构的效率不同，因此库中选用的是效率较高的 deque 作为默认底层容器

🔥 queue 的模拟实现🔥

关于 queue 的模拟实现很简单，主要就是针对一些常用的接口，具体代码如下：

namespace xas
{template<class T, class Container = deque<T>>class Queue{public:// 入队void push(const T& x){_con.push_back(x);}// 出队void pop(){_con.pop_front();}// 获取队头元素T& front(){return _con.front();}const T& front() const{return _con.front();}// 获取队尾元素T& back(){return _con.back();}const T& back() const{return _con.back();}//获取队列中有效元素个数size_t size() const{return _con.size();}//判断队列是否为空bool empty() const{return _con.empty();}//交换两个栈中的数据void swap(Queue<T, Container>& q){_con.swap(q._con);}private:Container _con;};// 测试函数void test_queue(){Queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);q.push(7);cout << "队列中元素个数：" << q.size() << endl;cout << "出队顺序：";while (!q.empty()) {cout << q.front() << " ";q.pop();}}
}

测试结果：

七、总结

以上就是本篇关于 C++ STL学习之【stack和queue的详细概念和使用】的全部内容了，在本文中， 我们首先学习了栈和队列的基本概念和使用；其次学习了容器适配器，了解它存在的意义及种类；最后认识了容器适配器的默认底层容器 双端队列，见识了其复杂的结构设计及优缺点。

最后我们再来看一下栈和队列在实际生活中的应用吧

栈的典型应用：

浏览其中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就将上一个网页执行入栈，这样我们就可以通过【后退】操作来回倒上一页面，后退操作实际上是在执行出栈。如果同时支持后退和前进，那么则需要两个栈来配合。
程序内存管理。每当调用函数时，系统就会在栈顶添加一个栈帧，用来记录函数的上下文信息。在递归函数中，向上递推会不断执行入栈，向上回溯阶段时出栈。

队列的典型应用：