エンジニア実践的基礎: キュー

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

キュー

キューはスタックと対照的なデータ構造です。スタックが一番最後に追加したデータを参照するのに対し、キューは一番最初に追加したデータを参照します。

キューはラーメン屋の行列のようなものです。行列では最初に並んだ人から順にラーメンを食べられます。割り込みはマナー違反です。遅く到着した人ほど入店するのに時間がかかります。

行列のイメージ

一番直感的なキューの実装は単方向リストです。単方向リストはノードが次のノードへの参照を通してつながる電車のようなデータ構造でしたね。この先頭から順にノードを辿る方法がまさにキューの仕様です。

単方向リストを使ったキュー

もちろん単方向リストと全く同じではなく、キューは他のノードの間にノードを挿入できません。新しいノードは必ず後ろから追加します。また、キューは先頭のキューを取り出さないと後続のキューを参照できません。単方向リストはノードを取り出さなくでも後続のキューを参照できます。

先頭ノードを取り出すことを「デキュー(Dequeue)」、末尾ノードに新しいノードを追加することを「エンキュー(Enqueue)」と呼びます。

実装

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.head:
            # 末尾に新しいノードを追加
            self.tail.next, self.tail = new_node, new_node
        else:
            # ノードが１つなら先頭と末尾が同じノード
            self.head = self.tail = new_node

    def dequeue(self):
        if self.head is None:
            return None
        data = self.head.data
        # 次のノードを先頭にする
        self.head = self.head.next
        if self.head is None:
            # 先頭ノード末尾もNone
            self.tail = None
        return data

計算量

小話: 仕様と実装

今回の解説ではキューを単方向リストで実装しました。しかしキューの実装方法は他にもあります。例えば動的配列を先頭から値を取り出し、末尾に新しい値を追加すればキューになります。ただし、動的配列のを使った実装はデータの取り出し時にすべてのノードを左にシフトする必要があり(O(n) の計算量)、単方向リストの実装に比べて非効率です。

このように仕様に対し実装は複数存在します。仕様とは「何(What)」であり実装は「方法(How)」です。いちごのショートケーキの仕様が「生クリームの上にいちごが乗ったケーキ」とすると、その調理方法が実装になります。

確かに実装方法を理解して記憶することも大事ですが、大抵の場合すぐに忘れてしまいます。ですから実装方法にこだわるより、仕様をしっかりと記憶する方が大事です。仕様さえ覚えていれば、あで実装方法は調べられます。それに、実務でプログラミングするときは実装方法よりも、特定の条件下でトレードオフを意識しながら最適なデータ構造を決める場合が多く、その判断基準はデータ構造の仕様の違いです。