【 数据结构 & 算法 】—— 栈、队列、堆
2020-10-15 本文已影响0人
Du1in9
< 思维导图 >
预备知识：STL stack（堆）
预备知识：STL queue（队列）
使用队列实现栈（栈、队列）（★）
- LeetCode 225.Implement Stack using Queues.cpp
#include <stdio.h>
#include <queue>
class MyStack {
private:
// 新建数据队列
std::queue<int> _data;
public:
MyStack() {
}
void push(int x) {
// 新建临时队列
std::queue<int> 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();
}
};
int main(){
MyStack S;
S.push(1);
S.push(2);
S.push(3);
S.push(4);
// 4，3，2，1
printf("%d\n", S.top());
S.pop();
// 3，2，1
printf("%d\n", S.top());
S.push(5);
// 5，3，2，1
printf("%d\n", S.top());
return 0;
}
使用栈实现队列（栈、队列）（★）
- LeetCode 232.Implement Queue using Stacks.cpp
#include <stdio.h>
#include <stack>
class MyQueue {
private:
// 新建数据栈
std::stack<int> _data;
public:
MyQueue() {
}
void push(int x) {
// 新建临时栈
std::stack<int> temp_stack;
// 若数据栈不为空，导入临时栈
while(!_data.empty()){
temp_stack.push(_data.top());
_data.pop();
}
// 将新元素导入临时栈
temp_stack.push(x);
// 若临时栈不为空，导入数据栈
while(!temp_stack.empty()){
_data.push(temp_stack.top());
temp_stack.pop();
}
}
// 弹出数据栈头部元素
int pop() {
int x = _data.top();
_data.pop();
return x;
}
// 返回数据栈头部元素
int peek() {
return _data.top();
}
// 返回数据栈是否为空
bool empty() {
return _data.empty();
}
};
int main(){
MyQueue Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
// 4，3，2，1
printf("%d\n", Q.peek());
Q.pop();
// 4，3，2
printf("%d\n", Q.peek());
return 0;
}
包含 min 函数的栈（栈）（★）
- LeetCode 155.MinStack.cpp
#include <stdio.h>
#include <stack>
class MinStack {
private:
std::stack<int> _data;
std::stack<int> _min;
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() {
_data.pop();
_min.pop();
}
// 返回数据栈顶端数据
int top() {
return _data.top();
}
// 返回最小值栈顶端数据
int getMin() {
return _min.top();
}
};
int main(){
MinStack minStack;
minStack.push(-2);
// -2
printf("top = [ %d ]\n", minStack.top());
printf("min = [ %d ]\n\n", minStack.getMin());
minStack.push(0);
// -2，0
printf("top = [ %d ]\n", minStack.top());
printf("min = [ %d ]\n\n", minStack.getMin());
minStack.push(-5);
// -2，0，-5
printf("top = [ %d ]\n", minStack.top());
printf("min = [ %d ]\n\n", minStack.getMin());
minStack.pop();
// -2，0
printf("top = [ %d ]\n", minStack.top());
printf("min = [ %d ]\n\n", minStack.getMin());
return 0;
}
使用队列实现栈（栈、队列）（★★）
- poj1363.cpp
#include <stdio.h>
#include <stack>
#include <queue>
// 检查队列 order 是否合法
bool check_is_valid_order(std::queue<int> &order){
// S 为模拟栈
std::stack<int> S;
int n = order.size();
for (int i = 1; i <= n; i++){
// 将 1 到 n 依次压入栈
S.push(i);
// 如果 S 不为空，且栈顶等于队列顶
while(!S.empty() && order.front() == S.top()){
S.pop();
order.pop();
}
}
// 如果最后 S 不为空，则不合法
if (!S.empty()){
return false;
}
// 如果最后 S 为空，则合法
return true;
}
int main(){
int n, train;
// 输入队列长度 n
scanf("%d", &n);
std::queue<int> order;
// 输入元素 train，存入队列 order
for (int i = 0; i < n; i++){
scanf("%d", &train);
order.push(train);
}
// 检查队列 order 是否合法
if (check_is_valid_order(order)){
printf("Yes\n");
}
else{
printf("No\n");
}
return 0;
}
简单的计算器（栈）（★★★）
- LeetCode 224.Basic Calculator.cpp
#include <stdio.h>
#include <string>
#include <stack>
class Solution {
private:
// 带入数字和运算符进行计算
void compute(std::stack<int> &number_stack,
std::stack<char> &operation_stack){
// 如果只有一个数字
if (number_stack.size() < 2){
return;
}
// 取出、弹出数字
int num2 = number_stack.top();
number_stack.pop();
int num1 = number_stack.top();
number_stack.pop();
// 运算、弹出运算符
if (operation_stack.top() == '+'){
number_stack.push(num1 + num2);
}
else if(operation_stack.top() == '-'){
number_stack.push(num1 - num2);
}
operation_stack.pop();
}
public:
int calculate(std::string s) {
static const int STATE_BEGIN = 0;
static const int NUMBER_STATE = 1;
static const int OPERATION_STATE = 2;
std::stack<int> number_stack;
std::stack<char> operation_stack;
int number = 0;
int STATE = STATE_BEGIN;
int compuate_flag = 0;
for (int i = 0; i < s.length(); i++){
// 跳过空格字符
if (s[i] == ' '){
continue;
}
switch(STATE){
case STATE_BEGIN:
// 若是字符 0123456789
if (s[i] >= '0' && s[i] <= '9'){
STATE = NUMBER_STATE;
}
// 若是字符 +-()
else{
STATE = OPERATION_STATE;
}
i--;
break;
case NUMBER_STATE:
// 字符数字转换为整型数字
if (s[i] >= '0' && s[i] <= '9'){
number = number * 10 + s[i] - '0';
}
// 存入数字
else{
number_stack.push(number);
if (compuate_flag == 1){
compute(number_stack, operation_stack);
}
number = 0;
i--;
STATE = OPERATION_STATE;
}
break;
case OPERATION_STATE:
// 存入运算符
if (s[i] == '+' || s[i] == '-'){
operation_stack.push(s[i]);
compuate_flag = 1;
}
// 改变运算开关
else if (s[i] == '('){
STATE = NUMBER_STATE;
compuate_flag = 0;
}
else if (s[i] == ')'){
compute(number_stack, operation_stack);
}
else if (s[i] >= '0' && s[i] <= '9'){
STATE = NUMBER_STATE;
i--;
}
break;
}
}
// 返回最后运算结果
return number_stack.top();
}
};
int main(){
std::string s = "1+121 - (14+(5-6) )";
Solution solve;
printf("1+121-(14+(5-6)) = %d\n", solve.calculate(s));
return 0;
}
预备知识：STL 优先级队列（二叉堆）
数组中第 K 大的数（堆）（★）
- LeetCode 215.Kth Largest Element in an Array.cpp
#include <stdio.h>
#include <vector>
#include <queue>
class Solution {
public:
int findKthLargest(std::vector<int>& nums, int k) {
// 最小堆，堆顶为最小值
std::priority_queue<int, std::vector<int>, std::greater<int> > Q;
// 遍历 nums 数组
for (int i = 0; i < nums.size(); i++){
// 使堆里元素个数为 k
if (Q.size() < k){
Q.push(nums[i]);
}
// 使堆里为数组最大的 k 个数
else if (Q.top() < nums[i]){
Q.pop();
Q.push(nums[i]);
}
}
// 返回堆顶元素
return Q.top();
}
};
int main(){
std::vector<int> nums;
nums.push_back(3);
nums.push_back(2);
nums.push_back(1);
nums.push_back(5);
nums.push_back(6);
nums.push_back(4);
Solution solve;
printf("数组 [3, 2, 1, 5, 6, 4] 第 2 大的数为：%d\n", solve.findKthLargest(nums, 2));
return 0;
}
寻找中位数（堆）（★★★）
- LeetCode 295.Find Median from Data Stream.cpp
#include <stdio.h>
#include <queue>
class MedianFinder {
private:
// 最大堆构造
std::priority_queue<double, std::vector<double>, std::less<double> > big_queue;
// 最小堆构造
std::priority_queue<double, std::vector<double>, std::greater<double> > small_queue;
public:
MedianFinder() {
}
void addNum(double num) {
// 如果最大堆空，push 到最大堆
if (big_queue.empty()){
big_queue.push(num);
return;
}
// 如果最大堆、最小堆个数相同
if (big_queue.size() == small_queue.size()){
// 若小于最大堆堆顶，push 到最大堆
if (num < big_queue.top()){
big_queue.push(num);
}
// 若大于最小堆堆顶，push 到最小堆
else{
small_queue.push(num);
}
}
// 如果最大堆个数 > 最小堆个数
else if(big_queue.size() > small_queue.size()){
// 若大于最大堆堆顶，push 到最小堆
if (num > big_queue.top()){
small_queue.push(num);
}
// 若小于最大堆堆顶
else{
// 最大堆堆顶 push 到最小堆堆顶
small_queue.push(big_queue.top());
// 替换最大堆堆顶
big_queue.pop();
big_queue.push(num);
}
}
// 如果最大堆个数 < 最小堆个数
else if(big_queue.size() < small_queue.size()){
// 若小于最小堆堆顶，push 到最大堆
if (num < small_queue.top()){
big_queue.push(num);
}
// 若大于最小堆堆顶
else{
// 最小堆堆顶 push 到最大堆堆顶
big_queue.push(small_queue.top());
// 替换最小堆堆顶
small_queue.pop();
small_queue.push(num);
}
}
}
// 寻找中位数函数
double findMedian(){
// 若两堆个数相同，返回平均数
if (big_queue.size() == small_queue.size()){
return (big_queue.top() + small_queue.top()) / 2;
}
// 若最大堆个数多，返回最大堆堆顶
else if (big_queue.size() > small_queue.size()){
return big_queue.top();
}
// 若最小堆个数多，返回最小堆堆顶
return small_queue.top();
}
};
int main(){
MedianFinder M;
double test[] = {1.2, 3.4, 4.5, 2.3, 5.6, 8.9};
for (int i = 0; i < 6; i++){
M.addNum(test[i]);
}
printf("数组 [1.2, 3.4, 4.5, 2.3, 5.6, 8.9] 的中位数为：%lf\n", M.findMedian());
return 0;
}
