ETS Struktur Data
Nama : Benedictus Imanuel Wicaksono
NRP : 5025251039
NRP : 5025251039
Soal Struktur Data
1. Jelaskan struktur data Array. Digunakan untuk apa Array, Berikan contoh
penggunaanya dalam aplikasi.
Array merupakan struktur data linier yang menyimpan kumpulan elemen dengan tipe data yang sama. Elemen-elemen tersebut disimpan dalam blok memori berdekatan. Tiap elemen dalam array dapat diakses secara langsung dengan indexing. Array dapat digunakan saat perlu menyimpan data dalam jumlah banyak dengan satu tipe data yang sama dan perlu akses cepat dengan kompleksitas waktu O(1). Array lebih direkomendasikan untuk implementasi yang lebih sederhana dibanding struktur data abstrak (ADT). Berikut adalah contoh penggunaannya dalam aplikasi:
- Tokopedia, untuk menyimpan deretan barang dimasukkan ke dalam keranjang belanja (cart).
- Spotify, untuk menyimpan daftar antrean lagu di playlist supaya bisa melompat ke lagu tertentu secara instan, karena Array mendukung random access.
- Mobile Legends, menyimpan kumpulan data skor pemain untuk diurutkan dan ditampilkan pada Leaderboard top global.
- Instagram, menyimpan deretan postingan di halaman feed atau untuk menyimpan daftar riwayat pencarian agar selalu tampil berurutan.
2. Diketahui Stack berupa Linked List dengan kondisi mula-mula Stack kosong.
Gambarkan Stack berupa Double Linked List tersebut beserta posisi penunjuknya
(pointer), jika ada perintah :
a. Push(Top,60), Push(Top,40), Pop(Top,Item)
b. Push(Top,25), Pop(Top,Item), Pop(Top,Item)
c. Pop(Top,Item), Pop(Top,Item), Push(Top,50)
Karena implementasi dalam linked list, maka ada previous, current, dan next.
Ilustrasi:
a. Stack awal:
Top | NULL | NULL | NULL |
Push(Top, 60):
Top | NULL | 60 | NULL |
Push(Top, 40):
Top | NULL | 40 | |
| | 60 | NULL|
Pop(Top,Item):
Top | NULL | 60 | NULL |
b. Stack awal:
Top | NULL | NULL | NULL |
Push(Top, 25):
Top | NULL | 25 | NULL |
Pop(Top,Item):
Top | NULL | NULL | NULL |
Pop(Top,Item):
(Error: Stack Underflow)
c. Stack awal:
Top | NULL | NULL | NULL |
Pop(Top,Item):
(Error: Stack Underflow)
Pop(Top,Item):
(Error: Stack Underflow)
Push(Top, 50):
Top | NULL | 50 | NULL |
3. Diketauhui Ekspresi berikut E = a + (2·b^3)/(f − g) + d·h
- Ubahlah ke dalam notasi Postfix
- Implementasikan menggunakan Stack dan buat screenshot eksekusinya.
#include <bits/stdc++.h>
using namespace std;
int precendence(char op){
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
else return 0;
}
bool isoperator(char c){
return(c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
string intopost(string infix){
stack<int> st;
string postfix = "";
for (int i = 0; i < infix.length(); i++){
char c = infix[i];
if (isalnum(c)){
postfix += c;
}
else if (c == '(') st.push(c);
else if (c == ')'){
while(!st.empty() && st.top() != '('){
postfix += st.top();
st.pop();
}
if (!st.empty()) st.pop();
}
else if (isoperator(c)){
while (!st.empty() && precendence(st.top()) >= precendence(c)){
postfix += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty()){
postfix += st.top();
st.pop();
}
return postfix;
}
int main(){
string infix;
cout << "Masukkan infix: ";
cin >> infix;
string postfix = intopost(infix);
cout << "Postfix: " << postfix << endl;
return 0;
}
Output:
4. Diketahui maksimum Queue = 9 elemen dengan kondisi mula-mula Queue kosong.
Gambarkan Queue beserta posisi Front dan Rear, jika ada perintah :
a. Tambah Angka 19
b. Tambah Angka 7
c. Hapus 2 Angka
d. Tambah Angka 40
e. Hapus 3 Angka
f. Tambah Angka 18
Maksimum queue 9 elemen (indeks 0-8)
Kondisi awal: queue kosong (front = -1, rear = -1)
|(indeks 0)|(indeks 1)|(indeks 2)|(indeks 3)|(indeks 4)|(indeks 5)|(indeks 6)|(indeks 7)|(indeks 8)|
a. Tambah Angka 19 (enqueue)
front = 0, rear = 0
| 19 | | | | | | | | |
b. Tambah Angka 7 (enqueue)
front = 0, rear = 1
| 19 | 7 | | | | | | | |
c. Hapus 2 Angka (dequeue 2 kali)
- Hapus ke-1: angka 19 keluar.
front = 0, rear = 0
| 7 | | | | | | | | |
- Hapus ke-2: angka 7 keluar.
(karena queue sudah kosong, front dan rear di-reset)
front = -1, rear = -1
| | | | | | | | | |
d. Tambah Angka 40 (enqueue)
front = 0, rear = 0
| 40 | | | | | | | | |
e. Hapus 3 Angka (dequeue 3 kali)
- Hapus ke-1: angka 40 keluar (queue kembali kosong, front dan rear di-reset -1).
- Hapus ke-2: Error, Queue Underflow (kosong, tidak ada yang bisa dihapus).
- Hapus ke-3: Error, Queue Underflow.
front = -1, rear = -1
| | | | | | | | | |
f. Tambah Angka 18 (enqueue)
front = 0, rear = 0
| 18 | | | | | | | | |
5. Soal Studi Kasus di halaman ke 2...
Studi Kasus: Antrian Layanan Akademik
Deskripsi Masalah
Di sebuah kampus, mahasiswa sering datang ke bagian layanan akademik (misalnya untuk
KRS, surat aktif kuliah, atau konsultasi administrasi). Untuk menjaga keteraturan, sistem
menggunakan antrian (queue) dengan prinsip:
FIFO (First In First Out) → yang datang lebih dulu, dilayani lebih dulu.
Sebuah sistem akademik memiliki fitur:
1. Mahasiswa mengambil nomor antrian.
2. Petugas melayani mahasiswa berdasarkan urutan.
3. Sistem dapat menampilkan antrian saat ini.
4. Sistem dapat mengecek siapa yang sedang dilayani.
5. Enqueue → Mahasiswa mengambil nomor
6. Dequeue → Mahasiswa dipanggil
7. Front → Mahasiswa yang sedang dilayani
8. Rear → Mahasiswa terakhir dalam antrian
Pertanyaan:
1. Jelaskan bagaimana struktur data queue digunakan dalam sistem ini.
Struktur data queue digunakan dalam sistem ini berdasarkan prinsip FIFO (First In First Out) ketika q.push() bertindak sebagai proses enqueue untuk menambahkan data mahasiswa baru ke posisi paling belakang (rear). Saat petugas siap memanggil, sistem menggunakan perintah q.front() untuk mengidentifikasi mahasiswa yang berada di urutan paling depan (front), dan setelah selesai dilayani fungsi q.pop() akan mengeksekusi proses Dequeue untuk mengeluarkan data mahasiswa tersebut dari memori antrian sehingga urutan di belakangnya otomatis bergeser maju. Seluruh siklus pelayanan dan pergeseran ini berjalan aman di bawah pengecekan kondisi !q.empty(), yang memastikan bahwa sistem tidak akan mengalami error akibat mencoba memanggil atau menghapus antrian yang sudah tidak ada orangnya.
2. Buat algoritma untuk:
o Menambahkan mahasiswa ke antrian (enqueue)
Menggunakan push ke queue bernama antrian dengan fungsi pushantrian, contohnya pushantrian(antrian, Mahasiswa A).
Menggunakan push ke queue bernama antrian dengan fungsi pushantrian, contohnya pushantrian(antrian, Mahasiswa A).
o Melayani mahasiswa (dequeue)
Menggunakan pop ke queue bernama antrian dengan fungsi popantrian contohnya popantrian(antrian).
3. Implementasikan program sederhana menggunakan bahasa pemrograman (misalnya
C++).
#include <bits/stdc++.h>
using namespace std;
void pushantrian(queue<string> &q, string nama) {
q.push(nama);
cout << "Status: " << nama << " masuk antrian" << endl;
}
void popantrian(queue<string> &q) {
if (!q.empty()) {
cout << q.front() << " dilayani" << endl;
q.pop();
}
}
void printantrian(queue<string> q) {
cout << "\nKondisi antrian terkini:" << endl;
int urutan = 1;
while (!q.empty()) {
cout << urutan << ". " << q.front() << endl;
q.pop();
urutan++;
}
}
int main() {
queue<string> antrian;
cout << "-----------------------------------" << endl;
pushantrian(antrian, "Mahasiswa A");
pushantrian(antrian, "Mahasiswa B");
pushantrian(antrian, "Mahasiswa C");
cout << "-----------------------------------" << endl;
popantrian(antrian);
cout << "-----------------------------------" << endl;
pushantrian(antrian, "Mahasiswa D");
printantrian(antrian);
return 0;
}
4. Simulasikan proses:
o Mahasiswa A, B, C masuk antrian
o Mahasiswa pertama dilayani
o Tambah mahasiswa D
o Tampilkan kondisi antrian
Link demo: https://youtu.be/ZBXTMEKJSjE
Source code: https://github.com/xbggnr/ETS-Strukdat.git
-- Terima Kasih --
Komentar
Posting Komentar