2

私はこのアルゴリズムに従うJavaで2つのスタックを使用してキューを実装しました：

enQueue（x）
xをstack1にプッシュします

deQueue（）
1）両方のスタックが空の場合、エラーが発生します。
2）stack1が空でないときにstack2が空の場合は、stack1からstack2にすべてをプッシュします。
3）stack2から要素をポップして返します。

ここでの問題は、最初のdeQueue()操作が非常に遅いことです（すべてをに転送するためstack2）。アルゴリズムをなんとかして変更して、deQueue常にO（1）になるようにすることはできますか？他に選択肢はありますか？

4

3 に答える 3

0

2つのスタックを交換できます。

deQueue（）

  1. 両方のスタックが空の場合、エラーが発生します。
  2. stack2が空で、stack1が空でない場合は、2つのスタックを交換します。
  3. stack2から要素をポップして返します。

スワップを使用すると、操作は常にO（1）になります。

FIFOキューが必要な場合は、2つのキューを使用してください。LIFOの動作が必要な場合にのみ、スタックを使用してください。

この場合、1つのキューを使用するか2つのキューを使用するかに違いはないため、1つのキューだけを使用することもできます。スレッドを使用している場合は、キューとスレッドプールをラップするExecutorServiceを使用します。

于 2012-08-21T18:38:28.523 に答える
0

私は噛みます：二重にリンクされたリストを使用してみませんか？これは、O（1）プッシュとO（1）ポップである必要があります。

于 2012-08-21T18:41:23.917 に答える
0

私たちが言うときfirst deQueue() operation is very slow (since it transfers everything to stack2).

私たちはこれについて話していると思います

2）stack1が空でないときにstack2が空の場合は、stack1からstack2にすべてをプッシュします。

stack1にあるすべてのものを同じ順序でstack2に転送するだけですか。これは単純な割り当て（stack2=stack1;）であり、したがってO（1）になります。

または、stack1からすべてを1つずつポップして、stack2に追加する必要があると言っている場合。基本的に、リスト（stack1）を逆にして、stack2に割り当てることについて話します（割り当てはO（1）です。リストを逆にするためのさまざまな優れたアルゴリズムがありますhttp://www.codeproject.com/Articles/27742/How-To-Reverse-a-Linked-List-3-Different-Ways。

Javaを使用している場合（タグに従って）、Collections.reverse(arrayList);リストを逆にするために簡単に使用できます。

于 2012-08-21T19:04:58.600 に答える