Leecode---栈---每日温度 / 最小栈及栈和队列的相互实现

栈：先入后出；队列：先入先出

一、每日温度
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();}
};