Go言語で予約キャンセル機能付きのキューを実装する（ジェネリクス対応版）

Aru

Go言語を使用して、予約キャンセル機能を備えたFIFO（先入れ先出し）キューの実装方法を詳しく解説します。また、ジェネリクスに対応することで再利用性を高めた実装を行います。この記事では、キューの基本的な構造から、Go言語のmapやスライスを使ったキューの実装方法と、さらに予約キャンセル機能の追加する方法について解説します。

Contents

（FIFO）キューとは
予約キャンセル機能付きFIFOキューの実装
- キャンセル機能付きFIFOキュー（計算量を無視した実装）
- キャンセル処理を高速化した予約キャンセル機能付きFIFOキュー
まとめ

（FIFO）キューとは

FIFOキュー（First-In-First-Out Queue）とは、最初に追加された要素が最初に取り出されるデータ構造です。

FIFOキューは、順序を守ることが重要な場面で広く利用されます。たとえば、チケット販売のWebサイトで購入要求を、要求順（先着順）に処理する場合などに利用できます。

ただ、Webの予約などでは、リクエスト後にキャンセルを行う処理が必要なこともあります。

そこで、ここでは、キューの基本機能に加えて「一度リクエストした要求を削除する機能」を持ったキューを実装してみます。

予約キャンセル機能付きFIFOキューの実装

今回の実装では、リクエスト番号をキューに入れて、リクエスト番号を使ってキャンセルができるキューを実装してみます。

コーディング面談の問題で似た題材を見つけて面白いと思ったので、自分なりに考えて実装してみました。

キャンセル機能付きFIFOキュー（計算量を無視した実装）

とりあえず、キャンセル機能付きのFIFOキューをジェネリクスを使って実装してみました。

以下が、Go言語のプログラムになります。

package main

import (
	"fmt"
)

// Queue ... キューを表す構造体です。
type Queue[T comparable] []T

// New ... キューの新規作成
func New[T comparable]() Queue[T] {
	var ret Queue[T]
	return ret
}

func (q *Queue[T]) Push(x T) {
	*q = append(*q, x)
}

func (q *Queue[T]) Pop() (T, bool) {
	var x T
	if len(*q) == 0 {
		return x, false
	}
	x = (*q)[0]
	*q = (*q)[1:]
	return x, true
}

func (q *Queue[T]) Cancel(x T) {
	pos := -1
	for i := 0; i < len(*q); i++ {
		if (*q)[i] == x {
			pos = i
			break
		}
	}

	if pos == -1 {
		return // not found
	}

	*q = append((*q)[:pos], (*q)[pos+1:]...)
}

func main() {

	q := New[int]()

	for i := 0; i < 100; i++ {
		q.Push(i)
	}

	for i := 0; i < 100; i++ {
		if i%3 == 1 {
			q.Cancel(i)
		}
	}

	for {
		v, ok := q.Pop()
		if ok == false {
			break
		}
		fmt.Println(v)
	}
}

それぞれの関数の処理は以下になります。

New
新しくキューを作成する
Push
キューに要素を入れる
Pop
キューから要素を取り出す
Cancel
キューから指定した要素を削除する

mainでは、int型のキューを作成し、0~99の値をPush、その後3で割ったあまりが1である要素を全てキャンセルし、最後に全ての要素をキューからPopしています。

このプログラムの計算量は以下になります。

Push　末尾に追加する処理はO(1)
Pop　先頭を取り出す処理はO(1)
Cancel　キャンセルは、要素を見つける処理があり、全体をスキャンするためO(n)。また、要素を見つけた場合は、後ろを詰める処理を行うのでO(n)

計算量を見るとCancelの処理が重いです。これを高速化することを考えます。

削除する要素を見つける処理はハッシュを使うとO(1)にできます。削除はListを使うとO(1)にできますが、今回は別の方法でやってみます。

キャンセル処理を高速化した予約キャンセル機能付きFIFOキュー

以下が、高速化したプログラムになります。

先程と違い、Queueは、データ（data）と、キャンセルされたかどうかを格納する辞書(cancels）を要素として持ちます。

package main

import (
	"fmt"
)

// Queue ... キューを表す構造体です。
type Queue[T comparable] struct {
	cancels map[T]bool
	data []T
}

// New ... キューの新規作成
func New[T comparable]() Queue[T] {
	var ret Queue[T]
	ret.data = []T{}
	ret.cancels = make(map[T]bool)
	return ret
}

func (q *Queue[T]) Push(x T) {
	q.data = append(q.data, x)
}

func (q *Queue[T]) Pop() (T, bool) {
	var x T
	for len(q.data) > 0 {
		x = q.data[0]
		if q.cancels[x] {
			q.data = q.data[1:]
		} else {
			break
		}
	}
	if len(q.data) == 0 {
		return x, false
	}
	x = q.data[0]
	q.data = q.data[1:]
	return x, true
}

func (q *Queue[T]) Cancel(x T) {
	q.cancels[x] = true
}

func main() {

	q := New[int]()

	for i := 0; i < 100; i++ {
		q.Push(i)
	}

	for i := 0; i < 100; i++ {
		if i%3 == 1 {
			q.Cancel(i)
		}
	}

	for {
		v, ok := q.Pop()
		if ok == false {
			break
		}
		fmt.Println(v)
	}
}

それぞれの関数の処理は以下になります。

New
新しくキューを作成する
Push
キューに要素を入れる（処理は同じ）
Pop
キューから要素を取り出す（キャンセルされた要素をスキップしてから、要素を取り出す）
Cancel
削除対象の要素をcancelsに格納する

先ほどのプログラムとはPopとCancelの処理が変わっています。このプログラムでは、キャンセル（Cancel）が行われてもマーキングするだけでキャンセルせずに、取り出す部分（Pop）で削除されたデータをスキップする処理を行います。

演算量は以下になります。

Push　末尾に追加する処理は、O(1)
Pop　削除対象の数により演算量は変化しますが、基本的に先頭を取り出す処理はO(1)
Cancel　キャンセルは、マーキングするだけなのでO(1)

以上のように、ちょっとだけプログラムを書き換えることでキャンセル処理を高速化できます

container/listを使わない理由

Go言語で用意されているListを利用すれば、削除処理をO(1)にできます。ただ、リンクリストはprev, nextの双方向へのポインタが必要になり、メモリ的には不利です。リストを使っても削除対象の検索を高速化するためのmapは必要になるので、Listを使うとメモリ消費が増えることになります。今回は、List構造のメモリ消費を考えて、Popで削除する処理にしました。

もちろんListを使った実装の方がよい場合もあります。