CareerCup

This works and is O(n) amortized.

Let us not talk about practicality in questions like "make stack using only one queue", which probably will never arise in real life, apart from testing problem solving abilities of a candidate in an interview.

Sorry that was O(1) amortized.

Of course you need to keep track of the count when you have to do the cycle again (which is missing from above solution).

Basically you need to maintain the number of elements which can be popped by Deque. If that count goes to zero, you do the cycle.

Here is some (psuedo)code trying to use the above answers

class <T> Stack {
    public push(T elem) {
        _stack.Enqueue(elem);
    }
    
    public T pop() {
        if (_stack.IsEmpty()) throw StackEmptyException;
    
        if (numPushable == 0) {
            int numToCycle = _stack.Count;
            while (numToCycle > 0) {
                T elem = _stack.Dequeu();
                _stack.Enqueue(T);
                _numPushable++;
                numToCycle--;   
            }
        }
        _numPushable--;
        return _stack.Dequeu();
    }
    private Queue<T> _stack;
    private int _numPushable = 0;
}

This an incorrect solution.

push push push pop push push pop

will give wrong answer.

Yes this works I think.

Code:

class <type T> Stack {
    public void push(T elem) {
        _stack.enque(elem);
    }
    
    public T pop() {
        _stack.reverse();
        T elem  = _stack.deque();
        _stack.reverse();
    }
    private Queue<T> _stack;
}

What if we wanted a fast pop, but push could be slower?

You don't get the point of this site, Richa.

What good does it do a candidate to post a question here, if they have already been through it in an interview and have failed to answer it?

The point of posting here is to let _other_ people know what kind of questions are being asked.

This site is just a repository of questions. People post the problems they were asked, not necessarily the problems they want the solution to, irrespective of whether a web-search gives the solution.

Yeah, so a -1 for that inane lmgtfy link.

No Anon this website is very disorganized already. I propose a stack overflow kind of implementation.

No Anon this website is very disorganized already. I propose a stack overflow kind of implementation.