# Only push is O(n), others are O(1). Using one queue. Combination of two shared solutions

• ``````class MyStack
{
Queue<Integer> queue;

public MyStack()
{
}

// Push element x onto stack.
public void push(int x)
{
for(int i=0;i<queue.size()-1;i++)
{
}
}

// Removes the element on top of the stack.
public void pop()
{
queue.poll();
}

// Get the top element.
public int top()
{
return queue.peek();
}

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

• This post is deleted!

• And I have a question: if using addAll() in Push(), is it O(1)?

`````` public void push(int x)
{

queue=temp;
}``````

• I think it is the same, as the function also push the elements of the queue one by one

• I like the idea of this solution as it is quite creative. But the push operation will become a very expansive when the queue grows large. In other words, this method has no clearly advantage in terms of efficiency.

• The idea is simple and great, but time consuming!

• There are two solutions cost O(n) and O(1) for different operations:

1. push: O(n), pop/top: O(1)
2. push: O(1), pop/top: O(n)

Time efficiency depends on operation frequency of push, pop, top:
if push>pop+top, second solution is better.
if push<pop+top, first solution is better.

And I feel, in most cases, push<pop+top.

This is same idea in C++:
https://leetcode.com/discuss/46975/a-simple-c-solution

• why is Only push is O(n), others are O(1). Using one queue?

• `private Queue<Integer> q1 = new LinkedList<>();`
anyone could explain how to understand this code from solution?
I mean why is it necessary to call Linkedlist<>()?
thank you!

• Nice solution. I just want to mention one thing, queue.poll() will return E(element) so I think method pop() should be public Integer pop(). Thanks.

• @YYZ90 My solution was similar, but I used a LinkedList instead :

``````public class StackWithQueues {

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

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

/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
return q.pollLast();
}

/**
* Get the top element.
*/
public int top() {
return q.peekLast();
}

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

}
``````

• @sixgod Queue is an interface in Java, and the LinkedList class implement Deque which is an interface extend Queue.

You can see the java document for the detail.

• This post is deleted!

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