data-structures - 2 つのスタックを使用してデキューを実装する方法

Question

デキュー - 両端キュー: 両端からのエンキューとデキューが可能です。

2 つのスタックを使用してデキューの ADT 操作を定義する方法。

実装では、パフォーマンスも考慮する必要があります。

Answer 1

最も簡単な解決策は、1 つのスタックをキューの先頭として使用し、もう 1 つを末尾として使用することです。エンキュー操作はそれぞれのスタックへのプッシュであり、デキュー操作はそれぞれのスタックでのポップです。

ただし、デキュー元のスタックが空の場合は、他のスタックから各要素をポップし、デキュー元のスタックにプッシュしてから、最後の要素をデキューする必要があります。これはあまり良いパフォーマンスではないため、この実装の全体的なパフォーマンスはワークロードに大きく依存します。ワークロードがフロント/バック エンキューおよびデキュー操作のバランスの取れた数である場合、これは非常に高速になります。しかし、ワークロードが多数の交互のヘッド デキューとテール デキューで構成され、キューが大きい場合、これは明らかに悪いアプローチです。

お役に立てれば

Answer 2

これを行う興味深い方法は次のとおりです

enqueue(q,  x)
  1) Push element x to stack1. This very simple, the problem is dequeue

dequeue(q)
  1) If stacks1 and stack2 are empty then error  "UNDERFLOW"
  2) If stack2 is empty, then 
       while (stack1 is not empty) do
           push all element from satck1 to stack2.
        end while;
  3) Pop the element from stack2 and return it.