Linux Programming

キュー

今回は簡単な例題として「キュー (queue)」という基本的なデータ構造を作ってみましょう。なお、標準ライブラリ (Standard Template Library) には <queue> というコンテナアダプタ ^[*1] が用意されています。私たちがキューを作る必要はありませんが、Ｃ++とデータ構造のお勉強ということで、あえてプログラムを作ってみましょう。

●キューとは？

私たちがチケットを買うとき、カウンタの前に並んで順番を待たなくてはいけませんね。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを表したのが下図です。

         図 : キューの動作

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

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

キューは配列や連結リスト ^[*2] を使って簡単に実装することができます。配列でキューを実装する場合、先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

                  図 : キューの動作

まずキューは空の状態で、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 が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実装する場合は、リングバッファとするのが普通です。

●クラス Queue の定義

それでは実際にプログラムを作ってみましょう。クラス名は Queue とします。今回はプログラムを簡単にするため、キューに格納するデータは整数 (int) に限定します。最初に、基本的なメンバ関数を下表に示します。

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

リスト : Queue の定義

class Queue {
  int front, rear, count, limit;
  int *buff;
  // コンストラクタと代入演算子は無効化
  Queue(const Queue&);
  Queue& operator=(const Queue&);
public:
  explicit Queue(int n) :
    front(0), rear(0), count(0), limit(n), buff(new int [n]) {}
  ~Queue() { delete[] buff; }
  void enqueue(int);
  int dequeue();
  int peek_front() const;
  void clear();
  int size() const { return count; }
  bool empty() const { return !count; }
  bool full() const { return count == limit; }
};

メンバ変数 count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。buff がキューの本体 (配列) です。メモリの取得はコンストラクタで行います。大きさはメンバ変数 limit に格納します。今回は簡単な例題なので、コピーコンストラクタと代入演算子の処理は無効化しておきます。

●データの挿入

次はデータを追加するメンバ関数 enqueue を作ります。

リスト : キューにデータを追加する

void Queue::enqueue(int x)
{
  if (full()) throw runtime_error("Queue::enqueue overflow");
  buff[rear++] = x;
  count++;
  if (rear == limit) rear = 0;
}

最初にメンバ関数 full を呼び出してキューが満杯かチェックします。full は count と limit が等しいかチェックするだけです。キューが満杯であれば、enqueue は例外を送出します。データは rear の位置に格納し、count と rear の値を更新します。rear の値が buff の範囲を超えたならば 0 に戻します。

●データの取り出し

次は、キューからデータを取り出す関数 dequeue を作ります。

リスト : キューからデータを取り出す

int Queue::dequeue()
{
  if (empty()) throw runtime_error("Queue::dequeue underflow");
  int x = buff[front++];
  count--;
  if (front == limit) front = 0;
  return x;
}

まず、メンバ関数 empty を呼び出してキューにデータがあるかチェックします。empty は count が 0 かチェックするだけです。キューが空の場合、dequeue は例外を送出します。データがある場合は buff[front] の位置にあるデータを取り出して返します。あとは、front と count の値を更新し、front の値が buff の範囲を超えたら 0 に戻します。

あとの操作関数は簡単なので説明は割愛します。詳細は プログラムリスト1 をお読みくださいませ。

●実行例

これでプログラムは完成です。それでは、簡単な実行例を示しましょう。

リスト : 簡単なテスト

int main()
{
  Queue q(10);
  for (int i = 0; i < 5; i++) q.enqueue(i);
  cout << q.empty() << endl;
  cout << q.full() << endl;
  cout << q.size() << endl;
  while (!q.empty()) cout << q.dequeue() << " ";
  cout << endl;
  int j = 10;
  while (!q.full()) q.enqueue(j++);
  while (!q.empty()) cout << q.dequeue() << " ";
  cout << endl;
}  

$ clang++ queue.cpp
$ ./a.out
0
0
5
0 1 2 3 4
10 11 12 13 14 15 16 17 18 19

コンストラクタでキューを作成して変数 q にセットします。for ループでキューにデータを 5 個セットします。size の返り値は 5 で、empty と full の返り値はどちらも 0 (false) です。次に、while ループでキューにデータがある間、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかります。

最後にデータを 10 個追加します。これでキューは満杯になるので、これ以上データを追加することはできません。full の返り値は 1 (true) になります。次に、dequeue でデータを取り出します。これでキューは空の状態になります。

●ディーキュー (deque)

もうひとつ簡単な例題として「deque (double ended queue)」というデータ構造を作ってみましょう。deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれています。キューの場合、データの追加は末尾に、データの取り出しは先頭に対してのみ行えます。これに対しディーキューは、先頭および末尾のどちらでもデータの追加と取り出しが行えるデータ構造です。

ディーキューは双方向リストやリングバッファを使って簡単に実装することができます。今回はリングバッファを使ってプログラムを作ってみましょう。なお、Ｃ++の STL には <deque> という vector に両端キューの機能を追加したコンテナクラスが用意されています。私たちがディーキューを作る必要はありませんが、Ｃ++とデータ構造のお勉強ということで、あえてプログラムを作ってみましょう。

●ディーキューの定義

クラス名は Deque とします。今回はプログラムを簡単にするため、ディーキューに格納するデータは整数 (int) に限定します。最初に、基本的なメンバ関数を下表に示します。

先頭にデータを追加する push_front, 末尾からデータを取り出す pop_back, 末尾要素を参照する peek_back を追加します。それから、STL (deque) のまねをして、添字演算子 [] で要素にアクセスできるようにしてみましょう。

クラス Deque の定義は次のようになります。

リスト : クラス Deque の定義

class Deque {
  int front, rear, count, limit;
  int *buff;
  // コンストラクタと代入演算子は無効化
  Deque(const Deque&);
  Deque& operator=(const Deque&);
public:
  explicit Deque(int n) :
    front(0), rear(0), count(0), limit(n), buff(new int [n]) {}
  ~Deque() { delete[] buff; }
  void push_front(int);
  void pop_front();
  void push_back(int);
  void pop_back();
  int peek_front() const;
  int peek_back() const;
  void clear();
  int size() const { return count; }
  bool empty() const { return !count; }
  bool full() const { return count == limit; }
  int& operator[](int);
};

●データの挿入

次はデータを挿入する push_front と push_back を作ります。

リスト : データの挿入

void Deque::push_front(int x)
{
  if (full()) throw runtime_error("Deque::push_front overflow");
  if (front == 0) front = limit;
  buff[--front] = x;
  count++;
}

void Deque::push_back(int x)
{
  if (full()) throw runtime_error("Deque::push_back overflow");
  buff[rear++] = x;
  count++;
  if (rear == limit) rear = 0;
}

push_front の場合、先頭データの位置は front なので、front - 1 の位置にデータを書き込みます。最初に front が 0 ならば limit に更新しておいて、buff[--front] に引数 x をセットします。そして、count を + 1 します。push_back は Queue のメンバ関数 enqueue と同じです。

●データの削除

次はディーキューからデータを削除するメンバ関数 pop_front と pop_back を作ります。

リスト : データの削除

void Deque::pop_front()
{
  if (empty()) throw runtime_error("Deque::pop_front underflow");
  front++;
  count--;
  if (front == limit) front = 0;
}

void Deque::pop_back()
{
  if (empty()) throw runtime_error("Deque::pop_back underflow");
  rear--;
  count--;
  if (rear < 0) rear = limit - 1;
}

pop_front は Queue のメンバ関数 dequeue とほぼ同じです。pop_back は末尾データを取り除きます。末尾データは rear - 1 の位置にあるので、rear と count を -1 するだけです。rear が 0 よりも小さくなったら、buff の末尾の位置 (limit - 1) に書き換えます。

●データの参照

次は先頭データと末尾データを返すメンバ関数 peek_front と peek_back を作ります。

リスト : データの参照

int Deque::peek_front() const
{
  if (empty()) throw runtime_error("Deque::peek_front underflow");
  return buff[front];
}

int Deque::peek_back() const
{
  if (empty()) throw runtime_error("Deque::peek_back underflow");
  if (rear == 0) return buff[limit - 1];
  return buff[rear - 1];
}

peek_front は Queue のメンバ関数と同じです。peek_back は rear - 1 の位置にある要素を返します。ただし、rear が 0 の場合は buff の末尾にある要素 (buff[limit - 1]) を返します。

●添字演算子の多重定義

最後に、添字演算子を多重定義します。

リスト : 添字演算子

int& Deque::operator[](int n)
{
  if (n < 0 || n >= count) throw runtime_error("Deque out of range");
  return buff[(front + n) % limit];
}

引数 n が 0 未満または count 以上の場合、要素は存在しないので例外を送出します。そうでなければ、先頭から n 番目の要素を返します。先頭要素は front の位置にあるので、要素の位置は (front + n) % limit で求めることができます。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト２ をお読みください。

●簡単なテスト

これでプログラムは完成です。それでは実際に試してみましょう。

リスト : 簡単なテスト

int main()
{
  Deque q(10);
  for (int i = 0; i < 5; i++) q.push_back(i);
  cout << q.empty() << endl;
  cout << q.full() << endl;
  cout << q.size() << endl;
  while (!q.empty()) {
    cout << q.peek_front() << " ";
    q.pop_front();
  }
  cout << endl;
  int j = 10;
  while (!q.full()) q.push_front(j++);
  for (int i = 0; i < 10; i++)
    cout << q[i] << " ";
  cout << endl;
  while (!q.empty()) {
    cout << q.peek_back() << " ";
    q.pop_back();
  }
  cout << endl;
}

$ clang++ deque.cpp
$ ./a.out
0
0
5
0 1 2 3 4
19 18 17 16 15 14 13 12 11 10
10 11 12 13 14 15 16 17 18 19

コンストラクタでディーキューを作成して変数 q にセットします。for ループでディーキューにデータを 5 個 push_back で追加します。size の返り値は 5 で、empty と full の返り値はどちらも 0 (false) です。

次に、while ループでディーキューにデータがある間、push_front でデータを取り出します。この場合、キューと同じ動作になり、先に入れたデータから順番に取り出されていることがわかります。最後にデータを 10 個 push_front で追加します。これでディーキューは満杯になるので、これ以上データを追加することはできません。

その次の for ループで、0 番目から 9 番目の要素を表示します。すると、データを追加した順番とは逆に表示されます。先頭にデータを追加しているので、スタックと同じ動作になるわけです。最後に、while ループでディーキューが空になるまで、データを取り出して表示します。pop_back で末尾からデータを取り出すと、キューと同じ動作になります。

●コンテナ deque の使い方

ご参考までに、STL に用意されている deque の使い方を簡単に説明します。deque は vector にメンバ関数 push_front, pop_front, front を追加したコンテナクラスと考えてください。これらの操作は定数時間 (O(1)) で行うことができます。それ以外は vector とほとんど同じです。ただし、vector と違って配列本体のメモリ領域は連続して確保されているとは限りません。要素へのポインタや参照を使う場合は注意が必要です。

簡単な使用例を示しましょう。

リスト : deque の使用例 (sample2001.cpp)

#include <iostream>
#include <deque>
using namespace std;

int main()
{
  deque<int> a;
  for (int i = 0; i < 10; i++) a.push_front(i);
  for (auto iter = a.begin(); iter != a.end(); ++iter)
    cout << *iter << " ";
  cout << endl;
  for (int i = 0; i < 10; i++) {
    cout << a.front() << " ";
    a.pop_front();
  }
  cout << endl;
  for (int i = 0; i < 10; i++) a.push_back(i);
  for (int i = 0; i < 10; i++) {
    cout << a.front() << " ";
    a.pop_front();
  }
  cout << endl;
}

$ clang++ sample2001.cpp
$ ./a.out
9 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

push_front と pop_front を使えばスタックと同じ動作になり、push_back と pop_front を使えばキューと同じ動作になります。

●アダプタ queue の使い方

最後に、STL のコンテナアダプタ queue の使い方を簡単に説明します。queue はデフォルトでコンテナクラスに deque を使います。主なメンバ関数を下表に示します。

size_type は STL の中で定義されているデータ型で配列の要素数を表すための値 (無符号整数) です。メンバ関数の使い方は、今まで説明したキューやディーキューとほとんど同じです。

簡単な使用例を示しましょう。

リスト : queue の簡単な使用例 (sample2002.cpp)

#include <iostream>
#include <queue>
using namespace std;

int main()
{
  queue<int> q0;
  for (int i = 0; i < 10; i++) q0.push(i);
  while (!q0.empty()) {
    cout << q0.front() << " ";
    q0.pop();
  }
  cout << endl;
  queue<double> q1;
  for (int i = 0; i < 10; i++) q1.push(i + 0.12345);
  while (!q1.empty()) {
    cout << q1.front() << " ";
    q1.pop();
  }
  cout << endl;
}

$ clang++ sample2002.cpp
$ ./a.out
0 1 2 3 4 5 6 7 8 9
0.12345 1.12345 2.12345 3.12345 4.12345 5.12345 6.12345 7.12345 8.12345 9.12345

今回はここまでです。次回は C++11 で導入された「右辺値参照 (rvalue reference)」と unique_ptr というスマートポインタについて説明します。

●プログラムリスト１

//
// queue.cpp : キュー
//
//             Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <stdexcept>
using namespace std;

class Queue {
  int front, rear, count, limit;
  int *buff;
  // コンストラクタと代入演算子は無効化
  Queue(const Queue&);
  Queue& operator=(const Queue&);
public:
  explicit Queue(int n) :
    front(0), rear(0), count(0), limit(n), buff(new int [n]) {}
  ~Queue() { delete[] buff; }
  void enqueue(int);
  int dequeue();
  int peek_front() const;
  void clear();
  int size() const { return count; }
  bool empty() const { return !count; }
  bool full() const { return count == limit; }
};

// データの挿入
void Queue::enqueue(int x)
{
  if (full()) throw runtime_error("Queue::enqueue overflow");
  buff[rear++] = x;
  count++;
  if (rear == limit) rear = 0;
}

// データの取り出し
int Queue::dequeue()
{
  if (empty()) throw runtime_error("Queue::dequeue underflow");
  int x = buff[front++];
  count--;
  if (front == limit) front = 0;
  return x;
}

int Queue::peek_front() const
{
  if (empty()) throw runtime_error("Queue::peek_front underflow");
  return buff[front];
}

// クリア
void Queue::clear()
{
  front = rear = count = 0;
}

int main()
{
  Queue q(10);
  for (int i = 0; i < 5; i++) q.enqueue(i);
  cout << q.empty() << endl;
  cout << q.full() << endl;
  cout << q.size() << endl;
  while (!q.empty()) cout << q.dequeue() << " ";
  cout << endl;
  int j = 10;
  while (!q.full()) q.enqueue(j++);
  while (!q.empty()) cout << q.dequeue() << " ";
  cout << endl;
}  

●プログラムリスト２

//
// deque.cpp : ディーキュー
//
//             Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <stdexcept>
using namespace std;

class Deque {
  int front, rear, count, limit;
  int *buff;
  // コンストラクタと代入演算子は無効化
  Deque(const Deque&);
  Deque& operator=(const Deque&);
public:
  explicit Deque(int n) :
    front(0), rear(0), count(0), limit(n), buff(new int [n]) {}
  ~Deque() { delete[] buff; }
  void push_front(int);
  void pop_front();
  void push_back(int);
  void pop_back();
  int peek_front() const;
  int peek_back() const;
  void clear();
  int size() const { return count; }
  bool empty() const { return !count; }
  bool full() const { return count == limit; }
  int& operator[](int);
};

// データの挿入
void Deque::push_front(int x)
{
  if (full()) throw runtime_error("Deque::push_front overflow");
  if (front == 0) front = limit;
  buff[--front] = x;
  count++;
}

void Deque::push_back(int x)
{
  if (full()) throw runtime_error("Deque::push_back overflow");
  buff[rear++] = x;
  count++;
  if (rear == limit) rear = 0;
}

// データの取り出し
void Deque::pop_front()
{
  if (empty()) throw runtime_error("Deque::pop_front underflow");
  front++;
  count--;
  if (front == limit) front = 0;
}

void Deque::pop_back()
{
  if (empty()) throw runtime_error("Deque::pop_back underflow");
  rear--;
  count--;
  if (rear < 0) rear = limit - 1;
}

int Deque::peek_front() const
{
  if (empty()) throw runtime_error("Deque::peek_front underflow");
  return buff[front];
}

int Deque::peek_back() const
{
  if (empty()) throw runtime_error("Deque::peek_back underflow");
  if (rear == 0) return buff[limit - 1];
  return buff[rear - 1];
}

// クリア
void Deque::clear()
{
  front = rear = count = 0;
}

int& Deque::operator[](int n)
{
  if (n < 0 || n >= count) throw runtime_error("Deque out of range");
  return buff[(front + n) % limit];
}

int main()
{
  Deque q(10);
  for (int i = 0; i < 5; i++) q.push_back(i);
  cout << q.empty() << endl;
  cout << q.full() << endl;
  cout << q.size() << endl;
  while (!q.empty()) {
    cout << q.peek_front() << " ";
    q.pop_front();
  }
  cout << endl;
  int j = 10;
  while (!q.full()) q.push_front(j++);
  for (int i = 0; i < 10; i++)
    cout << q[i] << " ";
  cout << endl;
  while (!q.empty()) {
    cout << q.peek_back() << " ";
    q.pop_back();
  }
  cout << endl;
}