0

以下は、双方向リンク リストを使用したキューの実装です。

QUEUE-EMPTY
if L.head == NIL
    return True
else return False

QUEUE(x):
if L.head == NIL:
    x.prev = NIL
    L.head = x
else
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x
    x.prev = cur
    x.next = NIL

DEQUEUE():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

改善方法 ？あれは正しいですか ？

QUEUE O(1) を作成する手段はありますか?

ありがとう ！！

4

2 に答える 2

1

以下の変更とコメントを参照してください。

QUEUE(x):
if L.head == NIL:
    x.prev = x.next = NIL // otherwise you never set up next
    L.head = x
else
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x
    x.prev = cur
    x.next = NIL

DEQUEUE():
// handle empty queue
if L.head == NIL:
    ERROR! // or something
else
    x = L.head
    L.head = x.next
    if x.next != NIL: // handle empty queue
        x.next.prev = L.head NIL // otherwise it points to itself
    return x

O(1)を作成するQUEUE(x)には、末尾へのポインタを保持する必要があります。

QUEUE(x):
if L.head == NIL:
    x.prev = NIL
    L.head = L.tail = x
else
    cur = L.tail
    cur.next = L.tail = x
    x.prev = cur
    x.next = NIL

DEQUEUE():
if L.head == NIL:
    ERROR! // or something
else
    x = L.head
    L.head = x.next
    if x.next != NIL:
        x.next.prev = NIL
    else
        L.tail = NIL
    return x

また、二重リンクリストは実際には必要ありません。単一リンクのリストは問題なく動作するはずです (他の操作もサポートしたい場合を除きます)。

于 2013-03-28T12:33:01.970 に答える
0

キューには 2 つの標準的な実装があります。

リング バッファーは、先頭と末尾へのポインターと共に配列に格納できます。すべての演算は、配列の長さを法として行われます。テールがヘッドに追いついた場合、キューがオーバーフローして使用できなくなります。

別の実装では、2 つの連結リストを使用します。最初のリストは順番にキューの先頭です。2 番目のリストは、逆順のキューの最後です。アイテムは 2 番目のリストに追加され、最初のリストから取得されます。最初のリストが空でアイテムがフェッチされるときはいつでも、2 番目のリストが反転されて最初のリストになり、新しい (空の) 2 番目のリストが作成されます。

どちらの実装も、挿入とフェッチ/削除の時間の複雑さは O(1) です。リング バッファーの実装には、絶対時間の複雑度 O(1) がありますが、キューの最大サイズが事前に定義されています。リンクされたリストの実装では、十分なメモリが利用可能であると仮定すると、時間の複雑さ O(1) が償却されますが、キューの最大サイズに制限はありません。

于 2013-03-28T15:47:11.683 に答える