# One Queue Java Solution

• ``````class MyStack {

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

// Removes the element on top of the stack.
public void pop() {
int size = q.size();
for(int i = 1; i < size; i++)
q.remove();
}

// Get the top element.
public int top() {
int size = q.size();
for(int i = 1; i < size; i++)
int ret = q.remove();
return ret;
}

// Return whether the stack is empty.
public boolean empty() {
return q.isEmpty();
}
}``````

• the complexity should be O(N^2) ?

• O(N) you can both insert and remove from the queue in O(1) time. So if you do that N times your total time complexity will be O(N)

• Still confused, for example:
in pop(), every time it will do a for loop, e.g existing "1,2,3,4,5" in the queue,
pop 5, need loop 4 times;
pop 4, need loop 3 times, ...
so totally need 4 + 3 + ... + 1 times, shouldn't be O(n^2)?

• Ahh, yes, if you are considering the client code that is inserting N times into the stack and them N times remove the values than yes such code is running in O(N^2) time.

Although most of the times all you do is provide the running time of each individual method so those will be O(N) for top and pop and constant for remaining.

• i think you can optimize this solution by caching the top value each time you pop. which will reduce the order of your top function to be O(1).

• If pop and top is not O(1), is it a Stack?

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