お気楽 Lua プログラミング超入門

はじめに

今回は簡単な例題として、「スタック (stack)」と「キュー (queue)」という基本的なデータ構造を作ってみましょう。

●スタックとは？

まず最初に、スタックについて簡単に説明します。下図を見てください。

    |-----|     |[ A ]|     |[ B ]|     |[ A ]|     |-----|
    |  |  |     |-----|     |[ A ]|     |-----|     |  |  |
    |  |  |     |  |  |     |-----|     |  |  |     |  |  |
    |  |  |     |  |  |     |  |  |     |  |  |     |  |  |
    |  |  |     |  |  |     |  |  |     |  |  |     |  |  |
    +-----+     +-----+     +-----+     +-----+     +-----+
  1. 空の状態  2. PUSH A   3. PUSH B   4. POP B    5. POP A  

                   図 : スタックの動作例

上図はバネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもうひとつ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。ひとつ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。

この容器の動作がスタックの動作になります。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。

このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。

●スタックのプログラム

Lua の場合、スタックは配列を使って簡単に実装することができます。クラス名は Stack とし、上表に示すメソッドを定義します。s はスタックのオブジェクトを表します。プログラムは次のようになります。

リスト : スタック

Stack = {}

function Stack.new()
  local obj = { buff = {} }
  return setmetatable(obj, {__index = Stack})
end

function Stack:push(x)
  table.insert(self.buff, x)
end

function Stack:pop()
  return table.remove(self.buff)
end

function Stack:top()
  return self.buff[#self.buff]
end

function Stack:isEmpty()
  return #self.buff == 0
end

Stack.new でスタックを生成します。オブジェクト obj にはデータを格納する配列 buff をセットします。メソッド push はスタックにデータ x を追加します。これは buff の最後尾に x を追加すればいいので、関数 table.insert を呼び出すだけです。メソッド pop は buff の最後尾の要素を削除してそれを返せばよいので、関数 table.remove を呼び出すだけです。メソッド top は最後尾のデータを削除せずに返し、メソッド isEmpty はスタックが空であれば true を返します。

なお、スタックにデータがない場合、pop と top は nil を返すことになります。nil を返さずに関数 error を使ってエラーを送出することもできます。興味のある方は試してみてください。

●スタックの実行例

それでは実行してみましょう。

> a = Stack.new()
> for i = 1, 8 do a:push(i) end
> while not a:isEmpty() do print(a:pop()) end
8
7
6
5
4
3
2
1

スタックに 1 から 8 までを push で格納し pop でデータを取り出すと 8, 7, 6, 5, 4, 3, 2, 1 になります。このように、スタックは後から入れたデータが先に取り出されます。

●キューとは？

 out                            in
    ──────────────
<=  A  B  C  D  E  .  .  .  Z    <=
    ──────────────

       図 : キューの動作

次は「キュー (queue)」について簡単に説明します。たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。

これを表したのが上図です。このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in, first-out)」と呼ばれます。

●キューのプログラム

Lua の場合、table.insert と table.remove を使うとキューを簡単に実装することができます。クラス名は Queue とし、下表に示すメソッドを定義します。

q はキューのオブジェクトを表します。プログラムは次のようになります。

リスト : キュー

Queue = {}

function Queue.new()
  local obj = { buff = {} }
  return setmetatable(obj, {__index = Queue})
end

function Queue:enqueue(x)
  table.insert(self.buff, x)
end

function Queue:dequeue()
  return table.remove(self.buff, 1)
end

function Queue:top()
  if #self.buff > 0 then
    return self.buff[1]
  end
end

function Queue:isEmpty()
  return #self.buff == 0
end

Queue.new でキューを生成します。オブジェクト obj にはデータを格納する配列 buff をセットします。enqueue はキューにデータ x を追加します。これは buff の最後尾に x を追加すればいいので、関数 table.insert を呼び出すだけです。dequeue は buff の先頭要素を削除してそれを返せばよいので、関数 table.remove の引数に 1 を指定して呼び出します。top は先頭要素を削除せずに返し、isEmpty はキューが空であれば true を返します。

●キューの実行例

簡単な実行例を示します。

> b = Queue.new()
> for i = 1, 8 do b:enqueue(i) end
> while not b:isEmpty() do print(b:dequeue()) end
1
2
3
4
5
6
7
8

キューに 1 から 8 までを enqueue で格納して、dequeue でデータを取り出すと 1, 2, 3, 4, 5, 6, 7, 8 になります。スタックとは逆に、キューはデータを入れた順番にデータが取り出されます。

●リングバッファよるキューの実装

ところで、table.remove で先頭要素を削除するとき、後ろの要素を前へ移動する処理が行われますが、データの移動を行わないでキューを実装する方法もあります。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

           0  1  2  3  4  5  6  7  8  9
rear = 0  ↓
QUEUE    [                              ]  : QUEUE は空
front= 0  ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : データの追加
front= 0  ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : 10を取り出す
front= 1     ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : 20,30を取り出す
front= 3           ↑

                図 : キューの動作

まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値を +1 します。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。

次に、データを取り出す場合、front の示すデータを取り出しから front の値を +1 します。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。

rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら先頭に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実装する場合は、リングバッファとするのがふつうです。

●キューのプログラム (2)

それでは、プログラムを作りましょう。クラス名は SizedQueue とし、上表に示すメソッドを定義します。q は SizedQueue のオブジェクトです。今回はリングバッファの大きさを固定するので、キューが満杯になる場合があります。そこで、メソッド isFull を用意して、キューが満杯の場合は true を返すことにします。

次はクラスを定義します。

リスト : リングバッファによるキューの実装

SizedQueue = {}

function SizedQueue.new(size)
  local obj = {
    front = 1,
    rear  = 1,
    count = 0,
    size  = size,
    buff  = {}
  }
  return setmetatable(obj, {__index = SizedQueue})
end

SizedQueue.new でキューを生成します。引数の size はキューの大きさです。インスタンス変数 size はキューの大きさ、buff には配列をセットします。インスタンス変数 count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューが空なのか満杯なのか簡単にチェックすることができます。

次はデータを追加するメソッド enqueue を作ります。

リスト : データの追加

function SizedQueue:enqueue(x)
  if self.count < self.size then
    self.buff[self.rear] = x
    self.rear = self.rear + 1
    self.count = self.count + 1
    if self.rear > self.size then
      self.rear = 1
    end
    return x
  end
end

まず、count と size を比較して、キューにデータを格納できるかチェックします。満杯の場合は nil を返します。データは rear の位置に格納し、count と rear の値を更新します。そして、rear の値が配列の範囲を超えたならば 1 に戻します。最後に return で x を返します。

次は、キューからデータを取り出すメソッド dequeue を作ります。

リスト : データを取り出す

function SizedQueue:dequeue()
  if self.count > 0 then
    local val = self.buff[self.front]
    self.front = self.front + 1
    self.count = self.count - 1
    if self.front > self.size then
      self.front = 1
    end
    return val
  end
end

まず、キューにデータがあるかチェックします。キューが空の場合は nil を返します。データがある場合は front の位置にある buff の要素を取り出して val にセットします。次に count と front の値を更新し、front の値が配列の範囲を超えたら 1 に戻します。最後に return で val を返します。

あとのメソッドは簡単です。次のリストを見てください。

リスト : その他のメソッド

function SizedQueue:top()
  if self.count > 0 then
    return self.buff[self.front]
  end
end

function SizedQueue:isFull()
  return self.count == self.size
end

function SizedQueue:isEmpty()
  return self.count == 0
end

top は front の位置にある要素を返します。キューが空の場合は nil を返します。isFull は count と size が等しいときに true を返します。isEmpty は count が 0 のときに true を返します。

●キューの実行例 (2)

それでは実際に実行してみましょう。

> c = SizedQueue.new(5)
> for i = 1, 5 do c:enqueue(i) end
> c:isFull()
true
> while not c:isEmpty() do print(c:dequeue()) end
1
2
3
4
5
> c:isEmpty()
true
> for i = 1, 3 do c:enqueue(i) end
> c:isFull()
false
> while not c:isEmpty() do print(c:dequeue()) end
1
2
3
> c:isEmpty()
true

正常に動作していますね。

なお、スタックとキューは「連結リスト」を使って実装することもできます。興味のある方はプログラムを作ってみてください。

●プログラムリスト

--
-- stackqueue.lua : スタックとキュー
--
--                  Copyright (C) 2011 Makoto Hiroi
--

-- スタック
Stack = {}

function Stack.new()
  local obj = { buff = {} }
  return setmetatable(obj, {__index = Stack})
end

function Stack:push(x)
  table.insert(self.buff, x)
end

function Stack:pop()
  return table.remove(self.buff)
end

function Stack:top()
  return self.buff[#self.buff]
end

function Stack:isEmpty()
  return #self.buff == 0
end

-- キュー
Queue = {}

function Queue.new()
  local obj = { buff = {} }
  return setmetatable(obj, {__index = Queue})
end

function Queue:enqueue(x)
  table.insert(self.buff, x)
end

function Queue:dequeue()
  return table.remove(self.buff, 1)
end

function Queue:top()
  if #self.buff > 0 then
    return self.buff[1]
  end
end

function Queue:isEmpty()
  return #self.buff == 0
end

-- リングバッファ
SizedQueue = {}

function SizedQueue.new(size)
  local obj = {
    front = 1,
    rear  = 1,
    count = 0,
    size  = size,
    buff  = {}
  }
  return setmetatable(obj, {__index = SizedQueue})
end

-- メソッド
function SizedQueue:enqueue(x)
  if self.count < self.size then
    self.buff[self.rear] = x
    self.rear = self.rear + 1
    self.count = self.count + 1
    if self.rear > self.size then
      self.rear = 1
    end
    return x
  end
end

function SizedQueue:dequeue()
  if self.count > 0 then
    local val = self.buff[self.front]
    self.front = self.front + 1
    self.count = self.count - 1
    if self.front > self.size then
      self.front = 1
    end
    return val
  end
end

function SizedQueue:top()
  if self.count > 0 then
    return self.buff[self.front]
  end
end

function SizedQueue:isFull()
  return self.count == self.size
end

function SizedQueue:isEmpty()
  return self.count == 0
end