C++STL~~stackqueue

文章目录

- 容器适配器
- 一、stack&queue的概念
- 二、stack&queue的使用
- 三、stack&queue的练习
- 四、总结

容器适配器

什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
在这里插入图片描述
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque（双端队列容器）
在这里插入图片描述

一、stack&queue的概念

stack（栈）
概念和特点
栈是一种后进先出（Last In First Out，LIFO）的数据结构。就像一叠盘子，最后放上去的盘子最先被拿走。
在这里插入图片描述

queue（队列）
概念和特点
队列是一种先进先出（First In First Out，FIFO）的数据结构。类似于排队买东西，先到的人先得到服务。
在这里插入图片描述

二、stack&queue的使用

stack的使用
在这里插入图片描述

例如：

#include <iostream>
#include <stack>int main() {std::stack<int> s;// 向栈中压入一些元素s.push(10);s.push(20);s.push(30);// 输出栈的大小std::cout << "初始栈的大小为：" << s.size() << std::endl;// 检查栈是否为空if (!s.empty()) {std::cout << "栈不为空。" << std::endl;}// 获取栈顶元素并输出std::cout << "栈顶元素为：" << s.top() << std::endl;// 弹出栈顶元素s.pop();// 再次输出栈顶元素和栈的大小std::cout << "弹出一个元素后，栈顶元素为：" << s.top() << std::endl;std::cout << "此时栈的大小为：" << s.size() << std::endl;// 继续弹出元素直到栈为空while (!s.empty()) {s.pop();}// 检查栈是否为空if (s.empty()) {std::cout << "栈已为空。" << std::endl;}return 0;
}
}

首先向栈中压入一些元素，然后展示了如何使用size获取栈的大小，empty判断栈是否为空，top获取栈顶元素，以及pop弹出栈顶元素。
queue的使用
在这里插入图片描述

#include <iostream>
#include <queue>int main() {std::queue<int> q;// 检查初始时队列是否为空std::cout << "初始时队列是否为空：" << (q.empty()? "是" : "否") << std::endl;std::cout << "初始队列大小：" << q.size() << std::endl;// 向队列中添加元素q.push(10);q.push(20);q.push(30);// 输出队列的大小和队首、队尾元素std::cout << "添加元素后队列大小：" << q.size() << std::endl;std::cout << "队首元素（front）：" << q.front() << std::endl;std::cout << "队尾元素（back）：" << q.back() << std::endl;// 弹出一个元素q.pop();// 再次输出队列的大小和队首、队尾元素std::cout << "弹出一个元素后队列大小：" << q.size() << std::endl;std::cout << "队首元素（front）：" << q.front() << std::endl;std::cout << "队尾元素（back）：" << q.back() << std::endl;// 检查队列是否为空std::cout << "此时队列是否为空：" << (q.empty()? "是" : "否") << std::endl;return 0;
}

首先展示了初始时队列的空状态和大小，然后添加元素后展示了队列的大小、队首和队尾元素，接着弹出一个元素后再次展示相关信息，最后检查队列是否为空。需要注意的是，queue中没有top函数，因为queue的特点决定了只能从队首和队尾进行操作。

三、stack&queue的练习

1.最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void
pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

思路：

1.首先，使用一个普通的栈来存储元素，这个栈用于实现push、pop和top操作。
2.为了能够在常数时间内获取最小元素，再使用另一个栈来存储当前的最小元素。每当向主栈中压入一个元素时，如果这个元素小于等于辅助栈的栈顶元素（或者辅助栈为空时），就将这个元素也压入辅助栈。这样，辅助栈的栈顶始终是当前主栈中的最小元素。
3.当执行pop操作时，如果弹出的元素等于辅助栈的栈顶元素，那么也从辅助栈中弹出这个元素，以保证辅助栈的栈顶始终是当前主栈中的最小元素。

#include <iostream>
#include <stack>class MinStack {
private:std::stack<int> mainStack;std::stack<int> minStack;
public:MinStack() {}void push(int val) {mainStack.push(val);if (minStack.empty() || val <= minStack.top()) {minStack.push(val);}}void pop() {if (mainStack.top() == minStack.top()) {minStack.pop();}mainStack.pop();}int top() {return mainStack.top();}int getMin() {return minStack.top();}
};

使用以下方式测试这个类

int main() {MinStack minStack;minStack.push(-2);minStack.push(0);minStack.push(-3);std::cout << minStack.getMin() << std::endl;minStack.pop();std::cout << minStack.top() << std::endl;std::cout << minStack.getMin() << std::endl;return 0;
}

2.栈的弹出压入序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

0<=pushV.length == popV.length <=1000
-1000<=pushV[i]<=1000
pushV 的所有数字均不相同

示例1 输入： [1,2,3,4,5],[4,5,3,2,1] 返回值：true 说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

思路：

1.使用一个辅助栈来模拟入栈和出栈的过程。
2.遍历压入序列pushV，将元素依次压入辅助栈。
3.同时，遍历弹出序列popV，检查辅助栈的栈顶元素是否与当前要弹出的元素相等。如果相等，则从辅助栈弹出该元素，继续检查下一个弹出元素；如果不相等，则继续从压入序列中压入元素到辅助栈，直到辅助栈的栈顶元素与当前要弹出的元素相等或者压入序列遍历完。
4.如果最终辅助栈为空，说明弹出序列是可能的，否则不可能。

#include <iostream>
#include <vector>
#include <stack>class Solution {
public:bool isPopOrder(std::vector<int> pushV, std::vector<int> popV) {std::stack<int> s;int i = 0, j = 0;while (i < pushV.size()) {s.push(pushV[i++]);while (!s.empty() && s.top() == popV[j]) {s.pop();j++;}}return s.empty();}
};

使用以下方式测试这个函数

int main() {Solution solution;std::vector<int> pushV = {1, 2, 3, 4, 5};std::vector<int> popV = {4, 5, 3, 2, 1};bool result = solution.isPopOrder(pushV, popV);std::cout << (result? "true" : "false") << std::endl;return 0;
}

3.二叉树的分层遍历**
给你二叉树的根节点 root ，返回其节点值的层序遍历。 (即逐层地，从左到右访问所有节点）。
在这里插入图片描述
思路

1.使用一个队列来实现层序遍历。首先将根节点入队。
2.不断循环，当队列不为空时：
- 记录当前队列的大小size，这个大小表示当前层的节点个数。
- 遍历当前层的所有节点，对于每个节点：
- 取出节点的值，将其加入到结果列表中。
- 如果该节点有左子节点，将左子节点入队。
- 如果该节点有右子节点，将右子节点入队。
3.循环结束后，就得到了二叉树的层序遍历结果。

#include <iostream>
#include <vector>
#include <queue>// 定义二叉树节点结构体
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:std::vector<std::vector<int>> levelOrder(TreeNode* root) {std::vector<std::vector<int>> result;if (!root) return result;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();std::vector<int> level;for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(level);}return result;}
};

使用以下方式测试这个函数

int main() {// 构建二叉树TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);Solution solution;std::vector<std::vector<int>> result = solution.levelOrder(root);for (const auto& level : result) {for (int val : level) {std::cout << val << " ";}std::cout << std::endl;}// 释放内存delete root->right->right;delete root->right->left;delete root->right;delete root->left;delete root;return 0;
}