演習課題「キューを完成させる」
Q 個のクエリが与えられます。空の配列 A を用意したあと、 Q 個のクエリに応じて以下の 2 種類の処理をしてください。
・ PUSH X: 配列 A の末尾に 文字 X を追加
・ POP: 配列 A の先頭にある要素を出力し、削除
各クエリの処理が終わったあと、配列 A の各要素の値を半角スペース区切りで出力してください。
入力される値
Q
query_1
query_2
...
query_Q
1 行目に Q が与えられます。続く Q 行にクエリが与えられます。 各クエリは
1 X
または
2
の形式で与えられ、最初の数値が 1 のとき PUSH 、 2 のとき POP を表します。 PUSH のときは続いて文字 X が与えられます。
条件
すべてのテストケースにおいて、以下の条件をみたします。
・ Q は 1 以上 100 未満
・ query の最初の数値は 1 または 2
・ X はアルファベット小文字
・ クエリ POP が与えられるときは必ず配列 A に要素が 1 つ以上存在する
期待する出力
各クエリの処理が終わったあと、配列 A の各要素の値を半角スペース区切りで出力してください。ただし、 POP のクエリが与えられた場合は配列 A の各要素を出力する 前に 配列 A の先頭にある要素を出力する必要があります。各行の末尾には改行を入れ、余計な文字、空行を含んではいけません。
( 1 回目のクエリが POP の場合) 配列 A の先頭にある要素
1 回目のクエリ処理後の A
( 2 回目のクエリが POP の場合) 配列 A の先頭にある要素
2 回目のクエリ処理後の A
...
( N 回目のクエリが POP の場合) 配列 A の先頭にある要素
N 回目のクエリ処理後の A
期待する出力値
e
e a
e a c
e
a c
＃05:キューの実装
このチャプターでは、キューの実装について学習します。
キューを実装するには、キューの先頭に要素を追加する push 操作とキューの末尾の要素を削除する pop 操作を実装する必要があります。
キューを配列に見立てることで、各操作は次のような配列の操作に対応させることができます。
push ・・・配列の末尾への要素の追加
pop・・・配列の先頭の要素の削除
お使いの言語によっては queue が言語ごとに用意されている標準ライブラリで用意されていることがあります。
実際に queue を使って問題を解く際には標準ライブラリを用いた方が楽であることが多いです。
「言語名 queue」などで調べてみると良いでしょう。
入力値5
1 a
1 d
2
1 r
2
コードimport java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] queue = new char[256]; // キュー本体
int queue_size = 0; // キューに入っている要素数
int queue_front = 0; // キューの先頭
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
int query = sc.nextInt();
if (query == 1) {
char x = sc.next().charAt(0);
queue[queue_size] = x;
queue_size++;
} else if (query == 2) {
System.out.println(queue[queue_front]);
queue_front++;
}
}
for (int j = queue_front; j < queue_size; j++) {
System.out.println(queue[j]);
}
sc.close();
}
}