栈：先入后出；队列：先入先出
一、每日温度
Leecode—739题目：
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
单调栈思路：
1、新建一个存储数组下标的栈，将数组元素的下标依次入栈；
2、入栈的过程中，要保证栈是单调的；如果此时数组元素大于栈顶下标对应的数组元素，弹出栈顶，再将此时的下标i入栈；
3、在这个过程中，下标i挤掉栈顶下标的时候，i-stack.top()，这个值就是我们要的“下一天”；没有出现“挤掉”情况的下标，也就是最后栈中仍剩余的下标，就是未来没有更高的温度，在answer数组中对应下标为初始的0即可。
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& temperatures)
{
int n = temperatures.size();
vector<int> answer(n);
// 存储下标的单调栈
stack<int> tmp;
for(int i=0; i<n; i++)
{
// 若栈不为空，且t[i]>栈顶
while(!tmp.empty() && temperatures[i] > temperatures[tmp.top()])
{
// 记录栈顶的下标
int top_Index = tmp.top();
// 当前栈顶对应的下标，它的‘下一天’就是 i-tmp.top()
answer[top_Index] = i - top_Index;
tmp.pop();
}
// 单调栈，将小于栈底的下标入栈
tmp.push(i);
}
return answer;
}
};
二、最小栈
Leecode–155：
题目：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
class MinStack
{
public:
// 定义两个栈容器
stack<int> st;
stack<int> minStack;
// 构造函数清空栈容器
MinStack()
{
while(!st.empty())
{
st.pop();
}
while(!minStack.empty())
{
minStack.pop();
}
// 初始化最小栈的栈顶元素为最大值，为了防止top访问空指针报错
minStack.push(INT_MAX);
}
void push(int x)
{
st.push(x);
// 比较最小栈栈顶值和当前值x的大小，将最小值压入最小栈
// 记录当前st栈的最小值为栈顶元素
int minval = std::min(minStack.top(),x);
minStack.push(minval); // 最小值压入最小栈
}
void pop()
{
st.pop();
minStack.pop();
}
int top()
{
return st.top();
}
int getMin()
{
// 取最小栈的栈顶元素，就是此时st栈的最小值
return minStack.top();
}
};
三、用队列实现栈
问题描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶(入栈)。
int pop() 移除并返回栈顶元素（出栈）。
int top() 返回栈顶元素（取栈顶）。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
class MyStack
{
queue<int> q; // 定义一个队列
public:
MyStack(){
}
void push(int x) // 入栈
{
int n = q.size();
q.push(x);
for(int i=0; i<n; i++)
{
q.push(q.front()); // 将队头放入队尾
q.pop(); // 移除队头
}
}
int pop() // 出栈==出队，有返回值，记录队头->移除队头->返回所记录的队头
{
int t = q.front();
q.pop();
return t;
}
int top() // 取栈顶==取队头
{
int t = q.front();
return t;
}
bool empty() // 判断栈空==判断队空
{
return q.empty();
}
};
四、用栈实现队列
top()是取栈顶元素，不会删除里面的元素，返回栈顶的引用；
pop()是删除栈顶元素，返回void。
int peek() :返回队列开头的元素
void push(int x): 将元素x放到队列的末尾
int pop() : 从队列开头移除并返回元素
boolean empty() : 若队列为空，返回true，否则返回false
算法实现：
用两个栈模拟一个队列，s1为输入栈，s2为输出栈；
1、push(x)：将x放入s1；
2、pop()：若s2为空，则将s1中所有的元素放入s2，s2的栈顶出栈，并返回栈顶元素；
3、peek()：若s2为空，将s1中所有的元素放入s2，并返回栈顶元素；
4、empty()：若s1 / s2都为空，返回true，否则返回false。
class MyQueue
{
private:
stack<int> s1, s2; // s1为输入栈，s2为输出栈
void int_2_out()
{
// 如果输出栈为空，则将输入栈所有元素放入输出栈
if (s2.empty())
{
while(!s1.empty())
{
//s1先把栈顶元素取出来放入s2，然后再pop删除，s1为空则停止
s2.push(s1.top());
s1.pop();
}
}
}
public:
MyQueue()
{
}
void push(int x) // 入队
{
s1.push(x);
}
int pop() // 模拟出队
{
// pop是从输出栈出栈
int_2_out(); // 判断输出栈是否为空，若为空，将输入栈放入输出栈
int x = s2.top();
s2.pop();
return x; // 返回栈顶
}
int peek() // 取队头操作
{
in_2_out();
return s2.top();
}
bool empty() // 栈 s1/s2 都为空，队列才为空
{
return s1.empty() && s2.empty();
}
};
