Definisi
Stack adalah struktur data linear yang menyimpan kumpulan elemen, di mana proses:
- penambahan (insertion / push)
- penghapusan (deletion / pop)
hanya dapat dilakukan pada satu sisi yang disebut top (puncak stack).
Prinsip Stack
Stack menggunakan prinsip:
👉 LIFO (Last In, First Out)
Artinya:
- Elemen yang terakhir dimasukkan akan menjadi yang pertama dikeluarkan
Analogi Sederhana
Seperti tumpukan piring:
- Piring terakhir yang diletakkan di atas → diambil pertama
- Tidak bisa mengambil dari tengah
Operasi Dasar Stack
- Push → menambahkan elemen ke stack
- Pop → menghapus elemen dari stack
- Peek/Top → melihat elemen paling atas
- isEmpty → mengecek apakah stack kosong
- isFull → mengecek apakah stack penuh (untuk array)
Contoh Implementasi Stack dalam C++ (Menggunakan Array)
#include <iostream>
using namespace std;
#define MAX 5
class Stack {
private:
int arr[MAX];
int top;
public:
Stack() {
top = -1; // stack kosong
}
// Push
void push(int x) {
if (top == MAX - 1) {
cout << "Stack Overflow\n";
} else {
arr[++top] = x;
cout << x << " ditambahkan ke stack\n";
}
}
// Pop
void pop() {
if (top == -1) {
cout << "Stack Underflow\n";
} else {
cout << arr[top--] << " dihapus dari stack\n";
}
}
// Peek
void peek() {
if (top == -1) {
cout << "Stack kosong\n";
} else {
cout << "Elemen teratas: " << arr[top] << endl;
}
}
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
s.peek();
s.pop();
s.peek();
return 0;
}
Stack dengan Link List
Pada implementasi ini:
- Stack direpresentasikan sebagai Linked List
- Setiap elemen disebut node
-
Setiap node memiliki:
- data
- pointer ke node berikutnya
👉 Top stack = node paling depan (head)
Operasi pada Stack (Linked List)
- Push → menambah node di depan
- Pop → menghapus node di depan
- Peek → melihat data paling atas
- isEmpty → cek apakah stack kosong
Implementasi C++
#include <iostream>
using namespace std;
// Struktur Node
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top;
public:
// Constructor
Stack() {
top = NULL;
}
// Push (tambah data)
void push(int x) {
Node* newNode = new Node();
newNode->data = x;
newNode->next = top;
top = newNode;
cout << x << " ditambahkan ke stack\n";
}
// Pop (hapus data)
void pop() {
if (top == NULL) {
cout << "Stack Underflow\n";
return;
}
Node* temp = top;
cout << temp->data << " dihapus dari stack\n";
top = top->next;
delete temp;
}
// Peek (lihat data teratas)
void peek() {
if (top == NULL) {
cout << "Stack kosong\n";
} else {
cout << "Elemen teratas: " << top->data << endl;
}
}
// Cek kosong
bool isEmpty() {
return (top == NULL);
}
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
s.peek();
s.pop();
s.peek();
return 0;
}
Penjelasan
-
Push
- Buat node baru
-
Arahkan
nextke top lama -
Update
top
-
Pop
- Simpan node top
- Geser top ke node berikutnya
- Hapus node lama
Kelebihan Stack dengan Linked List
✅ Tidak memiliki batas ukuran (dinamis)
✅ Tidak terjadi overflow seperti array (selama memori tersedia)
Application of Stack: Expression Conversion
Stack sangat banyak digunakan dalam manipulasi ekspresi matematika, khususnya untuk mengubah bentuk ekspresi agar mudah dievaluasi oleh komputer.
Jenis Notasi Ekspresi
Sebelum masuk ke konversi, pahami dulu 3 jenis notasi:
-
Infix → operator di tengah
Contoh:A + B -
Postfix (Reverse Polish Notation) → operator di belakang
Contoh:A B + -
Prefix (Polish Notation) → operator di depan
Contoh:+ A B
Mengapa Perlu Konversi?
- Komputer lebih mudah memproses postfix/prefix
- Tidak perlu tanda kurung
- Tidak ambigu (tidak perlu aturan prioritas)
Infix → Postfix
Contoh
Infix : A + B * C
Postfix : A B C * +
Algoritma (Menggunakan Stack)
- Scan dari kiri ke kanan
- Jika operand → langsung output
- Jika operator → bandingkan prioritas dengan stack
- Gunakan stack untuk menyimpan operator
- Keluarkan operator sesuai prioritas
Intinya
- Stack digunakan untuk menyimpan operator sementara
No comments:
Post a Comment