代码随想录：栈与队列
队列是先进先出，栈是先进后出
栈和队列都是数据结构
栈提供push和pop等接口，所有元素必须符合先进后出的规则，所以栈不能提供走访功能，也不提供迭代器，不像set集合和map映射一样提供迭代器来遍历所有元素
栈使用底层容器来完成所有的工作，对外提供统一的接口，底层容器可插拔，我们可以控制使用哪种容器来实现栈的功能，所以STL中的栈往往被归类为容器适配器
C++栈的底层实现可以是vector，deque，list，主要是数组和链表的底层实现，常用的SGI STL如果不指定底层实现则默认为deque，deque是一个双向队列，只要封住双向队列的一端只从另一端操作就可以实现栈的逻辑
C#中栈的两种实现方式一种是用链表实现，像普通链表一样存储元素，但是每个元素指针指向它的前一个节点，然后就只需用一个指针去指向最后一个元素（栈顶指针），进栈时就可以直接添加元素到栈顶元素后面，再把栈顶元素更新成新元素即可，出栈就让栈顶指针指向的元素输出然后指针指向前一个元素即可。另一种是用数组（顺序表）实现，用下标代替指针的作用，栈顶元素指向下一个元素进栈的位置，取栈顶元素时要取栈顶元素指针减一的下标
链表插入元素必须指向上一个元素的位置然后让新元素指向它，数组是连续存储的所以不需要
C#中栈Stack<>，队列Queue<>,若要使用双向队列则可以使用LinkedList<>
力扣232：用栈实现队列
public class MyQueue
//用栈实现队列的操作就需要使用两个栈，一个输入栈一个输出栈，进行push的时候就直接将数据放进输入栈，进行pop的时候就先看输出栈中有没有数据，因为栈是先进先出的，将输入栈中的数据挨个取出放到输出栈后先进入输入栈的数据就会在输出栈的顶端，因此pop时若输出栈中有数据就先弹出数据，若没有就把输入栈的数据全部导入到输出栈再从输出栈中弹出数据。判断是否为空就看输入栈和输出栈若都为空队列就是空的。
{
private Stack<int> stin=new Stack<int>();
private Stack<int> stout=new Stack<int>();
public MyQueue() {
}
public void Push(int x) {
stin.Push(x);
}
public int Pop()
{
if (stout.Count == 0)
{
while (stin.Count!=0)
{
stout.Push(stin.Pop());
}
}
int result=stout.Pop();
return result;
}
public int Peek()
{
int res = Pop();
stout.Push(res);
return res;
//peek操作的实现直接使用pop操作，额外增加一部将pop弹出的元素加入输出栈顶的操作即可
}
public bool Empty()
{
return stin.Count == 0 && stout.Count == 0;
}
}
力扣225：用队列实现栈
public class MyStack
//用两个队列模拟栈，在进栈时直接填入队列中，出栈时先将队列中除了最后一个元素（最新进的元素）移动到备份队列中，将队列中剩下的那个元素弹出，再将备份队列中的元素移动回队列中即可，代码实现与上一题类似，只是多了一步将备份队列元素移动回队列中的操作
{
private Queue<int> que=new Queue<int>();
private Queue<int> backup = new Queue<int>();
public MyStack() {
}
public void Push(int x) {
que.Enqueue(x);
}
public int Pop() {
while (que.Count>1)
{
backup.Enqueue(que.Dequeue());
}
int result = que.Dequeue();
while (backup.Count!=0)
{
que.Enqueue(backup.Dequeue());
}
return result;
}
public int Top() {
while (que.Count>1)
{
backup.Enqueue(que.Dequeue());
}
int result=que.Dequeue();
backup.Enqueue(result);
while (backup.Count!=0)
{
que.Enqueue(backup.Dequeue());
}
return result;
}
public bool Empty() {
return que.Count==0;
}
}
//用一个队列也可以模拟栈，将队列的尾部当作备份队列，把头部的元素全部添加到尾部，此时头部弹出的元素就是原来队列最尾部的元素，代码如下
public class MyStack
{
private Queue<int> que=new Queue<int>();
public MyStack() {
}
public void Push(int x) {
que.Enqueue(x);
}
public int Pop()
{
int count = que.Count;
while (count-->1)
{
que.Enqueue(que.Dequeue());
}
return que.Dequeue();
}
public int Top() {
int count = que.Count;
while (count-->1)
{
que.Enqueue(que.Dequeue());
}
int result=que.Dequeue();
que.Enqueue(result);
return result;
}
public bool Empty() {
return que.Count==0;
}
}
力扣20：有效的括号
public class Solution {
//遍历整个字符串，遇到左括号时就向栈中填入对应的右括号，不是左括号时就看栈中是否为空，空的话说明有多余右括号所以不匹配，不是空的话看栈顶是否与当前字符串相同，若不同说明当前这对左右括号不匹配，当全部遍历后若栈不为空则说明有多余左括号所以不匹配。
public bool IsValid(string s)
{
Stack<int> stack = new Stack<int>();
for (int i = 0; i < s.Length; i++)
{
if (s[i]=='(')
{
stack.Push(')');
}
else if (s[i]=='[')
{
stack.Push(']');
}
else if (s[i]=='{')
{
stack.Push('}');
}
else if (stack.Count==0|| s[i]!=stack.Peek())
{
return false;
}
else
{
stack.Pop();
}
}
return stack.Count == 0;
}
}
力扣150：逆波兰表达式求值
public class Solution {
//遍历整个数组，将数字挨个加入栈中，当加入的是运算符时说明前面两个数字需要进行此计算，将两个数字弹出并将运算结果加入栈，这样循环至数组结束整个栈中只会留下一个结果数字，将其弹出作为结果即可
public int EvalRPN(string[] tokens)
{
Stack<int> stack = new Stack<int>();
foreach (var x in tokens)
{
if (x!="+"&& x!="-"&& x!="*"&& x!="/")
{
stack.Push(Convert.ToInt32(x));
}
else
{
int a = stack.Pop();
int b = stack.Pop();
if (x=="+")
{
stack.Push(b+a);
}
if (x=="-")
{
stack.Push(b-a);
}
if (x=="*")
{
stack.Push(b*a);
}
if (x=="/")
{
stack.Push(b/a);
}
}
}
return stack.Pop();
}
}
力扣239：滑动窗口最大值
public class Solution
{
//使用LinkedList<>来存放索引，从头到尾元素不断减小，这样构造出一个单调队列，遍历整个数组，对于tail指向的每一个数比较队列尾部是否比它小，比它小就去掉直到队列内都比它大，再将这个数填入队列尾部，这样在head和tail移动过程中单调数列list的头部即为此窗口内最大值。
public int[] MaxSlidingWindow(int[] nums, int k)
{
LinkedList<int> list = new LinkedList<int>();
int[] result = new int[nums.Length - k + 1];
int tail = 0, head = tail - k + 1;
//窗口大小为k，head就是窗口开始tail就是窗口结束
while (tail<nums.Length)
{
while (list.Count!=0&& nums[list.Last.Value]<nums[tail])
{
list.RemoveLast();
//删除list中比tail所指的数小的部分
}
list.AddLast(tail);
if (list.First.Value<head)
{
list.RemoveFirst();
//list.First的下标比head小说明这个数不在当前窗口内应删除
}
if(head>=0){
result[head] = nums[list.First.Value];
//head>0时head所指的数才有意义，提交时未判断导致了数据异常，数组result对应head下标的数就是nums数组中下标list.First.Value的数
}
head++;
tail++;
//窗口移动
}
return result;
}
}
力扣347：前k个高频元素
public class Solution {
public int[] TopKFrequent(int[] nums, int k) {
Dictionary<int,int> dic=new();
for(int i=0;i<nums.Length;i++){
if(dic.ContainsKey(nums[i])){
dic[nums[i]]++;
}
else{
dic.TryAdd(nums[i],1);
//建立映射，将每个出现的数字的Value设置为其出现次数
}
}
PriorityQueue<int,int>pq=new();
//PirorityQueue<TElement,TPriority>当执行Dequeue()操作时会先去掉优先级低的元素，这里利用这一点便可以做成一个小顶堆，只保留出现次数最多的k个元素
foreach(var x in dic){
pq.Enqueue(x.Key,x.Value);
if(pq.Count>k){
pq.Dequeue();
//堆大小大于k时弹出到只剩k个元素
}
}
int[] result=new int[k];
for(int j=k;j>0;j--){
result[j-1]=pq.Dequeue();
//因为小顶堆会先弹出出现次数少的，所以数组需要逆序输出才能得到正确答案
}
return result;
}
}
力扣42：接雨水
public class Solution {
//构造一个单调栈，每当遇到添加的新元素下标对应的值高于栈顶元素说明容器产生了凹槽可以蓄水，进行一次计算，此时计算的就是以栈顶代表的柱子为容器底所能盛水的量。随后弹出栈顶元素继续比较直到新加的柱子高度小于等于栈顶柱子高度，将新元素入栈
public int Trap(int[] height)
{
Stack<int> stack = new();
stack.Push(0);
int sum = 0;
for (int i=1;i<height.Length;i++)
{
if (height[i]<height[stack.Peek()])
{
stack.Push(i);
}
else if (height[i]==height[stack.Peek()])
{
stack.Pop();
stack.Push(i);
//等高的话更新成新柱子下标，其实这里也可以不加，效果是一样的但是计算思路是拿左面的当底和右面的当底的区别
}
else if (height[i]>height[stack.Peek()])
{
while(stack.Count!=0&&height[i]>height[stack.Peek()]){
int a=stack.Pop();
if(stack.Count!=0){
sum += (i - stack.Peek() - 1) * (Math.Min(height[stack.Peek()], height[i])-height[a]);
//新柱子高度大于栈顶，右边柱子下标i，左边stack.Peek,水高度是左右两柱子最矮的减去容器底柱子高度，因为只计算两柱子中间的容量所以底边长为右减左加一
}
}
stack.Push(i);
}
}
return sum;
}
}
