C++でキューを1から実装する

C++でデータ構造を実装してみるシリーズ。今回はキューを勉強しました。
標準ライブラリにありますが、勉強のために自分で実装します。

目標

キューを自分の手で実装してみる。

キュー

キューは先入れ先出し（FIFO: First In First Out）を特徴とするデータ構造。両端が空いた箱の中にデータを入れて、先頭に入れたやつが押し出されてくるイメージ。

標準ライブラリでは次のようなメソッドが定義されている。

size()	要素数を返す。
front()	先頭の要素を返す。
pop()	先頭の要素を削除する。
push(x)	末尾に要素xを追加する。
empty()	キューが空であればtrue、空でなければfalseを返す

実装してみた

先頭の要素を削除するたびに全ての要素を前に移動しているのは非効率なので、リングバッファを用いて実装します。インデックスが配列の範囲を超えてしまった場合にインデックスを0にリセットします。１次元配列の先頭と末尾をくっつけて、要素が溢れないようにぐるぐる循環しているイメージです。

メンバ変数m_headとm_tailはそれぞれ、先頭の要素のインデックス、末尾の要素のインデックス+1を指すことに注意。
なお、空の状態と満杯の状態を区別するために、m_tailからm_headまでは少なくとも１つ開けています。

queue.h

#ifndef _MY_QUEUE_H_
#define _MY_QUEUE_H_

class MyQueue {
 private:
  int m_head;
  int m_tail;
  int MAX;
  int m_q[100000];

 public:
  MyQueue();
  int size();
  int front();
  void pop();
  void push(int x);
  bool empty();
};

#endif // _MY_QUEUE_H_

queue.cpp

#include<iostream>
#include "my_queue.h"
using namespace std;

MyQueue::MyQueue() : m_head(0), m_tail(0)
{
  MAX = sizeof(m_q) / sizeof(m_q[0]);
}

int MyQueue::size() {
  if (m_tail > m_head) return m_tail - m_head;
  else return m_tail + MAX - m_head;
}

int MyQueue::front() {
  return m_q[m_head];
}

void MyQueue::pop() {
  if (m_head == m_tail) cout << "Error: queue is empty." << endl;  // under flow
  else m_head = (m_head + 1) % MAX;
}

void MyQueue::push(int x) {
  if (m_head == (m_tail + 2) % MAX) {
    cout << "Error: queue is full." << endl;  // over flow
  } else {
    m_tail = (m_tail + 1) % MAX;
    m_q[m_tail] = x;
  }
}

bool MyQueue::empty() {
  if (m_head == m_tail) return true;
  else return false;
}

main.cpp

#include<iostream>
#include "my_queue.h"
using namespace std;

int main(void) {
  MyQueue queue;

  // 空の状態
  if (queue.empty()) {
    cout << "queue is empty" << endl;
  } else {
    cout << "queue is not empty" << endl;
  }

  // 要素を加える
  queue.push(1);
  queue.push(2);

  if (queue.empty()) {
    cout << "queue is empty" << endl;
  } else {
    cout << "queue is not empty" << endl;
  }

  // 要素を取り出す
  cout << "head: " << queue.front() << " size: " << queue.size() << endl;
  queue.pop();
  cout << "head: " << queue.front() << " size: " << queue.size() << endl;
  queue.pop();
  queue.pop();  
  
  return 0;
}

実行結果

queue is empty
queue is not empty
head: 0 size: 2
head: 1 size: 1
Error: queue is empty.

まとめ

キューを実装しました。リングバッファの考え方についても学びました。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.