第十二天今天这个还好写一点嗷。一、用栈实现队列题目请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty。解答双栈倒腾既然队列是先进先出而栈是先进后出所以干脆整两个栈。把第一个栈弹出的东西在压入第二个栈实现栈的反转。public class MyQueue { Stackint stack1; Stackint stack2; public MyQueue() { stack1 new Stackint(); stack2 new Stackint(); } public void Push(int x) { stack1.Push(x); } public int Pop() { if(stack2.Count 0) while(stack1.Count ! 0) stack2.Push(stack1.Pop()); return stack2.Pop(); } public int Peek() { if(stack2.Count 0) while(stack1.Count ! 0) stack2.Push(stack1.Pop()); return stack2.Peek(); } public bool Empty() { return stack1.Count 0 stack2.Count 0; } }二、最小栈题目设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。解答一列表处理依旧超时写法最直觉的办法是用一个List存所有元素取最小值时排序一下取第一个。public class MinStack {Listint list null;public MinStack() {list new Listint();}public void Push(int value) {list.Add(value);}public void Pop() {list.RemoveAt(list.Count - 1);}public int Top() {return list[list.Count - 1];}public int GetMin() {Listint tempList list.OrderBy(x x).ToList();return tempList[0];}}依旧超时写法哇。解法二依旧用两个栈为了在 O(1) 时间取到最小值可以用一个辅助栈minStack它和数据栈stack同步入栈、出栈但minStack只存当前栈状态下的最小值。public class MinStack { Stack Sta null; Stack minSta null;//只存最小值 public MinStack() { Sta new Stack(); minSta new Stack(); } public void Push(int value) { Sta.Push(value); if(minSta.Count 0 || value minSta.Peek()){ minSta.Push(value); }else{ minSta.Push(minSta.Peek()); } } public void Pop() { Sta.Pop(); minSta.Pop(); } public int Top() { return Sta.Peek(); } public int GetMin() { return minSta.Pop(); } }还是两个栈好用一点一个存数据另一个只存最小值。