代碼隨想錄：棧與隊列
隊列是先進先出，棧是先進后出
棧和隊列都是數(shù)據(jù)結(jié)構(gòu)
棧提供push和pop等接口，所有元素必須符合先進后出的規(guī)則，所以棧不能提供走訪功能，也不提供迭代器，不像set集合和map映射一樣提供迭代器來遍歷所有元素
棧使用底層容器來完成所有的工作，對外提供統(tǒng)一的接口，底層容器可插拔，我們可以控制使用哪種容器來實現(xiàn)棧的功能，所以STL中的棧往往被歸類為容器適配器
C++棧的底層實現(xiàn)可以是vector，deque，list，主要是數(shù)組和鏈表的底層實現(xiàn)，常用的SGI STL如果不指定底層實現(xiàn)則默認(rèn)為deque，deque是一個雙向隊列，只要封住雙向隊列的一端只從另一端操作就可以實現(xiàn)棧的邏輯
C#中棧的兩種實現(xiàn)方式一種是用鏈表實現(xiàn)，像普通鏈表一樣存儲元素，但是每個元素指針指向它的前一個節(jié)點，然后就只需用一個指針去指向最后一個元素（棧頂指針），進棧時就可以直接添加元素到棧頂元素后面，再把棧頂元素更新成新元素即可，出棧就讓棧頂指針指向的元素輸出然后指針指向前一個元素即可。另一種是用數(shù)組（順序表）實現(xiàn)，用下標(biāo)代替指針的作用，棧頂元素指向下一個元素進棧的位置，取棧頂元素時要取棧頂元素指針減一的下標(biāo)
鏈表插入元素必須指向上一個元素的位置然后讓新元素指向它，數(shù)組是連續(xù)存儲的所以不需要
C#中棧Stack<>，隊列Queue<>,若要使用雙向隊列則可以使用LinkedList<>
力扣232：用棧實現(xiàn)隊列
public?class?MyQueue
//用棧實現(xiàn)隊列的操作就需要使用兩個棧，一個輸入棧一個輸出棧，進行push的時候就直接將數(shù)據(jù)放進輸入棧，進行pop的時候就先看輸出棧中有沒有數(shù)據(jù)，因為棧是先進先出的，將輸入棧中的數(shù)據(jù)挨個取出放到輸出棧后先進入輸入棧的數(shù)據(jù)就會在輸出棧的頂端，因此pop時若輸出棧中有數(shù)據(jù)就先彈出數(shù)據(jù)，若沒有就把輸入棧的數(shù)據(jù)全部導(dǎo)入到輸出棧再從輸出棧中彈出數(shù)據(jù)。判斷是否為空就看輸入棧和輸出棧若都為空隊列就是空的。
{
????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操作的實現(xiàn)直接使用pop操作，額外增加一部將pop彈出的元素加入輸出棧頂?shù)牟僮骷纯?/p>
????}
????
????public?bool?Empty()
????{
????????return?stin.Count?==?0?&&?stout.Count?==?0;
????}
}
力扣225：用隊列實現(xiàn)棧
public?class?MyStack
//用兩個隊列模擬棧，在進棧時直接填入隊列中，出棧時先將隊列中除了最后一個元素（最新進的元素）移動到備份隊列中，將隊列中剩下的那個元素彈出，再將備份隊列中的元素移動回隊列中即可，代碼實現(xiàn)與上一題類似，只是多了一步將備份隊列元素移動回隊列中的操作
{
????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;
????}
}
//用一個隊列也可以模擬棧，將隊列的尾部當(dāng)作備份隊列，把頭部的元素全部添加到尾部，此時頭部彈出的元素就是原來隊列最尾部的元素，代碼如下
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?{
//遍歷整個字符串，遇到左括號時就向棧中填入對應(yīng)的右括號，不是左括號時就看棧中是否為空，空的話說明有多余右括號所以不匹配，不是空的話看棧頂是否與當(dāng)前字符串相同，若不同說明當(dāng)前這對左右括號不匹配，當(dāng)全部遍歷后若棧不為空則說明有多余左括號所以不匹配。
????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?{
//遍歷整個數(shù)組，將數(shù)字挨個加入棧中，當(dāng)加入的是運算符時說明前面兩個數(shù)字需要進行此計算，將兩個數(shù)字彈出并將運算結(jié)果加入棧，這樣循環(huán)至數(shù)組結(jié)束整個棧中只會留下一個結(jié)果數(shù)字，將其彈出作為結(jié)果即可
????
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<>來存放索引，從頭到尾元素不斷減小，這樣構(gòu)造出一個單調(diào)隊列，遍歷整個數(shù)組，對于tail指向的每一個數(shù)比較隊列尾部是否比它小，比它小就去掉直到隊列內(nèi)都比它大，再將這個數(shù)填入隊列尾部，這樣在head和tail移動過程中單調(diào)數(shù)列l(wèi)ist的頭部即為此窗口內(nèi)最大值。
????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就是窗口結(jié)束
????????while?(tail<nums.Length)
????????{
????????????while?(list.Count!=0&&?nums[list.Last.Value]<nums[tail])
????????????{
????????????????list.RemoveLast();
//刪除list中比tail所指的數(shù)小的部分
????????????}
????????????list.AddLast(tail);
????????????if?(list.First.Value<head)
????????????{
????????????????list.RemoveFirst();
//list.First的下標(biāo)比head小說明這個數(shù)不在當(dāng)前窗口內(nèi)應(yīng)刪除
????????????}
????????????if(head>=0){
????????????????result[head]?=?nums[list.First.Value];
//head>0時head所指的數(shù)才有意義，提交時未判斷導(dǎo)致了數(shù)據(jù)異常，數(shù)組result對應(yīng)head下標(biāo)的數(shù)就是nums數(shù)組中下標(biāo)list.First.Value的數(shù)
????????????}
????????????
????????????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);
//建立映射，將每個出現(xiàn)的數(shù)字的Value設(shè)置為其出現(xiàn)次數(shù)
????????????}
????????}
????????PriorityQueue<int,int>pq=new();
//PirorityQueue<TElement,TPriority>當(dāng)執(zhí)行Dequeue()操作時會先去掉優(yōu)先級低的元素，這里利用這一點便可以做成一個小頂堆，只保留出現(xiàn)次數(shù)最多的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();
//因為小頂堆會先彈出出現(xiàn)次數(shù)少的，所以數(shù)組需要逆序輸出才能得到正確答案
????????}
????????return?result;
????}
}
力扣42：接雨水
public?class?Solution?{
//構(gòu)造一個單調(diào)棧，每當(dāng)遇到添加的新元素下標(biāo)對應(yīng)的值高于棧頂元素說明容器產(chǎn)生了凹槽可以蓄水，進行一次計算，此時計算的就是以棧頂代表的柱子為容器底所能盛水的量。隨后彈出棧頂元素繼續(xù)比較直到新加的柱子高度小于等于棧頂柱子高度，將新元素入棧
????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);
//等高的話更新成新柱子下標(biāo)，其實這里也可以不加，效果是一樣的但是計算思路是拿左面的當(dāng)?shù)缀陀颐娴漠?dāng)?shù)椎膮^(qū)別
????????????}
????????????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]);
//新柱子高度大于棧頂，右邊柱子下標(biāo)i，左邊stack.Peek,水高度是左右兩柱子最矮的減去容器底柱子高度，因為只計算兩柱子中間的容量所以底邊長為右減左加一
????????????????????}
????????????????}
????????????????
????????????????stack.Push(i);
????????????}
????????????
????????}
????????return?sum;
????}
}
