データ構造その5(Deque)

前回はBagとStackを見ました。

しかし、リリースがあったとは言え、週3回の授業の1回分に1ヵ月かかってるので、少しペースを上げたい…。

今回はDequeを見ていきます。

動的配列の復習

利点

• それぞれの要素へのアクセスが容易

• 必要に応じて拡張される

• ユーザー(プログラムを書く人)はメモリ管理を意識する必要がない

動的配列を使ったStackの復習

• 追加削除は一番上の要素に行う

• 時々容量が増加する

• 削除の処理はO(1)の計算量で行える

• 追加の処理もO(1)の計算量で行える

動的配列を使ったBagの復習

• 順番は重要ではなく、最後に追加される

• 追加はO(1)で時折容量が増加する

• 削除はO(n)かかる

動的配列の問題

• データが1つの大きなメモリのブロックに保持される

• 必要以上のメモリが使われることが多い

  • 特に追加より頻繁に削除が行われる場合

• 他のADTの実装に非効率的

データがいっぱいになって2倍の容量を確保した後に削除が行われると最初の容量Cが2Cに拡張されて、その後一気に削除されると拡張されたCの領域が丸々使われないことも起きます。広げることはあっても縮めることはないわけです。

Queue

• 要素は最後に追加され、先頭から削除される

• レジの行列の様なデータ構造

• 先入れ先出し(First In First Out = FIFO)

Queueのインターフェース

addBack(newElement) // 要素の追加
front()  // 最初の要素の取得
removeFront()  // 最初の要素の削除
isEmpty()  // キューが空かチェックする 

• どちら側の端(先頭/最後)に挿入するのが良いか

• どちらの端から削除するのが良いか

• 計算量はどうなるか

先頭を削除

• 削除の計算量はO(n)(前に詰める必要がある)

  • 効率的じゃない

• 最後に追加するのはO(1)

先頭に追加

• 追加の計算量はO(n)(後ろに並び替える必要がある) 

  • 効率的じゃない

• 最後を削除するのはO(1)

Deque

• 特徴

  • front/back両側から要素の挿入ができる

  • front/back両側から要素が削除できる

• StackやQueueはDequeの特殊なケース

• Dequeは2つの端の繋がったStack

Dequeのインターフェース

addFront(newElement)  // frontへの挿入
addBack(newElement)  // backへの挿入
front()  // front側の先頭の要素を返す
bacck()  // back側の先頭の要素を返す
removeFront()  // frontから要素を削除
removeBack()  // backから要素を削除
isEmpty()  // 空かチェックする

動的配列によるDeque

• キーアイデア

  • "front"のインデックスは0でなくてもよい

→"front"と"back"は配列内で浮動でよい

Dequeの実装例

この例ではstart indexはback indexより大きくなります。
back indexは次に使われるindexを指しています。と言っても左上の構造の通り、データ構造内には保持していません。この辺は実装で説明します。

Dequeの追加

ポイントは前述の通りsizeとstart indexだけでback indexを持たないところです。back indexはsizeから決まるのでadd backは値を入れてsizeを加算します。

Dequeの削除

同様にsizeもしくはindexをずらします。
この際要素はそのまま置かれても問題ないです。

要素のローテート

indexが前後にはみ出した場合、もしくはいっぱいになった場合は対応が必要です

• index < 0の場合

  • capacityと足す(埋まって拡張してると思われるので、ループして最後に)

• index > capacityの場合

  • capacityを引く

• size == capacityの場合

  • 新しいバッファ(メモリ割り当て)を用意する

実装

では実装を見ていきましょう。疑似コードなので悪しからず。

class Deque {
    DyArr<TYPE> data;
    int capacity;
    int size;
    int start;
}

サイズを持つか、最後の示すポインタを持つか

• 前述の通りback indexはstart indexとsizeから計算します

• 何故back indexを持たないでしょう？

• 持たなくても良いですが、sizeは頻繁に計算する必要があります

back indexはどう算出するか

modを使う

backIndex = (start + size) % capacity;

この例ではback index=1, (start + size) = 9でcapacityは7なのでback index=2となります。

class Deque {
...
    Deque(int initCapacity) {
       size = 0;
       start = 0;
       assert(capacity > 0);
       capacity = initCapacity;
       data = new DyArr<TYPE>(capacity);
    }
   
    void addBack(TYPE val) {
      if (size == capacity) {
        doubleCapacity();
      }
      int back_idx = (start + size) % capacity;
      data[back_idx] = val;
      ++size;
    }
    
    void addFront(TYPE val) {
      if (size == capacity) {
        doubleCapacity();
      }
      --start;
      if (start < 0) {
        start += capacity; // size == capacity後に入る
      }
      data[start] = val;
      ++size;
    }
 ...
}
        

課題

• addFront/addBackの計算量は？

• front()/back()/removeFront()/removeBack()の実装を考えてみましょう

• 純粋に前/後ろに入れる場合と前後から使う場合で何が嬉しいか自分の言葉で説明してみましょう

次回

次回は配列と並ぶ重要なデータ構造、連結リストのお話です。