Stack (Tumpukan)
Terakhir diperbarui
Stack adalah koleksi yang hanya punya satu ujung terbuka. Kamu menambahkan nilai dengan push ke bagian atas, dan mengambil nilai dengan pop dari bagian atas itu juga, jadi nilai yang terakhir masuk selalu menjadi yang pertama keluar. Itulah arti LIFO, dan hanya itu aturannya: tidak ada cara untuk menjangkau bagian tengah tanpa mengambil dulu apa yang ada di atasnya. Tekan Putar di atas dan lihat kolomnya bertambah tinggi di setiap push lalu menyusut dari ujung yang sama di setiap pop.
Batasan itulah intinya. Karena kedua operasi hanya menyentuh bagian atas, masing-masing bernilai O(1) setinggi apa pun stack-nya, dan kepastian itu menjadi alasan stack ada di balik begitu banyak hal dalam komputasi: call stack yang menjalankan rekursi, riwayat undo di editor, pencocokan kurung di parser, dan stack eksplisit yang mengubah depth-first search rekursif menjadi loop. Tukar ujung pengambilannya, dan kamu mendapatkan queue.
Kompleksitas waktu dan ruang
Untuk stack standar yang berbasis array atau linked list:
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Push | O(1) | O(1) teramortisasi pada dynamic array, yang sesekali melakukan resize. |
| Pop | O(1) | Selalu elemen teratas, jadi tidak perlu ada pergeseran. |
| Peek (atas) | O(1) | Baca nilai teratas tanpa mengambilnya. |
| Pencarian | O(n) | Bukan kegunaan stack: kamu harus melakukan pop terus sampai ke bawah. |
| Ruang | O(n) | Satu slot per nilai yang disimpan. |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Stack dimulai dalam keadaan kosong, dengan bagian atas tidak menunjuk ke apa pun. |
| 2 | Push menulis nilai di posisi teratas lalu menaikkan posisi atas satu langkah. |
| 3 | Setiap push berikutnya masuk tepat di atas nilai sebelumnya. |
| 4 | Pop membaca nilai di posisi teratas, lalu menurunkan posisi atas satu langkah. |
| 5 | Nilai yang dikembalikan selalu nilai yang paling baru di-push. |
| 6 | Melakukan pop pada stack kosong adalah error, yang disebut stack underflow, jadi kode sungguhan memeriksa is_empty() terlebih dahulu. |
Contoh penerapan
Melakukan push 3, 7, 5, lalu mengosongkan stack:
| Operasi | Stack (bawah ke atas) | Mengembalikan |
|---|---|---|
push(3) | [3] | tidak ada |
push(7) | [3, 7] | tidak ada |
push(5) | [3, 7, 5] | tidak ada |
pop() | [3, 7] | 5, nilai paling baru |
pop() | [3] | 7 |
pop() | [] | 3, nilai paling lama, terakhir |
Kapan memakai stack
| Pakai saat | Hindari saat |
|---|---|
| Kamu butuh item terbaru kembali lebih dulu: undo, tombol kembali, pencocokan kurung | Kamu butuh item terlama lebih dulu, dan itu adalah queue |
| Kamu sedang mengubah algoritma rekursif menjadi iteratif | Kamu perlu mencari atau mengakses lewat indeks ke bagian tengah data |
| Kamu sedang mem-parsing struktur bersarang seperti ekspresi, JSON, atau HTML | Banyak pembaca butuh akses sembarang, dan untuk itu array atau map lebih cocok |
Kamu ingin penyisipan dan pengambilan O(1) yang terjamin tanpa penyeimbangan ulang | Kamu butuh data yang tetap terurut, yang bisa diberikan oleh heap atau pohon |
Kode Stack
Implementasi Stack yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Stack dalam Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Kode Stack dalam JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Kode Stack dalam Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Kode Stack dalam C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Kode Stack dalam C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}FAQ Stack
Apa arti LIFO?
Last in, first out (terakhir masuk, pertama keluar): nilai yang paling baru di-push adalah yang pertama di-pop. Tumpukan piring adalah gambaran yang biasa dipakai: kamu mengambil piring yang baru saja kamu letakkan, bukan yang paling bawah. Queue memakai aturan kebalikannya, yaitu FIFO.
Apa perbedaan stack dan queue?
Hanya ujung tempat pengambilannya. Keduanya menambahkan di satu ujung dalam
O(1); stack mengambil dari ujung yang sama (LIFO), sedangkan queue mengambil dari ujung lainnya (FIFO). Selebihnya, termasuk tabel kompleksitas di atas, sama persis.Apa saja operasi utama stack?
push menambahkan nilai di atas, pop mengambil dan mengembalikan nilai teratas, peek (kadang top) membaca nilai teratas tanpa mengambilnya, dan is_empty memberi tahu apakah masih ada isinya. Keempatnya bernilai O(1).Apa itu stack overflow?
Melakukan push ke stack yang sudah tidak punya ruang. Kasus yang terkenal adalah call stack: setiap pemanggilan fungsi melakukan push sebuah frame, jadi rekursi yang tidak pernah mencapai base case-nya terus melakukan push sampai batas stack runtime tercapai dan program crash. Error kebalikannya, melakukan pop pada stack kosong, disebut stack underflow.
Bagaimana stack diimplementasikan?
Ada dua cara yang umum. Dynamic array melakukan push dan pop di akhir array, yang bernilai
O(1) teramortisasi dan ramah cache: list di Python dan ArrayDeque di Java bekerja dengan cara ini. Linked list melakukan push dan pop di head, yang bernilai O(1) pada kasus terburuk tanpa resize, tetapi berbiaya satu pointer per elemen. std::stack di C++ adalah adaptor yang secara bawaan berjalan di atas std::deque, sebuah array tersegmentasi, dan menerima container lain jika kamu memberikannya.Di mana stack dipakai dalam program nyata?
Call stack untuk pemanggilan fungsi dan rekursi, riwayat undo dan redo, navigasi kembali di browser, evaluasi ekspresi dan pencocokan kurung di parser, serta stack eksplisit yang mengubah depth-first search rekursif menjadi loop iteratif.
Sumber terkait
Visualisasi lainnya
