[Solved]: implementation of queue using stack with REVERSE

Problem Detail: 

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions.

---

I'm looking for implementation of queue where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction , or any better algorithm .

Asked By : Mithlesh Upadhyay

Answered By : Lieuwe Vinkhuijzen

Your queue should append items to the rear of the stack, and get them off the top, so here's a pseudocode implementation of your two functions:

$\texttt{Queue::Enqueue}(e):$
$\quad$Reverse;
$\quad$Push($e$);
$\quad$Reverse;

$\texttt{Queue::Dequeue}():$
$\quad$__return__ Pop;

Verify for yourself whether and why these functions produce the desired behaviour: why does the $\texttt{Enqueue}$ function reverse the stack, but not $\texttt{Dequeue}$?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47892

 Ask a Question

 Download Related Notes/Documents