Qfyilyi

I have a queue with some numbers for example 5,6,7,8 is in queue, 5 is q->front and 8 is q->rear.. Can I reverse them in queue but without using stacks?

Of course! But it won't be as efficient.

Using a stack:              O(N) time.   O(1) memory.

Using an associative array: O(N) time.   O(1) memory.

Using a fixed-size array:   O(N) time.   O(N) memory.

Using an extendable array:  O(N) time.   O(N) memory.

Using a queue:              O(N^2) time. O(1) memory.

Using an associative array will use more time than using a stack, but the performance and memory usage of both will scale identically.

The following snippets show how each of those data structures can be used.

Stack:

# O(N) time. O(1) memory.

sub reverse_queue_using_stack {

   my ($in_q) = @_;



   my $stack = Stack->new();

   while ( my ($item) = $in_q->dequeue() ) {

      $stack->push($item);

   }



   my $out_q = Queue->new();

   while ( my ($item) = $stack->pop() ) {

      $out_q->enqueue($item);

   }



   return $out_q;

}

Associative array:

# O(N) time. O(1) memory.

sub reverse_queue_using_dict {

   my ($in_q) = @_;



   my $dict = Dictionary->new();

   my $i = 0;

   while ( my ($item) = $in_q->dequeue() ) {

      $dict->set($i++, $item);

   }



   my $out_q = Queue->new();

   while ($i--) {

      $out_q->enqueue($dict->delete($i));

   }



   return $out_q;

}

Fixed-size array (and a queue if you can't get the size of a queue):

# O(N) time. O(N) memory.

sub reverse_queue_using_array {

   my ($in_q) = @_;



   my $count = 0;

   my $queue = Queue->new();

   while ( my ($item) = $in_q->dequeue() ) {

      ++$count;

      $queue->enqueue($item);

   }



   my $array = Array->new($count);

   for my $i (0..$count-1) {

      $array->set($i, $queue->dequeue());

   }



   my $out_q = Queue->new();

   for (1..$count) {

      my $i = $count - $_;

      $out_q->enqueue($array->get($i));

   }



   return $out_q;

}

Extendable array:

# O(N) time. O(N) memory.

sub reverse_queue_using_list {

   my ($in_q) = @_;



   my $list = List->new();

   while ( my ($item) = $in_q->dequeue() ) {

      $list->append($item);

   }



   my $count = $list->size();



   my $out_q = Queue->new();

   for (1..$count) {

      my $i = $count - $_;

      $out_q->enqueue($list->get($i));

   }



   return $out_q;

}

Queue:

# O(N^2) time. O(1) memory.

sub reverse_queue_using_queue {

   my ($in_q) = @_;



   my $queue = Queue->new();

   my $out_q = Queue->new();

   while (1) {

      my ($tail) = $in_q->dequeue()

         or last;



      while ( my ($item) = $in_q->dequeue() ) {

         $queue->enqueue($tail);

         $tail = $item;

      }



      $out_q->enqueue($tail);

      ($in_q, $queue) = ($queue, $in_q);

   }



   return $out_q;

}

Tested using the following harness:

#!/usr/bin/perl

use strict;

use warnings;

use feature qw( say );



# The implementation of these don't matter;

# if the problem can be solved using only the methods provided by these classes,

# the problem can be solved using any implementation of these classes.



{

   package Queue;

   sub new     { my $class = shift; bless(, $class) }

   sub enqueue { my $self = shift; push @$self, @_; }

   sub dequeue { my $self = shift; @$self ? shift(@$self) : () }

}



{

   package Stack;

   sub new  { my $class = shift; bless(, $class) }

   sub push { my $self = shift; push @$self, @_; }

   sub pop  { my $self = shift; @$self ? pop(@$self) : () }

}



{

   package Array;  # Fixed-size array.

   use Carp qw( croak );

   sub new  { my ($class, $size) = @_; bless([ (undef) x $size ], $class) }

   sub size { my $self = shift; 0+@$self }

   sub get  { my ($self, $i) = @_; croak "!" if $i<0 || $i>=@$self; $self->[$i] }

   sub set  { my ($self, $i, $item) = @_; croak "!" if $i<0 || $i>=@$self; $self->[$i] = $item; }

}



{

   package List;  # Extendable array.

   use Carp qw( croak );

   sub new    { my $class = shift; bless(, $class) }

   sub size   { my $self = shift; 0+@$self }

   sub get    { my ($self, $i) = @_; croak "!" if $i<0; $self->[$i] }

   sub set    { my ($self, $i, $item) = @_; croak "!" if $i<0; $self->[$i] = $item; }

   sub append { my ($self, $item) = @_; push @$self, $item; }

}



{

   package Dictionary;

   use Carp qw( croak );

   sub new    { my $class = shift; bless({}, $class) }

   sub get    { my ($self, $k) = @_; croak "!" if !exists($self->{$k}); $self->{$k} }

   sub set    { my ($self, $k, $item) = @_; $self->{$k} = $item; }

   sub exists { my ($self, $k) = @_; exists($self->{$k}) }

   sub delete { my ($self, $k) = @_; croak "!" if !exists($self->{$k}); delete($self->{$k}) }

}





sub purge_queue {

   my ($q) = @_;



   my @vals;

   while ( my ($item) = $q->dequeue() ) {

      push @vals, $item;

   }



   return @vals;

}



# ...



for my $reverse_func_name (qw(

   reverse_queue_using_stack

   reverse_queue_using_dict

   reverse_queue_using_array

   reverse_queue_using_list

   reverse_queue_using_queue

)) {

   my $reverse_func = &$reverse_func_name;



   my $in_q = Queue->new();

   $in_q->enqueue($_) for 'a'..'j';



   my $out_q = $reverse_func->($in_q);

   say sprintf "%-26s %s", "$reverse_func_name:", join ' ', purge_queue($out_q);

}

You could use the recursive stack to reverse a queue internally:

#include <queue>



void reverseQueue(queue<int> &q) {

    if (!q.empty()) {

        int front = q.front();

        q.pop();

        reverseQueue(q);

        q.push(front);

    }

}

source