494. Implement Stack by Two Queues

Leave a comment

September 3, 2016 by oneOokay

两个queue,其中一个queue作为primary queue,另一个queue用来倒values。每一次的pop, top, push结束之后,所有的元素都应该以正确的顺序存在于primary queue中,这样才不会逻辑混乱。再注意一下把重复的代码做成单独的method。

class Stack {
// Push a new item into the stack

private Queue<Integer> queue1 = new LinkedList<Integer>();
private Queue<Integer> queue2 = new LinkedList<Integer>();

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

public void moveItems(){//把primary queue里面的元素除了最后一个以外,都移到temporary queue里
while (queue1.size() > 1)
{
queue2.add(queue1.poll());
}
}

public void swapQueues(){

Queue<Integer> tmp = new LinkedList<Integer>();
tmp = queue2;
queue2 = queue1;
queue1 = tmp;
}

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

// Return the top of the stack
public int top() {
moveItems();
int result = queue1.poll();
swapQueues();
queue1.add(result);
return result;
}

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: