📚 Stack

Struktur Data dan Algoritma

Pertemuan 05

Universitas Pertahanan RI

🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Menjelaskan konsep LIFO dan karakteristik stack
Mengimplementasikan stack dengan array dan linked list
Menganalisis kompleksitas setiap operasi stack
Menerapkan stack untuk balanced parentheses
Menerapkan stack untuk konversi dan evaluasi ekspresi

📋 Agenda

Konsep Dasar Stack (LIFO)
ADT Stack dan Operasi
Implementasi dengan Array
Implementasi dengan Linked List
Aplikasi: Balanced Parentheses
Aplikasi: Konversi & Evaluasi Ekspresi

📖 Apa itu Stack?

Stack adalah struktur data linear yang mengikuti prinsip LIFO (Last-In-First-Out) — elemen yang terakhir dimasukkan akan menjadi elemen pertama yang dikeluarkan.

🍽️ Bayangkan setumpuk piring di dapur — piring terakhir yang diletakkan di atas akan menjadi piring pertama yang diambil.

📖 Ilustrasi Konsep LIFO

TOP ↑

Last In = First Out

PUSH: Tambah di TOP
POP: Hapus dari TOP
Elemen E masuk terakhir
Elemen E keluar pertama

Placeholder: images/p05-01-ilustrasi-konsep-lifo.png

📊 Analogi Dunia Nyata

Analogi	Penjelasan
🍽️ Tumpukan piring	Piring teratas diambil pertama
📚 Tumpukan buku	Buku di atas diambil lebih dulu
↩️ Undo di editor	Aksi terakhir di-undo pertama
🔙 Browser back	Halaman terakhir dikunjungi kembali
📞 Call stack	Fungsi terakhir selesai pertama

🎖️ Konteks Militer

Dalam operasi militer, konsep stack sangat relevan:

Sistem komando darurat: Perintah terakhir prioritas tertinggi untuk dibatalkan
Log radar: Data terbaru perlu diakses cepat untuk analisis situasi
Waypoint UAV: Pilot dapat membatalkan waypoint terakhir

📖 ADT Stack

ADT Stack mendefinisikan stack sebagai kumpulan elemen dengan operasi yang terbatas pada satu ujung yang disebut TOP.

📊 Operasi Dasar Stack

Operasi	Deskripsi	Return
`push(x)`	Menambahkan x ke top	void
`pop()`	Menghapus & mengembalikan top	elemen
`peek()`	Mengembalikan top tanpa hapus	elemen
`isEmpty()`	Cek apakah kosong	boolean
`isFull()`	Cek apakah penuh (array)	boolean

📖 Visualisasi Push & Pop

PUSH(40)

↑ Tambah di TOP

POP()

↑ Hapus dari TOP, return 40

Placeholder: images/p05-02-push-pop-operations.png

🧠 Quiz: Trace Operasi Stack

Stack kosong S. Apa hasil setelah operasi berikut?


push(5), push(10), push(15), pop(), push(20), pop(), pop()

Jawaban:

Stack akhir: [5]

Return values: 15, 20, 10

📊 Trace Langkah per Langkah

Step	Operasi	Stack	Return
1	push(5)	[5]	-
2	push(10)	[5, 10]	-
3	push(15)	[5, 10, 15]	-
4	pop()	[5, 10]	15
5	push(20)	[5, 10, 20]	-
6	pop()	[5, 10]	20
7	pop()	[5]	10

💻 Implementasi Stack dengan Array

Menggunakan array dengan ukuran tetap (fixed size)

topIndex = -1 menandakan stack kosong
Push: ++topIndex, lalu simpan data
Pop: Ambil data, lalu --topIndex

Placeholder: images/p05-03-array-memory-layout.png

💻 Class StackArray - Struktur


class StackArray {
private:
    static const int MAX_SIZE = 100;
    int data[MAX_SIZE];
    int topIndex;  // -1 jika kosong
    
public:
    StackArray() : topIndex(-1) {}
    
    bool isEmpty() { return topIndex == -1; }
    bool isFull()  { return topIndex == MAX_SIZE - 1; }
};

💻 Operasi Push


void push(int value) {
    if (isFull()) {
        cout << "Error: Stack Overflow!" << endl;
        return;
    }
    data[++topIndex] = value;
}

⚠️ Stack Overflow: Terjadi ketika push ke stack yang sudah penuh

💻 Operasi Pop & Peek


int pop() {
    if (isEmpty()) {
        cout << "Error: Stack Underflow!" << endl;
        return -1;
    }
    return data[topIndex--];
}

int peek() {
    if (isEmpty()) {
        cout << "Error: Stack kosong!" << endl;
        return -1;
    }
    return data[topIndex];
}

📊 Kompleksitas Array Stack

Operasi	Time	Space
push()	O(1)	O(1)
pop()	O(1)	O(1)
peek()	O(1)	O(1)
isEmpty()	O(1)	O(1)

Total Space: O(n) untuk n elemen maksimum

📊 Kelebihan & Kekurangan Array

✅ Kelebihan

Implementasi sederhana
Akses O(1) ke top
Cache-friendly

❌ Kekurangan

Ukuran tetap
Waste memory
Stack overflow

💡 Dynamic Array Stack

Doubling Strategy: Kapasitas dilipatgandakan saat penuh


void resize() {
    int newCapacity = capacity * 2;
    int* newData = new int[newCapacity];
    for (int i = 0; i <= topIndex; i++)
        newData[i] = data[i];
    delete[] data;
    data = newData;
    capacity = newCapacity;
}

Amortized push: O(1)

💻 Implementasi Stack dengan Linked List

Operasi push dan pop dilakukan di head (bukan tail) untuk kompleksitas O(1)

Placeholder: images/p05-04-linked-list-stack.png

💻 Struktur Node


struct Node {
    int data;
    Node* next;
    
    Node(int value) : data(value), next(nullptr) {}
};

Visualisasi: topNode → [40] → [30] → [20] → [10] → NULL

💻 Operasi Push (Linked List)


void push(int value) {
    Node* newNode = new Node(value);
    newNode->next = topNode;  // Arahkan ke top lama
    topNode = newNode;        // Update top
    count++;
}

✅ Kompleksitas: O(1) - selalu di head

💻 Operasi Pop (Linked List)


int pop() {
    if (isEmpty()) {
        cout << "Stack Underflow!" << endl;
        return -1;
    }
    
    Node* temp = topNode;
    int value = temp->data;
    topNode = topNode->next;  // Update top
    delete temp;              // Hapus node lama
    count--;
    return value;
}

🧠 Quiz: Mengapa di Head?

Mengapa operasi stack di linked list dilakukan di HEAD, bukan TAIL?

Jawaban:

Pop di TAIL membutuhkan O(n) karena harus traverse untuk menemukan node sebelum tail.

Pop di HEAD: O(1) - akses langsung!

Placeholder: images/p05-09-pop-tail-on-complexity.png

📊 Kelebihan & Kekurangan Linked List

✅ Kelebihan

Ukuran fleksibel
Tidak ada waste memory
Tidak perlu resize

❌ Kekurangan

Overhead pointer
Tidak cache-friendly
Alokasi per operasi

📊 Perbandingan Array vs Linked List

Aspek	Array Static	Array Dynamic	Linked List
Ukuran	Tetap	Fleksibel	Fleksibel
Push	O(1)	O(1)*	O(1)
Pop	O(1)	O(1)	O(1)
Cache	Friendly	Friendly	Tidak
Overflow	Mungkin	Tidak	Tidak

* amortized

📖 Aplikasi: Balanced Parentheses

Memeriksa apakah tanda kurung () [] {} dalam string sudah seimbang.

✓ Balanced: "([]){}", "{[()]}"

✗ Not Balanced: "([)]", "((("

📖 Algoritma Balanced Parentheses

Untuk setiap karakter:
Jika kurung buka → PUSH
Jika kurung tutup → POP & CHECK
Di akhir: stack harus kosong

💻 Implementasi isBalanced()


bool isBalanced(string expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{')
            s.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;
            char top = s.top();
            s.pop();
            if (!isMatchingPair(top, c))
                return false;
        }
    }
    return s.empty();
}

📊 Trace: "{[()]}"

Step	Char	Action	Stack
1	{	PUSH	{
2	[	PUSH	{[
3	(	PUSH	{[(
4	)	POP ✓	{[
5	]	POP ✓	{
6	}	POP ✓	empty

Hasil: BALANCED ✓

Placeholder: images/p05-05-balanced-parentheses-trace.png

🧠 Quiz: Trace "[(])"

Trace algoritma untuk string: "[(])"

Char	Action	Stack
[	PUSH	[
(	PUSH	[(
]	POP (	[

( tidak match dengan ] → NOT BALANCED ✗

📖 Notasi Ekspresi

Notasi	Format	Contoh
Infix	operand op operand	`A + B`
Prefix	op operand operand	`+ A B`
Postfix	operand operand op	`A B +`

💡 Mengapa Postfix?

✅ Tidak memerlukan tanda kurung
✅ Tidak perlu aturan prioritas saat evaluasi
✅ Mudah dievaluasi dengan stack
✅ Digunakan di kalkulator dan compiler

📊 Prioritas Operator

Operator	Prioritas	Associativity
`^`	3 (tertinggi)	Right to Left
`* /`	2	Left to Right
`+ -`	1 (terendah)	Left to Right

📖 Algoritma Infix ke Postfix

Shunting-Yard Algorithm:

Operand → langsung ke output
( → push ke stack
) → pop sampai (
Operator → pop operator dengan prioritas ≥, lalu push
Akhir → pop semua sisa operator

📊 Trace: "(A+B)*C"

Token	Action	Stack	Output
(	PUSH	(
A	Output	(	A
+	PUSH	(+	A
B	Output	(+	AB
)	POP sampai (		AB+
*	PUSH	*	AB+
C	Output	*	AB+C
END	POP all		AB+C*

Placeholder: images/p05-06-infix-to-postfix.png

📖 Evaluasi Ekspresi Postfix

Algoritma:

Operand → PUSH ke stack
Operator → POP dua operand, hitung, PUSH hasil
Akhir → nilai di top adalah hasil

💻 Implementasi evaluatePostfix()


int evaluatePostfix(string postfix) {
    stack<int> operandStack;
    for (char token : postfix) {
        if (isdigit(token))
            operandStack.push(token - '0');
        else {
            int op2 = operandStack.top(); operandStack.pop();
            int op1 = operandStack.top(); operandStack.pop();
            int result;
            switch (token) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/': result = op1 / op2; break;
            }
            operandStack.push(result);
        }
    }
    return operandStack.top();
}

📊 Trace: "23*5+"

Token	Action	Stack	Calc
2	PUSH	[2]	-
3	PUSH	[2, 3]	-
*	POP, calc, PUSH	[6]	2*3=6
5	PUSH	[6, 5]	-
+	POP, calc, PUSH	[11]	6+5=11

Hasil: 11

Placeholder: images/p05-07-postfix-evaluation-trace.png

🧠 Quiz: Evaluasi "53+2*4-"

Hitung nilai ekspresi postfix: "53+2*4-"

5+3 = 8 → 8*2 = 16 → 16-4 = 12

Infix: (5+3)*2-4 = 12 ✓

📖 Function Call Stack

Setiap fungsi dipanggil → stack frame di-push

Fungsi selesai → stack frame di-pop

Parameter fungsi
Variabel lokal
Return address

💻 Contoh: factorial(4)


int factorial(int n) {
    if (n <= 1) return 1;       // Base case
    return n * factorial(n-1);  // Recursive
}

Placeholder: images/p05-08-function-call-stack.png

📊 Call Stack factorial(4)

PUSH Phase

fact(1)

fact(2)

fact(3)

fact(4)

main()

POP Phase

fact(1) → return 1
fact(2) → 2*1 = 2
fact(3) → 3*2 = 6
fact(4) → 4*6 = 24

Placeholder: images/p05-10-factorial-call-stack-trace.png

📝 Ringkasan

Konsep	Poin Penting
LIFO	Last-In-First-Out
Operasi	push(), pop(), peek(), isEmpty()
Array	O(1) semua operasi, ukuran tetap/dinamis
Linked List	O(1) semua operasi, ukuran fleksibel
Balanced ()	Push buka, pop & match tutup
Postfix	Push operand, pop-calc-push operator

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.10.1 | Weiss Ch.3.6 | Hubbard Ch.5

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 05: Stack