Pythonでキューの要素がペアごとに連続しているかどうかを確認する方法

数値が格納されたキューがあるとします。このとき、キュー内の隣り合う要素同士がすべてペアで連続している（差がちょうど1である）かどうかを判定します。

例えば、入力が que = [3,4,6,7,8,9] の場合、出力は True になります。これは 3→4、6→7、8→9 のいずれのペアも差が1だからです。もし途中に差が1でないペアが存在すれば、結果は False となります。

解決手順

この問題は、以下の手順に従って解くことができます。

• キュー q を定義し、与えられたリストの全要素を q に挿入します
• 一時リスト temp を新しく作成します
• q が空になるまで、次の処理を繰り返します
  • キューの先頭要素を temp に追加し、キューからその要素を削除します
• もう一つのリスト temp2 を新しく作成します
• temp が空になるまで、次の処理を繰り返します
  • temp の末尾要素を temp2 に追加し、temp から削除します
• result を True に初期化します
• temp2 のサイズが 1 より大きい間、次の処理を繰り返します
  • x := temp2 の末尾要素を取り出して削除します
  • y := temp2 の末尾要素を取り出して削除します
  • |x − y| が 1 でない場合、result を False に設定します
  • x と y を q に戻します
• temp2 のサイズが 1 の場合は、残りの要素を q に戻します
• result を返します

実装例

理解を深めるために、以下の実装を見てみましょう。

import queue

def solve(que):
    q = queue.Queue()
    for i in que:
        q.put(i)
    temp = []
    while q.qsize() != 0:
        temp.append(q.queue[0])
        q.get()
    temp2 = []
    while len(temp) != 0:
        temp2.append(temp[len(temp) - 1])
        temp.pop()
    result = bool(True)
    while len(temp2) > 1:
        x = temp2[len(temp2) - 1]
        temp2.pop()
        y = temp2[len(temp2) - 1]
        temp2.pop()
        if abs(x - y) != 1:
            result = False
        q.put(x)
        q.put(y)
    if len(temp2) == 1:
        q.put(temp2[len(temp2) - 1])
    return result

que = [3,4,6,7,8,9]
print(solve(que))

入力

[3,4,6,7,8,9]

出力

True

アルゴリズムのポイント

このアプローチでは、まずキューの内容を一時リストに移し替え、さらに逆順のリストを作成することで、元の順序どおりにペアを取り出せるようにしています。末尾から2つずつ要素を取り出して絶対値の差を検証し、検証済みの要素はキューに戻すため、処理後も元のデータ構造が保持されます。時間計算量は O(n)、補助的な記憶領域も O(n) であり、キューのFIFO（先入れ先出し）という制約を守りながら判定を行う点が特徴です。