Two possible solutions

• This is trivial problem and can be easly solved using either one or two queues.

First the two queue solutions:

``````class MyStack {

private Queue<Integer> full = new LinkedList<>();
private Queue<Integer> empty = new LinkedList<>();

// Push element x onto stack.
public void push(int x) {

full.offer(x);
}

// Removes the element on top of the stack.
public void pop() {

copyAllButOne();
full.remove();
swap();
}

// Get the top element.
public int top() {

copyAllButOne();
final int result = full.remove();
empty.offer(result);
swap();
return result;
}

// Return whether the stack is empty.
public boolean empty() {

return full.isEmpty();
}

private void copyAllButOne() {
while(full.size() > 1) {
empty.offer(full.remove());
}
}

private void swap() {
Queue<Integer> tmp = full;
full = empty;
empty = tmp;
}
}
``````

Secondly the single queue solution, as long as your queue implementation provides size() method you can easly implement it.

``````class MyStack {
private final Queue<Integer> queue = new LinkedList<>();

// Push element x onto stack.
public void push(int x) {

queue.offer(x);
}

// Removes the element on top of the stack.
public void pop() {

moveAllButOne();
queue.remove();
}

// Get the top element.
public int top() {

moveAllButOne();
final int result = queue.remove();
queue.offer(result);
return result;
}

// Return whether the stack is empty.
public boolean empty() {

return queue.isEmpty();
}

private void moveAllButOne() {
for(int count = queue.size(); count > 1; count--) {
queue.offer(queue.remove());
}
}
}
``````

In terms of performence and memory usage both solutions are (almost) the same.

With running time of the methods as fallows:

empty() - O(1)
push() - O(1)
pop() - O(N)
top() - O(N)

And memory usage of O(N) for both solutions.

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