How could I implement a stack using a queue?
-
1Here's a question dealing with using two queues: stackoverflow.com/questions/688276/…eldarerathis– eldarerathis2010-10-28 02:01:46 +00:00Commented Oct 28, 2010 at 2:01
Add a comment
|
4 Answers
push: insert the element into the back of the queue.
pop: remove an element from the front, insert it immediately in the back, repeat N-1 times, where N is the size of the queue, then remove the last element and return it.
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
class MyStack {
Queue<Integer> q;
/** Initialize your data structure here. */
public MyStack() {
q = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
q.offer(x);
for(int i = 1 ; i < q.size() ; i++) {
q.offer(q.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return q.isEmpty() ? -1 : q.poll();
}
/** Get the top element. */
public int top() {
return q.isEmpty() ? -1 : q.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q.isEmpty();
}
}
Comments
Version A:
push:
enqueue in queue1
pop:
while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2 dequeue and return the last item of queue1, then switch the names of queue1 and queue2
Version B:
push:
enqueue in queue2 enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
pop:
deqeue from queue1
Comments
Concept of using one queue to implement stack takes O(2n) or (machine independent) O(n) space complexity. But when you are working for a large size array double of size might not be available, also time complexity is O(n^2)or precisely O(n*(n+1)/2) in case you try to use only one queue.
