キュー

キュー (Queue) は、多くのアルゴリズムで使われる主要なデータ構造の一つで、実際の生活での行列にとても似ています。最初に追加された要素が、最初に「処理」されて取り除かれるしくみです。

たとえば、コーヒーを待って並んでいるアリたちの列を想像してみましょう。列の先頭にいるアリがコーヒーを受け取って列を抜けると、その次のアリがまたコーヒーを受け取り、列を抜ける……という流れで、列が空になるまで続きます。

ほとんどの一般的なプログラミング言語 (Python、C++、Java など) では、キューのデータ構造があらかじめ実装されているため、宣言や利用はとても簡単です。それでも、リンクドリストなどを使って自分でキューを実装する方法も考えられます。あなたならどう実装しますか 🤔?

from queue import Queue

q = Queue()    # 新しいQueueを作成
q.put(1)       # Queueの先頭に1を追加
q.put(2)       # 次に2を追加
q.put(3)       # 2の次に3を追加

# get()を使ってQueueから要素を取り除く
print(q.get()) # 1を出力
print(q.get()) # 2を出力
print(q.get()) # 3を出力

チャレンジ: キューのシミュレーション

このシステムでは、店内にいる顧客を管理する必要があります。やることはシンプルで、顧客を待ち行列に追加する操作と、先頭の顧客が満足して離れる操作が必要です。顧客を取り除くたびに、その顧客の名前を出力してください。

入力

最初の行には、整数 n (1 ≤ n ≤ 100 000) が1つ含まれます。

続く n 行には、操作内容が書かれており、操作は add または pop のいずれかです:

• add の場合は、その後ろに名前が続きます。ここで指定された顧客を待ち行列に追加します。

• pop の場合は操作名のみで、他に何も続きません。

いずれの pop 操作が実行される際にも、必ずキューに顧客がいる状態が保証されています。

また、名前は最大で20文字以内であることが保証されています。

出力

各 pop 操作が実行されるたびに、待ち行列の先頭にいる顧客の名前を出力してください。

例