6

How could I implement a stack using a queue?

Adriaan
  • 17,741
  • 7
  • 42
  • 75
Chander Shivdasani
  • 9,878
  • 20
  • 76
  • 107
  • 1
    Here's a question dealing with using two queues: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues – eldarerathis Oct 28 '10 at 02:01

4 Answers4

5

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.

Eugene Smith
  • 9,126
  • 6
  • 36
  • 40
  • I refreshed the page right before I started answering only to find this answer posted already =( Good job! =) – BeemerGuy Oct 28 '10 at 02:07
  • @EugeneSmith does that meant that the pop operation here is O(N) when the stack is implemented with just one queue? – J_Y Oct 27 '20 at 08:26
1

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.

enter image description here

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();
  }
}
Girish Rathi
  • 129
  • 1
  • 4
0

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

Maulzey
  • 4,100
  • 5
  • 22
  • 30
0

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.

Vishesh Sharma
  • 1