81、【栈与队列】leetcode ——232. 用栈实现队列(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:232. 用栈实现队列
使用两个对顶栈实现
因为只能用栈的后进先出的方式实现队列先进先出的方式,因此就使用两个栈来实现。
一个stack用于输入元素,另一个stack用于输出元素。
每次先输入的会被压入到stack-in的栈底,当想要实现队列的方式输出时,需要让stack-in的栈底元素输出。因此就再用另一个stack-out作为媒介,将stack-in中元素全部压入stack-out中,此时stack-in中的栈底元素,就变成了stack-out中的栈顶元素。此时输出stack-out中元素时,先被输出的便是stack-in中的栈底元素。从而实现了队里的FIFO操作方式。
class MyQueue {
public:
stack<int> sIn;
stack<int> sOut;
MyQueue() {
}
void push(int x) {
sIn.push(x);
}
int pop() {
// 当sOut里为空时,将sIn中元素都加入压入进去
if(sOut.empty()) {
while(!sIn.empty()) {
sOut.push(sIn.top());
sIn.pop();
}
}
// 当sOut里不为空时,获取sOut的栈顶元素弹出
int res = sOut.top();
sOut.pop();
return res;
}
int peek() {
// 复用已定义过的pop()方法
int res = this->pop();
// 因为为获取队头元素,而不弹出,因此需要压回栈中
sOut.push(res);
return res;
}
bool empty() {
return sOut.empty() && sIn.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
参考文章:232.用栈实现队列、用栈实现队列
相关文章
- C++动态链接库
- C/C++中的switch语句使用注意
- C/C++基础讲解(五)之基础例程2篇
- Open3D (C++) KD tree的使用——可视化近邻搜索点之间的连线
- Open3D (C++)球旋转算法(BPA)三维建模
- C++每日面试之hex数组转int
- LeetCode 4. 寻找两个正序数组的中位数(执行用时: 20 ms , 在所有 C++ 提交中击败了 94.05% 的用户)
- Leetcode 两数之和 C / C++
- LeetCode 罗马数字转整数(执行用时: 16 ms , 在所有 C++ 提交中击败了 49.87% 的用户)
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
- c++ vector C++ vector存放结构体 并且排序
- c++ const 类型检查
- C++之queue和dequeu用法(七十二)
- C++11 基于范围的for循环
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- c++stl之lower_bound,upper_bound和equal_range函数的详细介绍!!!
- C++Primer学习笔记3-类
- 黑马C++笔记——简易通讯录
- C++17开始取消std::codecvt_utf8支持