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.

分析:

queue1 = new LinkedList<Integer>();

在Java中,queue是个抽象的类,不能有具体的对象,其实现方法可以用LinkedList之类的数据结构,这点跟c++并不一样

解法:

class Stack {
    // Push a new item into the stack
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public Stack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }

    private void dumpElement() {
        while (queue1.size() != 1 ) {
            queue2.offer(queue1.poll() );
        }
    }

    private void swapQueue() {
        Queue<Integer> temp = queue2;
        queue2 = queue1; 
        queue1 = temp;
    }

    public void push(int x) {
        // Write your code here
        queue1.offer(x);
    }

    // Pop the top of the stack
    public void pop() {
        // Write your code here
        dumpElement();
        int res = queue1.poll();
        swapQueue();
    }

    // Return the top of the stack
    public int top() {
        // Write your code here
        dumpElement();
        int res = queue1.poll();
        swapQueue();
        queue1.offer(res);
        return res;
    }

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

results matching ""

    No results matching ""