# Implement Stack using Queues

• The third approach is really good.

• We can also make a one-queue solution with push ~ O(1) and pop ~ O(n)

// Push element x onto stack.
void push(int x) {
_top = x;
q.push(x);
}

``````// Removes the element on top of the stack.
void pop() {
for (int i = q.size() - 1; i--; ) _top = q.front(), q.push(_top), q.pop();
q.pop();
}``````

• The idea of the 3rd approach means rotating a queue, which has been included in some basic collection libraries.

• Using java dequeue to solve this!
public class MyStack {

``````Deque<Integer> queue;

/** Initialize your data structure here. */
public MyStack() {
}

/** Push element x onto stack. */
public void push(int x) {
queue.offerFirst(x);
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (!queue.isEmpty()) {
return queue.pollFirst();
}
return -1;
}

/** Get the top element. */
public int top() {
if (!queue.isEmpty()) {
return queue.peekFirst();
}
return -1;
}

/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
``````

}

• Didnt understand the second approach.
If we do Q1.remove() it will pop 1 instead of 2. Please let me know if I am wrong

• Actually the Approach #3 is the samilar with Approach #2 as just replacing the 2 Queues with the only one common shared Queue1 like a Ring. So the Approach #1 can also replacing the 2 Queues with the only one common shared Queue1 like a Ring.

• @sirykd Actually the Approach #3 is the samilar with Approach #2 as just replacing the 2 Queues with the only one common shared Queue1 like a Ring. So the Approach #1 can also replacing the 2 Queues with the only one common shared Queue1 like a Ring as your Approach.

• Maintaining top separately is not needed for Approach #2. q1.peek() can be returned as top.

1. Why the space complexity of Approach #2,#3 push method are O(1)??? I thought it O(N) because we need additional memory to store the elements in queue.
2. How to determine whether it is O(1) or O(N)?

• In the Approach #3 here is a wrong interface for `pop()`, the correct one should be:

``````    // Removes the element on top of the stack.
public int pop() {
return q1.remove();
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.