Tumpukan (struktur data) 📖 Wikipedia

Dalam ilmu komputer, tumpukan (bahasa Inggris: stackcode: en is deprecated ) adalah struktur data linear yang mengikuti prinsip LIFO (Last In, First Out), yang berarti elemen yang terakhir dimasukkan akan menjadi elemen pertama yang dikeluarkan. Konsep ini dapat diibaratkan seperti tumpukan piring di sebuah kafetaria: piring terakhir yang diletakkan di atas tumpukan adalah piring pertama yang akan diambil untuk digunakan.^[1]

Sebagai tipe data abstrak, tumpukan membatasi akses datanya hanya pada satu ujung struktur, yang biasa disebut sebagai puncak (top). Tumpukan tidak mengizinkan akses acak (random access) ke elemen yang berada di tengah atau di dasar tumpukan. Untuk menjangkau elemen di bawah puncak, seluruh elemen di atasnya harus dikeluarkan terlebih dahulu.^[2]

Sebuah tumpukan umumnya mendukung dua operasi utama dan beberapa operasi pendukung untuk mengelola data di dalamnya:

• Push (dorong/masukkan): Menambahkan sebuah elemen ke puncak tumpukan. Jika tumpukan telah mencapai kapasitas maksimalnya (pada implementasi berukuran tetap), operasi ini tidak dapat dilakukan dan memicu kondisi galat yang disebut overflow.
• Pop (keluarkan/ambil): Menghapus dan mengembalikan elemen yang berada di puncak tumpukan. Jika operasi ini dipanggil saat tumpukan kosong, sistem akan memicu kondisi galat yang disebut underflow.
• Peek atau Top (intip): Mengembalikan nilai dari elemen yang berada di puncak tumpukan tanpa menghapus elemen tersebut dari struktur.
• IsEmpty (apakah kosong): Memeriksa apakah tumpukan dalam keadaan kosong.
• IsFull (apakah penuh): Memeriksa apakah tumpukan telah penuh (biasanya hanya berlaku pada implementasi berkapasitas statis).

Tumpukan dapat diimplementasikan dalam perangkat lunak melalui dua struktur data dasar:

Implementasi dengan larik (array) menyimpan elemen tumpukan dalam blok memori yang berdampingan secara fisik. Pendekatan ini sangat efisien dalam penggunaan memori (karena tidak memerlukan ruang tambahan untuk menyimpan rujukan atau pointer) dan sangat cepat secara komputasi berkat lokalitas rujukan (locality of reference). Namun, ukuran maksimal tumpukan biasanya harus ditentukan di awal (statis), dan jika larik penuh, memperbesar ukurannya memakan biaya komputasi yang besar.

Implementasi dengan senarai berantai (linked list) menyimpan setiap elemen sebagai simpul (node) yang tersebar di memori, di mana setiap simpul memiliki rujukan ke simpul di bawahnya. Pendekatan ini memungkinkan ukuran tumpukan bertambah atau berkurang secara dinamis tanpa batas ukuran kaku, namun memerlukan alokasi memori tambahan untuk menyimpan struktur rujukan tersebut.

Pada implementasi yang baik (baik menggunakan larik maupun senarai berantai), operasi-operasi dasar pada tumpukan sangat cepat karena tidak memerlukan perulangan atau pergeseran elemen lain.^[1]

Operasi	Kompleksitas waktu
Push	${\displaystyle O(1)}$
Pop	${\displaystyle O(1)}$
Peek / Top	${\displaystyle O(1)}$
IsEmpty	${\displaystyle O(1)}$

• (Catatan: Pada larik dinamis, operasi push terkadang memakan waktu ${\displaystyle O(n)}$ jika larik harus diperbesar, tetapi secara rata-rata teramortisasi tetap memakan waktu ${\displaystyle O(1)}$).*

Tumpukan merupakan salah satu struktur data yang paling fundamental dan sering diaplikasikan dalam beraneka ragam sistem komputasi:

Kalkulator yang menggunakan notasi Polandia terbalik (Reverse Polish Notation atau RPN, di mana operator diletakkan secara posfiks) menggunakan tumpukan untuk menyimpan dan menghitung nilai secara efisien tanpa memerlukan tanda kurung. Selain itu, hampir semua kompilator menggunakan tumpukan untuk mengevaluasi ekspresi matematika, memvalidasi pasangan tanda kurung, dan menguraikan (parsing) sintaks blok program sebelum diterjemahkan ke bahasa tingkat rendah.

Tumpukan sangat berguna untuk menyelesaikan algoritme pencarian berbasis runut balik (backtracking). Misalnya, dalam penyelesaian sebuah labirin (maze), kita dapat menyimpan setiap percabangan jalan yang kita lewati menggunakan tumpukan. Apabila kita mencapai jalan buntu, kita dapat memanggil operasi pop untuk mundur ke persimpangan terakhir dan mencoba rute alternatif. Contoh penerapan algoritme ini yang paling terkenal adalah penelusuran graf dan pohon menggunakan metode pencarian mendalam (Depth-First Search atau DFS).

Sistem operasi dan mesin virtual menggunakan struktur tumpukan panggilan (call stack) untuk mengelola eksekusi fungsi atau prosedur. Ketika sebuah fungsi dipanggil, variabel lokal dan alamat kembalinya (return address) didorong (push) ke dalam tumpukan panggilan. Ketika fungsi tersebut selesai dikerjakan, sistem menarik (pop) memori tersebut untuk kembali ke baris kode asal yang memanggilnya. Prinsip inilah yang memungkinkan berjalannya algoritme rekursif.

Fitur "Batal" dan "Ulangi" (Undo / Redo) pada aplikasi penyunting teks maupun perangkat lunak desain diimplementasikan menggunakan dua buah tumpukan. Setiap kali pengguna melakukan aksi baru, aksi tersebut didorong ke tumpukan Undo. Saat pengguna menekan Undo, aksi tersebut diambil dari tumpukan Undo, dibatalkan efeknya, lalu didorong ke tumpukan Redo. Prinsip serupa digunakan pada fitur tombol "Kembali" (Back) dan "Maju" (Forward) pada peramban web.

• Struktur data
• Antrean (struktur data)
• Larik
• Senarai berantai

• (Inggris) stack dalam Dictionary of Algorithms and Data Structures NIST