Soal 5: Stack dan Queue

Dalam dunia informatika, penggunaan struktur data queue (antrian) dan stack (tumpukan) sangatlah umum. Kedua struktur data tersebut memiliki kesamaan yakni bahwa keduanya dapat diimplementasikan menggunakan array. Sedangkan perbedaannya terletak pada cara keluar masuk elemen. Struktur data queue memiliki sifat FIFO (first in first out), artinya elemen yang pertama kali masuk juga akan keluar pertama kali. Sedangkan struktur data stack memiliki sifat LIFO (last in first out), artinya elemen yang terakhir kali masuk akan keluar pertama kali juga.

Pada soal ini, Anda akan mensimulasikan sebuah struktur data yang merupakan gabung antara queue dan stack. Pada struktur data ini, suatu elemen dapat masuk ke bagian awal menggunakan perintah push_front maupun bagian akhir menggunakan perintah push_back. Begitu juga proses pengambilan elemen, dapat mengambil dari bagian awal menggunakan perintah pop_front maupun dari bagian akhir menggunakan perintah pop_back. Diberikan struktur data tersebut dalam keadaan kosong, lakukan beberapa operasi memasukkan dan mengeluarkan elemen, tentukan kondisi akhir dari struktur data tersebut.

FORMAT MASUKAN

Baris pertama berisi sebuah bilangan N (1 ≤ N ≤ 10 000). N baris berikutnya masing-masing berisi sebuah perintah. Sesuai deskripsi di atas, terdapat 4 kemungkinan perintah yakni:

Perintah push_front dan push_back tentunya akan diikuti sebuah elemen berupa bilangan bulat antara 1 sampai 1 000 000. Dan perintah pop_front maupun pop_back tidak akan dilakukan saat struktur data tersebut tidak memiliki elemen.

FORMAT KELUARAN

Elemen-elemen berurutan dari bagian awal sampai bagian akhir yang berada di kondisi akhir struktur data tersebut.

CONTOH MASUKAN

7
push_back 1
push_back 2
push_front 3
push_back 4
push_front 5
pop_back
pop_front

CONTOH KELUARAN

3
1
2