LeetCode -- Implement Queue using Stacks

LeetCode -- Implement Queue using Stacks

題目描述：


Implement the following operations of a queue using stacks.


push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).




思路：
本題考查的就是使用兩個棧來實現一個隊列，主要還是對棧本身的一個熟悉。
1.使用s1和s2兩個棧
2.push時，直接入s2
3.pop時，先把s2的item 彈出入s1，再從s1中彈出1個，再將s1中元素逐個入s2
4.peek，類似pop，區別在於只取值但不刪除。將s2的每個item彈出入s1，n = s1.pop(),然後將s1元素逐個彈入s2，返回n。
5.empty，判斷s2是否為空即可。


實現代碼：

public class Queue {
    public Queue(){
        _s1 = new Stack();
        _s2 = new Stack();
    }
    private Stack _s1 ;
    private Stack _s2;
    // Push element x to the back of queue.
    public void Push(int x) {
        _s2.Push(x);
    }
    
    // Removes the element from front of queue.
    public void Pop() {
        while(_s2.Count > 0){
            _s1.Push(_s2.Pop());
        }
        _s1.Pop();
        while(_s1.Count > 0)
        {
            _s2.Push(_s1.Pop());
        }
    }


    // Get the front element.
    public int Peek() {
		while(_s2.Count > 0){
			_s1.Push(_s2.Pop());
		}
		
        var n = _s1.Peek();
		while(_s1.Count > 0){
			_s2.Push(_s1.Pop());
		}
        return n;
    }


    // Return whether the queue is empty.
    public bool Empty() {
        return _s2.Count == 0;
    }
}