How can one implement a queue with only a stack implementation?

Question

Chu Chu · Accepted Answer

You will need at least two stacks.

public class Queue
{

    private Stack inbox = new Stack();
    private Stack outbox = new Stack();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}

Nitish · Answer

#include
#include
using namespace std;
stack st1, st2;

int pop(  )
{
if (!st1.empty())
{
int t,t1;
while(st1.size() != 1)
{
t = st1.top();
st1.pop();
st2.push(t);
}
t1 = st1.top();
st1.pop();
while(st2.size())
{
t = st2.top();
st2.pop();
st1.push(t);
}
return t1;
}

}
int main()
{


st1.push(2);
st1.push(3);
st1.push(4);
st1.push(5);
st1.push(6);
cout<

Anonymous · Answer

you have double ended queue (Deque) and insertion and removal can be handled at both end either left or right.

But if you want to implement Queue as stack, then restrict the operation at any one end
either left.  So Front and rear both become at the same end.

Anonymous · Answer

Never mind my previous answer was wrong implementation. It is actually implementing stack using Queue.

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?