データ構造その4(Stack＆Bag)

さて、前回からデータ構造そのものに入りましたが、楽しんで頂けているでしょうか？

前回は動的配列を扱いました。可変長配列と言われたりもします。英語ではDynamic Arrayですね。

今回はStackとBagのインターフェースと動的配列を使った実装を見ていきます。

StackのADT

定義

後入れ先出しでデータ要素を扱うコレクション。
積み上げた皿のように後に置いたものを先に取る構造です。

操作

• Stackへの要素追加

• Stackから要素の削除

• Stackのtopの要素の読み込み

• Stackに要素が含まれるかのチェック

Stackのインターフェース

インターフェースで操作のための関数の定義が共通化されることにより実装を効果的に隠します。基本的に似たような名前の関数が各言語で提供されます。

void init();
void push();
TYPE top();
void pop();
bool isEmpty();

Cで書くとわかりにくいと思うのでpython風に書きます

class DyArr:
    _data = None
    _size = 0
    _cap = 0
  
    def __init__(self, cap: int): ...
    # def free(self): ...
    def add(self, val: Any): ...
    def get(self, idx: int) -> Any: ...
    def put(self, idx: int, val: Any) -> Any: ...
    def size(self) -> int: ...
    def __double_capacity(self): ...

class Stack:
    def __init__(self, cap: int):
        self._dy_arr = DyArr(cap)

    # def free(self):
    #    self.dy_arr.free()

    def push(self, val: Any):
        self._dy_arr.add(val)

    def top() -> Any:
        assert self._dy_arr.size() > 0
        return self._dy_arr.get(self._dy_arr.size() - 1)

    def pop():
        assert self._dy_arr.size() > 0
        self._dy_arr._size -= 1

    is_empty() -> bool:
        return self._dy_arr.size() == 0

伝わったでしょうか？

return self._dy_arr.get(self._dy_arr.size() - 1)

この辺の-1するのとかは初学者は理解しましょう。

Bagのインターフェース

void init();
void free();
void add(TYPE);
bool contains(TYPE);
void remove(TYPE);
int size();

initでDyArrを内部にinitして保持して、(free/)add/size は動的配列の関数をそのまま呼ぶだけです。

重要なのはcontains/removeです。

Bag.remove()

これに関してはDyArrを拡張した方がよいでしょう。

Pythonだとわかりにくい(厳密には配列でなくリストなので)ので疑似コードで書きます。

class DyArr {
  _data = []
  _cap = 0
  _size = 0
...
  void remove_at(idx) { ... }
  void remove(val) {
    i = 0
    while i < this._size {
      if (val == this._data[i]) {
        this.remove_at(i)
        return
      }
      ++i
    }
  }
}

  では、全ての要素を一致する要素を削除する関数を書くとどうなるでしょう？

class DyArr {
  _data = []
  _cap = 0
  _size = 0
...
  void remove(val) {
    i = 0
    while i < this._size {
      if (val == this._data[i]) {
        this._data.remove_at(i)
        --i  # or continue
      }
      ++i
    }
  }
}

これはなぜデクリメント(--i)するのでしょう？

答えは一致した部分が抜けて詰められるからです。
□□■□□が□□□□になると削除後にインクリメントしてしまうと元々4個目にあった要素が一致するかチェックされないからです。

ではremove_atを見ましょう

  void remove_at(idx) {
    assert(this._size > idx) && (idx >= 0)
  
    for (i = idx; i <= this._size -2; ++i) {
      this._data[i] = this._data[i + 1]
    }

    this._size -= 1
  }

 これの計算量はなんでしょう？
また、それを改善する方法は？少し考えてから進んでください。

順番を保持しなくてよい場合、下記実装で済みます。

void remove_at(idx) {
    assert(this._size > idx) && (idx >= 0)
  
    this._data[idx] = this._data[this._size - 1]

    this._size -= 1
}

何をしたかわかるでしょうか？
順不同で良いなら、最後の要素を削除する要素と入れ替えてサイズを減らします。次に要素を追加すると削除予定だった値が上書きされる感じです。

この場合、計算量はどう改善されたでしょう？

課題

containsも含めてお好きな言語で実装してBagを完成させましょう。

次回

次回はDequeになります。
Dequeまでは単純な構造でその次のLinkedList辺りから少し複雑になっていきます。