TUGAS PERTEMUAN 5_STRUKTUR DATA (D)

 Nama : Rado Putra Yustisiawan

NRP : 5025251048

Kelas : Struktur Data D

1) KONSEP DASAR STACK

1.1 PENJELASAN MATERI

Stack atau tumpukan adalah sebuah struktur data linear yang mengikuti prinsip LIFO (Last In, First Out). Konsep ini berarti data yang terakhir kali dimasukkan ke dalam tumpukan akan menjadi data yang pertama kali dikeluarkan.

Bayangkan sebuah tumpukan piring atau tumpukan buku; kamu hanya bisa menambah atau mengambil piring dari bagian paling atas. Jika kamu ingin mengambil piring paling bawah, kamu harus mengeluarkan semua piring di atasnya satu per satu. Dalam pemrograman, titik akses tunggal ini disebut sebagai Top (puncak). Stack sangat berguna dalam algoritma yang membutuhkan pembalikan data atau penyimpanan status sementara (seperti fitur Undo/Redo pada teks editor).

1.2 OPERASI DASAR PADA STACK

Untuk mengelola data di dalam stack, terdapat beberapa operasi standar yang harus dipahami:

• Push: Operasi untuk memasukkan atau menambahkan elemen baru ke posisi paling atas (top).

• Pop: Operasi untuk menghapus atau mengambil elemen yang berada di posisi paling atas.

• Peek / Top: Operasi untuk melihat nilai atau informasi pada elemen teratas tanpa menghapusnya dari stack.

• isEmpty: Fungsi pengecekan untuk mengetahui apakah stack dalam keadaan kosong. Ini penting dilakukan sebelum operasi Pop.

• isFull: Fungsi pengecekan untuk mengetahui apakah kapasitas stack sudah mencapai batas maksimal (hanya berlaku pada implementasi berbasis Array)

1.3 NAMA PROGRAM DAN DESKRIPSI

Nama program : Program simulasi logika operasi stack

Deskripsi : Program ini merupakan prototipe sederhana yang merepresentasikan bagaimana elemen data bergerak masuk dan keluar dalam sebuah sistem tumpukan, serta bagaimana pointer top berubah posisinya

1.4 SCREENSHOOT PROGRAM

1.5 PENJELASAN PROGRAM

#include <iostream>: Baris ini merupakan instruksi preprocessor yang berfungsi untuk menyertakan pustaka (library) standar iostream. Pustaka ini menyediakan fasilitas dasar untuk operasi input dan output dalam C++.

using namespace std;: Pernyataan ini digunakan untuk memberitahu compiler bahwa program akan menggunakan ruang nama (namespace) standar. Hal ini memungkinkan penggunaan objek seperti cout secara langsung tanpa harus menuliskan awalan std:: .

int main() { ... }: Ini adalah fungsi utama yang menjadi titik awal eksekusi program. Setiap instruksi yang berada di dalam blok kurung kurawal { } akan diproses secara berurutan oleh sistem saat program dijalankan.

cout << "..." << endl;: Perintah cout (Console Out) digunakan untuk mengirim data ke aliran output standar (layar). Operator << berfungsi sebagai perantara untuk mengarahkan teks, sedangkan endl digunakan untuk membuat baris baru.

return 0;: Pernyataan ini berfungsi untuk mengakhiri fungsi main dan mengirimkan sinyal kepada sistem operasi bahwa program telah berhasil dijalankan secara normal tanpa adanya kesalahan (exit status success).

1.6 LINK SOURCE CODE

https://drive.google.com/file/d/1jJL7pk-0COfSYLCWFZEuGApG-dyiJ9Fa/view?usp=sharing

2) IMPLEMENTASI STACK MENGGUNAKAN ARRAY

2.1 PENJELASAN MATERI

Implementasi Stack dengan Array adalah cara yang paling sederhana namun memiliki batasan fisik. Dalam metode ini, kita memesan blok memori statis di awal dengan ukuran tertentu (kapasitas maksimal).

Untuk mengelola tumpukan ini, kita menggunakan sebuah variabel penanda yang biasanya disebut top.

• Saat stack kosong, nilai top diatur ke -1 (karena indeks array dimulai dari 0).

• Setiap kali melakukan Push, nilai top akan bertambah (increment), lalu data disimpan pada indeks tersebut.

• Setiap kali melakukan Pop, data pada indeks top diambil, lalu nilai top berkurang (decrement).

Kelemahan utama metode ini adalah Fixed Size; jika tumpukan sudah mencapai kapasitas maksimal array dan kita mencoba menambah data lagi, maka akan terjadi kondisi Stack Overflow. Sebaliknya, jika kita mengambil data dari stack yang kosong, terjadi Stack Underflow.

2.2 NAMA PROGRAM DAN DESKRIPSI

Nama Program : Program Manajemen Inventori Stack Array
Deskripsi : Program ini mengimplementasikan struktur data Stack menggunakan array untuk menyimpan data integer. Program dilengkapi dengan sistem proteksi Overflow dan Underflow untuk memastikan keamanan memori saat manipulasi data dilakukan.

2.3 SCREENSHOOT PROGRAM

 

2.4 PENJELASAN PROGRAM

#include <iostream>: Baris ini merupakan instruksi preprocessor yang berfungsi untuk menyertakan pustaka (library) standar iostream. Pustaka ini menyediakan fasilitas dasar untuk operasi input dan output dalam C++.

using namespace std;: Pernyataan ini digunakan untuk memberitahu compiler bahwa program akan menggunakan ruang nama (namespace) standar agar kita bisa menggunakan cout tanpa awalan std::.

#define MAX 5: Instruksi ini mendefinisikan konstanta global bernama MAX dengan nilai 5, yang berfungsi sebagai batas kapasitas maksimal array penyimpan stack.

class Stack { ... };: Pendefinisian sebuah kelas bernama Stack yang membungkus variabel (data) dan fungsi (operasi) menjadi satu kesatuan objek.

int arr[MAX];: Deklarasi array integer dengan ukuran sebanyak nilai MAX (5) untuk menampung elemen-elemen stack secara statis.

int top;: Variabel integer yang berfungsi sebagai penunjuk indeks posisi elemen paling atas yang ada di dalam stack.

Stack() { top = -1; }: Fungsi constructor yang otomatis dijalankan saat objek dibuat untuk mengatur kondisi awal stack agar kosong (indeks -1).

void push(int x) { ... }: Fungsi untuk menambah data. Di dalamnya terdapat pengecekan if (top == MAX - 1) untuk mencegah Stack Overflow sebelum menaikkan nilai top.

arr[++top] = x;: Kode ini menaikkan nilai top terlebih dahulu (pre-increment), baru kemudian memasukkan nilai x ke dalam array pada indeks top yang baru.

void pop() { ... }: Fungsi untuk menghapus data. Terdapat pengecekan if (top == -1) untuk mencegah Stack Underflow jika user mencoba menghapus data dari tumpukan kosong.

arr[top--]: Perintah untuk mengambil nilai dari indeks top saat ini, kemudian nilai top dikurangi 1 (post-decrement) setelah data berhasil ditampilkan.

void peek() { ... }: Fungsi untuk menampilkan isi data pada indeks top tanpa mengubah atau mengurangi posisi top tersebut.

int main() { ... }: Fungsi utama sebagai titik awal eksekusi program di mana objek Stack s dideklarasikan dan diuji coba operasinya.

return 0;: Mengakhiri fungsi utama dan menandakan program telah selesai berjalan dengan sukses tanpa error.

2.5 LINK SOURCECODE

https://drive.google.com/file/d/1SpaDd8KmOFX57PXFNcB8SV3nQUoJmtbj/view?usp=sharing

3) IMPLEMENTASI STACK MENGGUNAKAN LINKED LIST

3.1 PENJELASAN MATERI

Implementasi Stack dengan Linked List mengatasi masalah utama pada Array, yaitu keterbatasan kapasitas. Dalam model ini, setiap elemen data dibungkus dalam sebuah unit yang disebut Node. Setiap Node memiliki dua bagian utama: Data (nilai yang disimpan) dan Pointer Next (alamat memori node di bawahnya).

Pada Linked List, tidak ada indeks. Sebagai gantinya, kita menggunakan pointer top yang selalu menunjuk ke node paling depan (head).

• Saat melakukan Push, kita membuat node baru di memori, mengarahkan next node baru tersebut ke top yang lama, lalu memindahkan pointer top ke node baru tersebut.

• Saat melakukan Pop, kita mengambil data dari node yang ditunjuk top, memindahkan top ke node berikutnya (top->next), lalu menghapus node lama dari memori menggunakan perintah delete.

Keunggulan utamanya adalah Dynamic Sizing; stack bisa terus bertambah selama memori RAM komputer masih tersedia. Kita tidak perlu lagi mengecek Stack Full (isFull), cukup mengecek apakah memori berhasil dialokasikan.

3.2 NAMA PROGRAM DAN DESKRIPSI

Nama Program : Program Manajemen Tumpukan Dinamis

Deskripsi : Program ini mendemonstrasikan fleksibilitas alokasi memori dinamis untuk membentuk struktur data stack. Keunggulan utamanya adalah kemampuan menampung data tanpa batas kapasitas tetap (statik), serta manajemen memori yang efisien dengan menghapus node yang tidak lagi digunakan.

3.3 SCREENSHOOT PROGRAM

3.4 PENJELASAN PROGRAM

#include <iostream>: Instruksi preprocessor untuk menyertakan pustaka standar input-output C++.

using namespace std;: Menggunakan namespace standar agar penulisan kode lebih singkat tanpa awalan std::.

struct Node { ... };: Definisi struktur data baru bernama Node yang berisi variabel data (untuk menyimpan nilai) dan pointer next (untuk menyimpan alamat node selanjutnya).

Node top;:* Deklarasi pointer bertipe Node yang berfungsi untuk melacak alamat memori dari elemen teratas stack.

top = NULL;: Di dalam constructor, top diatur ke NULL yang menandakan bahwa pada awalnya stack tidak memiliki elemen (kosong).

Node newNode = new Node();:* Perintah new digunakan untuk memesan blok memori baru secara dinamis di heap memory untuk menyimpan data baru.

newNode->next = top;: Node baru diarahkan untuk menunjuk ke node yang sebelumnya berada di posisi paling atas.

top = newNode;: Memindahkan penanda top ke alamat node yang baru saja dibuat, menjadikannya elemen teratas.

if (top == NULL): Pengecekan kondisi apakah stack kosong sebelum melakukan operasi pengambilan data agar tidak terjadi error akses memori.

Node temp = top;:* Membuat pointer sementara (temp) untuk menyimpan alamat node yang akan dihapus agar alamat tersebut tidak hilang saat top dipindahkan.

top = top->next;: Memindahkan posisi top ke node yang berada tepat di bawahnya dalam tumpukan.

delete temp;: Instruksi untuk membebaskan atau menghapus memori yang digunakan oleh node lama, mencegah terjadinya kebocoran memori (memory leak).

bool isEmpty() { return (top == NULL); }: Fungsi pendukung untuk mengecek status kekosongan stack dengan melihat apakah pointer top masih bernilai NULL.

s.push(100);: Memanggil metode push pada objek s untuk memasukkan nilai 100 ke dalam tumpukan dinamis.

return 0;: Mengirim sinyal ke sistem operasi bahwa program telah berakhir dengan sukses.

3.5 LINK SOURCE CODE

https://drive.google.com/file/d/1jgzheQ7R4QFj5-nZm42HVnqdegrVC82L/view?usp=sharing

4) APLIKASI STACK : KONVERSI INFIX KE POSTFIX

4.1 PENJELASAN MATERI

Dalam matematika sehari-hari, kita menggunakan notasi Infix (contoh: $A + B$), di mana operator berada di antara dua operand. Namun, bagi komputer, notasi Infix cukup membingungkan karena adanya aturan derajat prioritas (perkalian lebih kuat dari penjumlahan) dan penggunaan tanda kurung.

Oleh karena itu, digunakanlah notasi Postfix atau Reverse Polish Notation (contoh: A B +), di mana operator diletakkan setelah operand. Pada Postfix, komputer tidak perlu lagi mengecek tanda kurung atau prioritas; cukup baca dari kiri ke kanan.

Cara Kerja Stack dalam Konversi:

1. Jika bertemu Operand (angka/huruf), langsung masukkan ke hasil akhir.

2. Jika bertemu Operator:

   • Cek apakah stack kosong atau berisi operator dengan prioritas lebih rendah. Jika ya, Push ke stack.

   • Jika operator di dalam stack punya prioritas lebih tinggi atau sama, Pop semua yang lebih kuat itu ke hasil akhir, baru Push operator baru tadi.

3. Di akhir proses, Pop semua sisa operator yang masih ada di dalam stack ke hasil akhir.

4.2 NAMA PROGRAM DAN DESKRIPSI

Nama Program : Program Konverter Notasi Matematika (Infix to Postfix)

Deskripsi : Program ini mensimulasikan logika berpikir kalkulator atau compiler dalam menerjemahkan ekspresi matematika manusia menjadi format yang siap dieksekusi oleh mesin menggunakan bantuan struktur data Stack.

4.3 SCREENSHOOT PROGRAM

4.4 PENJELASAN PROGRAM

#include <stack>: Baris ini menyertakan pustaka standar C++ yang menyediakan fungsi-fungsi siap pakai untuk struktur data Stack (Standard Template Library).

#include <string>: Pustaka ini digunakan agar program dapat mengolah data berupa teks atau kalimat secara efisien.

int ambilPrioritas(char op) { ... }: Fungsi pembantu untuk menentukan derajat kekuatan operator. Perkalian dan pembagian diberikan nilai 2, sedangkan penjumlahan dan pengurangan diberikan nilai 1.

void konversiKePostfix(string infix) { ... }: Fungsi inti yang berisi algoritma untuk mengubah urutan karakter dari format Infix menjadi Postfix.

stack<char> s;: Deklarasi sebuah objek stack bernama s yang khusus digunakan untuk menyimpan karakter (operator).

for (int i = 0; i < infix.length(); i++): Perulangan yang berfungsi memindai setiap karakter dalam kalimat matematika dari karakter pertama hingga terakhir

if (isalnum(c)): Fungsi untuk mengecek apakah karakter c adalah alphanumeric (huruf atau angka). Jika benar, maka ia dianggap operand dan langsung digabungkan ke variabel postfix.

while (!s.empty() && ...): Logika pengecekan tumpukan. Jika operator di puncak stack lebih kuat atau sama kuat dengan operator yang baru datang, maka operator lama harus keluar (pop) dan pindah ke hasil akhir.

s.push(c);: Setelah operator yang lebih kuat disingkirkan, operator baru yang sedang diproses dimasukkan ke dalam stack.

while (!s.empty()) { postfix += s.top(); s.pop(); }: Langkah terakhir untuk membersihkan stack. Semua operator yang masih tersisa di dalam tumpukan dipindahkan ke bagian akhir hasil postfix.

konversiKePostfix(rumus);: Memanggil fungsi konversi dengan parameter teks "A+B*C" untuk diuji coba hasilnya.

return 0;: Mengakhiri program dan mengembalikan status sukses ke sistem operasi.

4.5 LINK SOURCE CODE

https://drive.google.com/file/d/1PDg20WtjE_huBMLMn8PhmssPYZlLpXyg/view?usp=sharing

-----------------------------------------------------------------------------------------------------------------------

Itu dia implementasi kodingan saya untuk tugas kali ini. Saya sadar ini masih jauh dari sempurna, jadi mohon koreksinya jika ada kesalahan. 

Let’s discuss in the comments if you have any thoughts. 

                                                                                                                                     Thankyou, ciao!