題目描述 用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。 解題思路 棧：先進後出，隊列：先進先出。用兩個【先進後出】的實現一個【先進先出】。對於兩個棧而言，插入的時候沒有什麼問題，直接插入就可以，出棧的時候，需要藉助另外一個棧操作。簡單的來說就是負負為正。這裡有 ...
題目描述
用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。
解題思路
棧：先進後出，隊列：先進先出。用兩個【先進後出】的實現一個【先進先出】。對於兩個棧而言，插入的時候沒有什麼問題，直接插入就可以，出棧的時候，需要藉助另外一個棧操作。簡單的來說就是負負為正。這裡有個效率問題，進棧的第一個數據不用pop到出棧中直接返回就可以了。
基礎屬性
/// <summary> /// 出棧 /// </summary> private Stack<int> dequeue; /// <summary> /// 進棧 /// </summary> private Stack<int> enqueue; public Coding005() { dequeue = new Stack<int>(); enqueue = new Stack<int>(); }
進棧
/// <summary> /// 進棧 /// </summary> /// <param name="item"></param> public void Enqueue(int item) { enqueue.Push(item); }
出棧
/// <summary> /// 出棧 /// </summary> /// <returns></returns> public int Dequeue() { //沒有數據 if (enqueue.Count == 0 && dequeue.Count == 0) { return -1; } while (enqueue.Count > 0) { var item = enqueue.Pop(); dequeue.Push(item); } return dequeue.Pop(); }
優化過的出棧
/// <summary> /// 出棧（優化） /// </summary> /// <returns></returns> public int Dequeue2() { //沒有數據 if (enqueue.Count == 0 && dequeue.Count == 0) { return -1; } while (enqueue.Count > 1) { var item = enqueue.Pop(); dequeue.Push(item); } if (enqueue.Count == 1) { return enqueue.Pop(); } else { return dequeue.Pop(); } }
測試
[Fact] public void Test1() { Coding005 coding005 = new Coding005(); Queue<int> queue = new Queue<int>(); coding005.Enqueue(1); queue.Enqueue(1); coding005.Enqueue(2); queue.Enqueue(2); coding005.Enqueue(3); queue.Enqueue(3); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); } [Fact] public void Test2() { Coding005 coding005 = new Coding005(); Queue<int> queue = new Queue<int>(); coding005.Enqueue(1); queue.Enqueue(1); coding005.Enqueue(2); queue.Enqueue(2); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); coding005.Enqueue(3); queue.Enqueue(3); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); } [Fact] public void Test3() { Coding005 coding005 = new Coding005(); Queue<int> queue = new Queue<int>(); coding005.Enqueue(1); queue.Enqueue(1); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); } [Fact] public void Test4() { Coding005 coding005 = new Coding005(); Queue<int> queue = new Queue<int>(); coding005.Enqueue(1); queue.Enqueue(1); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); coding005.Enqueue(2); queue.Enqueue(2); coding005.Enqueue(3); queue.Enqueue(3); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); Assert.Equal(queue.Dequeue(), coding005.Dequeue()); }View Code
想入非非：擴展思維，發揮想象
1. 棧和隊列的熟悉
2. 兩個隊列實現棧
兩個隊列實現棧
思路：把進隊列的數據最後一個返回，每次都是返回進隊列的最後一個數據。第二個隊列主要用於保存臨時數據，之後做交換用的。
/// <summary> /// 棧和隊列:用兩個隊列實現棧 /// </summary> public class HStack { /// <summary> /// 出棧 /// </summary> private Queue<int> pop; /// <summary> /// 進棧 /// </summary> private Queue<int> push; public HStack() { pop = new Queue<int>(); push = new Queue<int>(); } /// <summary> /// 出棧 /// </summary> /// <returns></returns> public int Pop() { //沒有數據 if (push.Count == 0 && pop.Count == 0) { return -1; } while (push.Count > 1) { var item = push.Dequeue(); pop.Enqueue(item); } int result = push.Dequeue(); //數據交換回去 var temp = pop; pop = push; push = temp; return result; } /// <summary> /// 進棧 /// </summary> /// <param name="item"></param> public void Push(int item) { push.Enqueue(item); } }View Code
