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
next ke 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
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
Referensi
