Monday, February 8, 2016

Implement Stack by Two Queues

Implement Stack by Two Queues

Implement a stack by two queues. The queue is first in first out (FIFO). That means you can not directly pop the last element in a queue.


Example
push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Stack {
    
    private Queue<Integer> q1 = new LinkedList<Integer>();
    private Queue<Integer> q2 = new LinkedList<Integer>();
    
    private void swapQueue() {
        Queue<Integer> tmp = q2;
        q2 = q1;
        q1 = tmp;
    }
    
    // Push a new item into the stack
    public void push(int x) {
        // Write your code here
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        swapQueue();
    }

    // Pop the top of the stack
    public void pop() {
        // Write your code here
        q1.poll();
    }

    // Return the top of the stack
    public int top() {
        // Write your code here
        return q1.peek();
    }

    // Check the stack is empty or not.
    public boolean isEmpty() {
        // Write your code here
        return q1.size() == 0;
    }    
}
Posted by at