我可以不使用堆栈而反转队列吗？ [英] Can I reverse a queue without using stack?

问题描述

我有一个带有一些数字的队列，例如5、6、7、8在队列中，5在q->前，8在q->后。我可以在队列中反转它们而不使用堆栈吗？ / p>

解决方案

当然！

 使用堆栈：O（N）时间。 O（1）内存。 
使用关联数组：O（N）时间。 O（1）内存。 
使用固定大小的数组：O（N）时间。 O（N）内存。 
使用可扩展数组：O（N）时间。 O（N）内存。 
使用队列：O（N ^ 2）次。 O（1）内存。 
  

使用关联数组将比使用堆栈花费更多的时间，但是两者的性能和内存使用量

以下片段展示了如何使用这些数据结构。

堆栈：

 ＃O （N）时间。 O（1）内存。 
 sub reverse_queue_using_stack {
 my（$ in_q）= @_; 
 
 my $ stack = Stack-> new（）; 
 while（my（$ item）= $ in_q-> dequeue（））{
 $ stack-> push（$ item）; 
} 
 
 my $ out_q =队列-> new（）; 
 while（my（$ item）= $ stack-> pop（））{
 $ out_q-> enqueue（$ item）; 
} 
 
 return $ out_q; 
} 
  

关联数组：

< pre class = lang-perl prettyprint-override> ＃O（N）时间。 O（1）内存。
sub reverse_queue_using_dict {
my（$ in_q）= @_;

my $ dict =字典-> new（）;
我的$ i = 0；
while（my（$ item）= $ in_q-> dequeue（））{
$ dict-> set（$ i ++，$ item）;
}

my $ out_q =队列-> new（）;
而（$ i--）{
$ out_q->入队（$ dict-> delete（$ i））;
}

return $ out_q;
}


固定大小的数组（如果无法获取大小，则排队

 ＃O（N）时间。 O（N）内存。 
 sub reverse_queue_using_array {
 my（$ in_q）= @_; 
 
我的$ count = 0; 
 my $ queue =队列-> new（）; 
 while（my（$ item）= $ in_q-&dequeue（））{
 ++ $ count; 
 $ queue-> enqueue（$ item）; 
} 
 
 my $ array = Array-> new（$ count）;我的$ i的
（0 .. $ count-1）{
 $ array-> set（$ i，$ queue-> dequeue（））; 
} 
 
 my $ out_q =队列-> new（）; 
 for（1 .. $ count）{
 my $ i = $ count-$ _; 
 $ out_q-&n; enqueue（$ array-> get（$ i））; 
} 
 
 return $ out_q; 
} 
  

可扩展数组：

< pre class = lang-perl prettyprint-override> ＃O（N）时间。 O（N）内存。
sub reverse_queue_using_list {
my（$ in_q）= @_;

我的$ list = List-> new（）;
而（my（$ item）= $ in_q-> dequeue（））{
$ list-> append（$ item）;
}

my $ count = $ list-> size（）;

my $ out_q =队列-> new（）;
for（1 .. $ count）{
my $ i = $ count-$ _;
$ out_q-&n;排队（$ list-> get（$ i））;
}

return $ out_q;
}


队列：

 ＃O（N ^ 2）时间。 O（1）内存。 
 sub reverse_queue_using_queue {
 my（$ in_q）= @_; 
 
 my $ queue =队列-> new（）; 
 my $ out_q =队列-> new（）; 
而（1）{
我的（$ tail）= $ in_q-> dequeue（）
或最后一个； 
 
而（my（$ item）= $ in_q-> dequeue（））{
 $ queue-> enqueue（$ tail）; 
 $ tail = $ item; 
} 
 
 $ out_q->排队（$ tail）; 
（$ in_q，$ queue）=（$ queue，$ in_q）; 
} 
 
 return $ out_q; 
} 
  

使用以下工具进行了测试：

 ＃！/ usr / bin / perl 
使用strict; 
使用警告； 
使用功能qw（say）; 
 
＃这些的执行无关紧要； 
＃如果仅使用这些类提供的方法可以解决问题，则
＃使用这些类的任何实现都可以解决问题。 
 
 {
 package Queue; 
 sub new {my $ class = shift; bless（[]，$ class）} 
子队列{my $ self = shift;推@ $ self，@_; } 
子出队{my $ self = shift; @ $ self？ shift（@ $ self）：（）} 
} 
 
 {
 package Stack; 
 sub new {my $ class = shift; bless（[]，$ class）} 
 sub push {my $ self = shift;推@ $ self，@_; } 
 sub pop {my $ self = shift; @ $ self？ pop（@ $ self）：（）} 
} 
 
 {
 package Array; ＃固定大小的数组。 
使用鲤鱼qw（croak）; 
 sub new {my（$ class，$ size）= @_; bless（[（undef）x $ size]，$ class）} 
子大小{my $ self = shift; 0 + @ $ self} 
 sub get {my（$ self，$ i）= @_;嘶哑的！如果$ i< 0 || $ i> = @ $ self; $ self-> [$ i]} 
子集{my（$ self，$ i，$ item）= @_;嘶哑的！如果$ i< 0 || $ i> = @ $ self; $ self-> [$ i] = $ item; } 
} 
 
 {
包裹清单； ＃可扩展数组。 
使用鲤鱼qw（croak）; 
 sub new {my $ class = shift; bless（[]，$ class）} 
 sub size {my $ self = shift; 0 + @ $ self} 
 sub get {my（$ self，$ i）= @_;嘶哑的！如果$ i <0; $ self-> [$ i]} 
子集{my（$ self，$ i，$ item）= @_;嘶哑的！如果$ i <0; $ self-> [$ i] = $ item; } 
 sub append {my（$ self，$ item）= @_;推送@ $ self，$ item; } 
} 
 
 {
 package字典； 
使用鲤鱼qw（croak）; 
 sub new {my $ class = shift; bless（{}，$ class）} 
 sub get {my（$ self，$ k）= @_;嘶哑的！如果！exists（$ self-> {$ k}）; $ self-> {$ k}} 
子集{my（$ self，$ k，$ item）= @_; $ self-> {$ k} = $ item; } 
 sub存在{my（$ self，$ k）= @_;存在（$ self-> {$ k}）} 
 sub delete {my（$ self，$ k）= @_;嘶哑的！如果！exists（$ self-> {$ k}）; delete（$ self-> {$ k}）} 
} 
 
 
 sub purge_queue {
 my（$ q）= @_; 
 
我的@vals； 
而（my（$ item）= $ q-> dequeue（））{
 push @vals，$ item; 
} 
 
 return @vals; 
} 
 
＃... 
 
 for我的$ 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 =队列-> new（）; 
 $ in_q->排队（$ _）表示‘a’..’j’； 
 
我的$ out_q = $ reverse_func->（$ in_q）; 
说sprintf％-26s％s， $ reverse_func_name：，加入’，purge_queue（$ out_q）; 
} 
  

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);
}

这篇关于我可以不使用堆栈而反转队列吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！