目录
- 例1：使用队列实现栈（easy 栈、队列）
- 例2：使用栈实现队列（easy 栈、队列）
- 例3：包含min函数的栈（easy 栈）
- 例4：合法的出栈序列（medium 栈、队列）
- 例5：简单的计算器（hard 栈）
- 例6：数组中第K大的数（easy 堆）
- 例7：寻找中位数（hard 堆）
例1：使用队列实现栈（easy 栈、队列）
文章图片
文章图片
class MyStack {
public:
MyStack() {
}
void push(int x) {
std::queue temp_queue;
temp_queue.push(x);
while (!_data.empty()) {
temp_queue.push(_data.front());
_data.pop();
}
while (!temp_queue.empty()) {
_data.push(temp_queue.front());
temp_queue.pop();
}
}
//下面的操作，栈和队列一致
int pop() {
int x = _data.front();
_data.pop();
return x;
}
int top() {
return _data.front();
}
bool empty() {
return _data.empty();
}
private:
std::queue_data;
};
例2：使用栈实现队列（easy 栈、队列）
文章图片
class MyQueue {
public:
MyQueue() {
}
//双栈
void push(int x) {
input_stack.push(x);
}
int pop() {
adjust();
int x = output_stack.top();
output_stack.pop();
return x;
}
int peek() {
adjust();
return output_stack.top();
}
bool empty() {
return (input_stack.empty() && output_stack.empty());
}
private:
void adjust() {
if (!output_stack.empty()) {
return;
}
while (!input_stack.empty()) {
output_stack.push(input_stack.top());
input_stack.pop();
}
}
std::stack input_stack;
std::stack output_stack;
};
例3：包含min函数的栈（easy 栈）
文章图片
用一个单独的栈来存放最小值
文章图片
class MinStack {
public:
MinStack() {
}
void push(int x) {
_data.push(x);
if (_min.empty()) {
_min.push(x);
}
else {
if (x > _min.top()) {
x = _min.top();
}
_min.push(x);
}
}
void pop() {
_min.pop();
_data.pop();
}
int top() {
return _data.top();
}
int getMin() {
return _min.top();
}
private:
std::stack _data;
std::stack _min;
};
例4：合法的出栈序列（medium 栈、队列） 题目：
文章图片
思路：
文章图片
bool check_is_valid_order(std::queue& order) {
std::stack s;
//s为模拟栈
int n = order.size();
for (int i = 0;
i <= n;
i++) {
s.push(i);
while (!s.empty() && s.top() == order.front()) {
s.pop();
order.pop();
}
}
if (!s.empty()) {
return false;
}
return true;
}
例5：简单的计算器（hard 栈） 【数据结构与算法|数据结构与算法——栈、队列、堆汇总整理】力扣—— 224. 基本计算器（困难）
例6：数组中第K大的数（easy 堆）
文章图片
文章图片
文章图片
class Solution {
public:
int findKthLargest(vector& nums, int k) {
priority_queue, greater > q;
for (int i = 0;
i < nums.size();
i++) {
if (q.size() < k) {
q.push(nums[i]);
}
else if (q.top() < nums[i]) {
q.pop();
q.push(nums[i]);
}
}
return q.top();
}
};
例7：寻找中位数（hard 堆） 力扣—— 295. 数据流的中位数（困难）
推荐阅读
- 数据结构与算法|数据结构与算法——线性表（链表篇）
- 笔记|数据结构实验报告3————栈和队列及其应用
- 数据结构与算法|数据结构笔记——栈和队列
- 数据结构与算法复习笔记——栈和队列
- 数据结构|数据结构实验三——栈和队列的基本操作
- 算法|YOLOv6（又快又准的目标检测框架开源啦）
- 数据结构|设计B+树（B+Tree）
- 操作系统|操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
- java|毕业两年，从月薪3500到现在的华为java工程师，我是这样提升自己的技术栈的。