PRAKTIKUM 9 - STRUKTUR DATA
STACKS AND QUEUES
Learning outcomes:
1. Mampu menjelaskan konsep LIFO pada Stacks dan FIFO pada Queues
2. Mampu mengimplementasikan operasi dasar Stack dan Queue (push, pop, peek)
dengan struktur data Array.
3. Mampu menjelaskan implementasi Stack pada parsing arithmetic expressions.
4. Mampu menjelaskan dan mengimplementasikan circular Queue.
5. Mampu mengimplementasikan struktur data Stacks dan Queues pada program.
IDENTITAS PRAKTIKAN
NIM :
Nama Lengkap :
Kelas :
Praktikum 9 | Stacks and Queues
Struktur data yang dibahas pada praktikum kali ini adalah Stacks dan Queues. Selain
itu, ada pula struktur data yang sejenis yaitu priority queue (tidak dibahas pada praktikum
ini). Fungsi ketiga struktur data ini lebih sering digunakan sebagai programmer’s tool.
Yaitu, digunakan sebagai alat bantu konseptual penyimpanan data, bukan sebagai
penyimpanan data itu sendiri.
Stack, queue, dan priority queue lebih abstrak dibandingkan dengan struktur
penyimpanan data seperti arrays dan beberapa yang lainnya. Mekanisme mendasar untuk
mengimplementasikan stack, queue, dan priority queue dapat berupa Arrays sebagaimana
yang ditunjukkan pada pembahasan modul ini. Selain itu, dapat juga menggunakan
“Linked list”. Mekanisme mendasar untuk Priority queue dapat juga berupa salah satu
jenis khusus dari struktur data tree yang disebut dengan heap.
Pada struktur data Arrays, semua item dapat diakses, sedangkan pada stack, queue,
dan priority queue akses tersebut dibatasi, yaitu hanya satu item yang dapat diakses untuk
dibaca atau dihapus.
A. PENDAHULUAN
1. Stacks (tumpukan) merupakan suatu susunan koleksi data dimana data yang dapat
ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut
dengan top of stack. Dengan kata lain, stack hanya mengijinkan akses pada item yang
terakhir dimasukkan.
Stacks bersifat LIFO (Last In First Out). Jelaskan sifat LIFO pada stacks dan
gambarkan skema lengkap dari LIFO!
jawaban
22
Praktikum 9 | Stacks and Queues
2. Operasi utama pada Stacks yaitu push dan pop. Selain dua operasi tersebut, juga
terdapat operasi peek pada Stacks. Jelaskan masing-masing dari tiga operasi tersebut!
jawaban
3. Tulislah listing program berikut ini dan jelaskan tiap barisnya!
#include <iostream>
using namespace std;
class Stack {
private:
int maxSize;
long* stackArray;
int top;
public:
Stack(int size) {
maxSize = size;
stackArray = new long[maxSize];
top = -1;
}
~Stack() {
delete[] stackArray;
}
void push(long item) {
if (!isFull()) {
stackArray[++top] = item;
cout << "Pushed item: " << item << endl;
} else {
cout << "Stack is full. Cannot push item: " << item << endl;
}
}
23
Praktikum 9 | Stacks and Queues
long pop() {
if (!isEmpty()) {
long item = stackArray[top--];
cout << "Popped item: " << item << endl;
return item;
} else {
cout << "Stack is empty. Cannot pop item." << endl;
return -1;
}
}
long peek() {
if (!isEmpty()) {
cout << "Top item is: " << stackArray[top] << endl;
return stackArray[top];
} else {
cout << "Stack is empty. Nothing to peek." << endl;
return -1;
}
}
bool isEmpty() {
return (top == -1);
}
bool isFull() {
return (top == maxSize - 1);
}
};
int main() {
Stack stack(5);
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);
[Link](60);
[Link]();
[Link]();
[Link]();
[Link]();
cout << "Is stack empty? " << ([Link]() ? "Yes" : "No") << endl;
24
Praktikum 9 | Stacks and Queues
[Link]();
[Link]();
[Link]();
cout << "Is stack empty? " << ([Link]() ? "Yes" : "No") << endl;
return 0;
}
Apa output dari listing program tersebut? Jelaskan!
jawaban
4. Setelah anda memahami tiap baris listing nomer 3. Tuliskan kesimpulan logika untuk
setiap method pada class Stack: method push(), pop(), peek(), isEmpty(), dan
isFull()!
jawaban
5. Salah satu aplikasi yang menggunakan struktur penyimpanan stack adalah parsing
ekspresi aritmatika. Tuliskan langkah manual untuk merubah notasi infix:
U*(I+N)/M^L –G
menjadi notasi postfix menggunakan teknik stack!
25
Praktikum 9 | Stacks and Queues
jawaban
6. Queues (antrian) adalah struktur data yang hampir mirip dengan stack. Perbedaannya
adalah pada queues, akses item bagi yang pertama dimasukkan. Queues bersifat FIFO
(First In First Out). Jelaskan sifat FIFO pada queues dan gambarkan skema lengkap
dari FIFO!
26
Praktikum 9 | Stacks and Queues
7. Berikut ini listing Queue dengan Array. Tulis dan jelaskan!
#include <iostream>
using namespace std;
class Queue {
private:
int maxSize;
long* queArray;
int front;
int rear;
int nItems;
public:
Queue(int size) {
maxSize = size;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
~Queue() {
delete[ ] queArray;
}
void insert(long value) {
if (isFull()) {
cout << "Queue is full. Cannot insert item: " << value << endl;
} else {
if (rear == maxSize - 1) {
rear = -1;
}
queArray[++rear] = value;
nItems++;
}
}
long remove() {
if (isEmpty()) {
cout << "Queue is empty. Cannot remove item." << endl;
return -1;
} else {
long temp = queArray[front++];
if (front == maxSize) {
front = 0;
}
nItems--;
return temp;
}
}
27
Praktikum 9 | Stacks and Queues
long peek() {
if (isEmpty()) {
cout << "Queue is empty. Nothing to peek." << endl;
return -1;
} else {
return queArray[front];
}
}
bool isEmpty() {
return (nItems == 0);
}
bool isFull() {
return (nItems == maxSize);
}
int size() {
return nItems;
}
};
int main() {
Queue queue(5);
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);
[Link](60);
cout << "Front item is: " << [Link]() << endl;
cout << "Removed item: " << [Link]() << endl;
cout << "Removed item: " << [Link]() << endl;
[Link](60);
[Link](70);
while (![Link]()) {
cout << "Removed item: " << [Link]() << endl;
}
cout << "Is queue empty? " << ([Link]() ? "Yes" : "No") << endl;
return 0;
}
28
Praktikum 9 | Stacks and Queues
Tuliskan output dari listing tersebut dan jelaskan!
jawaban
8. Setelah anda memahami tiap baris listing nomer 7. Tuliskan kesimpulan logika untuk
setiap method pada class Queue: method insert(), remove(), peek(),
isEmpty(), dan isFull()!
jawaban
9. Apa jenis queue (linier/circular) yang diimplementasikan pada listing tersebut? Beri
alasan/bukti dari jawaban anda!
jawaban
29
Praktikum 9 | Stacks and Queues
B. PRAKTIKUM
1. Implementasi Stack
Salah satu contoh program sederhana yang mengimplementasikan stack adalah
program pembalik kata. Stack digunakan untuk membalik huruf. Langkah pertama,
tiap katakter pada String input diekstrak dan dimasukkan kedalam stack. Kemudian
tiap karakter tersebut dikeluarkan dan ditampilkan sebagai output. Karena memiliki
sifat LIFO, maka keluaran stack adalah karakter-karakter dengan urutan yang
berkebalikan dengan input.
Buatlah program pembalik kata tersebut dengan membuat 3 class, yaitu:
a. class “stack”. Class ini digunakan untuk menyimpan setiap karakter input pada
stack array. Berisi constructor dan method-method operasi stack.
b. class “pembalik”. Class ini digunakan untuk membaca setiap karakter input,
menyimpan karakter dengan memanggil method push() pada class “stack”
(point a), dan membalik input dengan memanggil method pop() pada class
“stack” (point a). Tiap karakter keluaran dari stack tersebut
disimpan/ditambahkan (append) pada String output sebagai keluaran yang akan
ditampilkan.
c. class “AppPembalik”. Class ini berisi method main. Digunakan untuk deklarasi
dan inisialisasi input, memanggil class “pembalik” untuk membalik input dan
mendapatkan output kata yang telah dibalik, serta menampilkan output pada
console.
Untuk membaca tiap karakter String, anda dapat mengunakan method charAt()
yang terdapat pada class String, misal [Link](index).
Contoh program pembalik kata ditunjukkan pada Gambar 3.1. Anda dapat
mengerjakan sebagaimana Gambar 3.1 (a) dan point tambahan akan diberikan jika
Anda mengerjakan sebagaimana Gambar 3.1 (b).
(a)
(b)
Gambar 3.1 Contoh output program pembalik kata. (a) String input diinisialisasi
secara langsung pada listing program (hardcode). (b) String input didapat dari
masukan dengan keyboard, program dapat membaca dan membalikkan input
secara berulang-ulang
30
Praktikum 9 | Stacks and Queues
2. Implementasi Queue
Implementasi queue banyak didunia nyata, sebagaimana antrian. Buatlah program
simulasi antrian dengan mengimplementasikan Queue Stack. Simulasi antrian
menunjukkan (lihat Gambar 3.2):
- penambahan objek pada daftar antrian. Lakukan beberapa kali hingga antrian
penuh. Ketika objek ditambahkan pada antrian yang penuh maka program akan
menampilkan keterangan antrian penuh.
- Menampilkan isi antrian
- Satu persatu objek keluar antrian hingga antrian kosong
Gambar 3.2 Output program simulasi antrian
3. Latihan Queue
Latihan: Antrian di Loket Tiket
Buat program antrian untuk simulasi loket tiket. Setiap kali pengguna menginput nama,
nama tersebut dimasukkan ke dalam antrian. Jika pengguna memilih opsi untuk "layani
pelanggan," nama paling depan dalam antrian akan dihapus dan ditampilkan sebagai
pelanggan yang dilayani.
Langkah-langkah:
- Buat fungsi `enqueue` untuk menambah pelanggan.
- Buat fungsi `dequeue` untuk melayani pelanggan.
- Tampilkan antrian saat ini setelah setiap operasi.
31
Praktikum 9 | Stacks and Queues
Contoh Output:
```plaintext
Tambah pelanggan: Andi
Tambah pelanggan: Budi
Tambah pelanggan: Cici
Layanan pelanggan berikutnya: Andi
Antrian saat ini: Budi, Cici
```
4. Latihan : Sistem Pengingat Tugas
Buat program yang menyimpan daftar tugas menggunakan queue, di mana tugas baru
ditambahkan ke akhir daftar. Setiap kali tugas selesai, tugas paling awal dalam daftar
dihapus.
Langkah-langkah:
- Buat fungsi untuk menambahkan tugas (`enqueue`).
- Buat fungsi untuk menyelesaikan tugas (`dequeue`).
- Tampilkan tugas yang tersisa.
Contoh Output:
```plaintext
Tambahkan tugas: Belajar Matematika
Tambahkan tugas: Belajar Bahasa Inggris
Tugas selesai: Belajar Matematika
Tugas tersisa: Belajar Bahasa Inggris
```
5. Latihan Stack
Latihan: Pembalikan Kata
Buat program untuk membalik urutan huruf dalam sebuah kata menggunakan stack.
Setiap huruf dalam kata dimasukkan ke dalam stack, kemudian diambil satu per satu dari
stack untuk menghasilkan kata yang terbalik.
Langkah-langkah:
- Minta pengguna memasukkan kata.
- Masukkan setiap huruf ke dalam stack.
- Ambil huruf dari stack untuk membentuk kata yang terbalik.
Contoh Output:
```plaintext
Masukkan kata: HELLO
Kata terbalik: OLLEH
```
Latihan : Validasi Kurung dalam Ekspresi
Buat program untuk memvalidasi kurung dalam sebuah ekspresi matematika
menggunakan stack. Jika semua kurung terbuka (`(`) memiliki pasangan kurung tutup
(`)`), ekspresi dianggap valid. Jika tidak, ekspresi dianggap tidak valid.
Langkah-langkah:
- Loop setiap karakter dalam ekspresi.
- Jika karakter adalah `(`, masukkan ke stack.
- Jika karakter adalah `)`, keluarkan `(` dari stack.
- Pada akhir ekspresi, stack harus kosong agar ekspresi valid.
32
Praktikum 9 | Stacks and Queues
Contoh Output:
```plaintext
Masukkan ekspresi: (5+3)*(2+4)
Ekspresi valid
Masukkan ekspresi: (5+3)*2+4)
Ekspresi tidak valid
```
Latihan: Konversi Infix ke Postfix
Buat program untuk mengonversi ekspresi infix (seperti `A + B * C`) menjadi postfix
(seperti `A B C * +`) menggunakan stack. Ini adalah aplikasi penting dalam pemrosesan
ekspresi aritmatika.
Langkah-langkah:
- Baca setiap karakter dalam ekspresi infix.
- Jika karakter adalah operan, tambahkan ke output.
- Jika karakter adalah operator, gunakan stack untuk mengelola prioritas operator.
6. Latihan Gabungan Queue dan Stack
Latihan : Penyaringan Pasien di Rumah Sakit
Bayangkan di sebuah rumah sakit terdapat dua antrian, yaitu untuk pasien dengan
kondisi darurat (prioritas) dan pasien reguler. Pasien darurat akan dilayani terlebih
dahulu, tetapi setiap pasien yang ditambahkan akan disimpan ke dalam stack untuk
memudahkan penghapusan pasien yang telah dilayani jika terdapat lebih banyak pasien
darurat.
Langkah-langkah:
- Gunakan queue untuk menambah pasien reguler.
- Gunakan stack untuk menambah pasien darurat.
- Setiap kali melayani, keluarkan pasien dari stack (prioritas) terlebih dahulu, lalu dari
queue jika stack kosong.
Dengan latihan-latihan ini, Anda dapat mempraktikkan berbagai skenario dengan
**queue** dan **stack** serta memahami perbedaan penggunaannya.
33
Praktikum 9 | Stacks and Queues
C. KESIMPULAN
Kesimpulan yang diperoleh dari pembahasan praktikum kali ini adalah:
1. Tentang konsep dan implementasi Stack
2. Tentang konsep dan implementasi Queue
34