-1
$\begingroup$

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 .

$\endgroup$
  • 2
    $\begingroup$ What have you tried and where did you get stuck? What's your question? This is not a place to outsource your work. $\endgroup$ – Raphael Oct 5 '15 at 15:07
  • $\begingroup$ I got , ENQUEUE : reverse , push , reverse and DEQUEUE : pop ! $\endgroup$ – 1 0 Oct 5 '15 at 15:13
  • 2
    $\begingroup$ That's some code, but what are your thoughts? Have you tried your idea on some examples? Have you tried to prove it correct? $\endgroup$ – Raphael Oct 5 '15 at 15:20
2
$\begingroup$

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}$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.