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();
	}
};