Stack using a queue

Question

I was browsing through some interview questions and stumbled upon this. It got me tearing my hair apart.

Does anyone know how to implement a stack using queue?.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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();
  }
}