Tumpukan (tipe data abstrak)

Dalam ilmu komputer , tumpukan adalah tipe data abstrak yang berfungsi sebagai kumpulan
elemen dengan dua operasi utama:

Dorong , yang menambahkan elemen ke koleksi, dan

Pop , yang menghapus elemen yang baru saja ditambahkan.

Mirip dengan tumpukan piring,

menambah atau mengurangi hanya
dapat dilakukan di bagian atas.

Representasi sederhana dari runtime tumpukan dengan

operasi push dan pop .

Selain itu, operasi peek dapat, tanpa mengubah tumpukan, mengembalikan nilai elemen terakhir
yang ditambahkan. Nama tumpukan adalah analogi untuk sekumpulan item fisik yang ditumpuk
satu di atas yang lain, seperti tumpukan piring.

Urutan penambahan atau pengurangan elemen dari tumpukan dijelaskan sebagai last in, first
out (terakhir masuk, pertama keluar ), yang disebut dengan akronim LIFO . [ nb 1 ] Seperti halnya
tumpukan objek fisik, struktur ini memudahkan untuk mengambil item dari atas tumpukan, tetapi
mengakses data yang lebih dalam di dalam tumpukan mungkin memerlukan pengurangan
beberapa item lainnya terlebih dahulu. [ 1 ]

Dianggap sebagai koleksi berurutan, tumpukan memiliki satu ujung yang merupakan satu-
satunya posisi di mana operasi push dan pop dapat terjadi, bagian atas tumpukan, dan tetap di
ujung lainnya, bagian bawah . Tumpukan dapat diimplementasikan sebagai, misalnya, daftar
tertaut tunggal dengan penunjuk ke elemen teratas.

Tumpukan dapat diimplementasikan agar memiliki kapasitas terbatas. Jika tumpukan penuh dan
tidak berisi cukup ruang untuk menerima elemen lain, tumpukan berada dalam kondisi stack
overflow .

Sejarah

Stack memasuki literatur ilmu komputer pada tahun 1946, ketika Alan Turing menggunakan
istilah "bury" dan "unbury" sebagai sarana memanggil dan kembali dari subrutin. [ 2 ] [ 3 ] Subrutin
dan stack dua tingkat telah diimplementasikan di Z4 Konrad Zuse pada tahun 1945. [ 4 ] [ 5 ]

Klaus Samelson dan Friedrich L. Bauer dari Universitas Teknik Munich mengusulkan ide
tumpukan yang disebut Operationskeller ("gudang bawah tanah operasional") pada tahun 1955
[6][7]
dan mengajukan paten pada tahun 1957. [ 8 ] [ 9 ] [ 10 ] [ 11 ] Pada bulan Maret 1988, saat
Samelson meninggal, Bauer menerima Penghargaan Pelopor Komputer IEEE untuk penemuan
prinsip tumpukan. [ 12 ] [ 7 ] Konsep serupa dikembangkan secara independen oleh Charles
Leonard Hamblin pada paruh pertama tahun 1954 [ 13 ] [ 7 ] dan oleh Wilhelm Kämmerer dengan
automatisches Gedächtnis ("memori otomatis") pada tahun 1958. [ 14 ] [ 15 ] [ 7 ]

Tumpukan sering digambarkan menggunakan analogi tumpukan piring berpegas di kafetaria.

[ 16 ] [ 1 ] [ 17 ]
Piring bersih diletakkan di atas tumpukan, mendorong piring yang sudah ada di sana.
Ketika piring paling atas dikeluarkan dari tumpukan, piring di bawahnya diangkat untuk menjadi
piring paling atas yang baru.

Operasi yang tidak penting

Dalam banyak implementasi, tumpukan memiliki lebih banyak operasi daripada operasi "push"
dan "pop" yang penting. Contoh operasi yang tidak penting adalah "top of stack", atau "peek",
yang mengamati elemen teratas tanpa mengeluarkannya dari tumpukan. [ 18 ] Karena ini dapat
dipecah menjadi "pop" diikuti oleh "push" untuk mengembalikan data yang sama ke tumpukan, ini
tidak dianggap sebagai operasi penting. Jika tumpukan kosong, kondisi underflow akan terjadi
saat eksekusi operasi "stack top" atau "pop". Selain itu, banyak implementasi menyediakan
pemeriksaan jika tumpukan kosong dan operasi yang mengembalikan ukurannya.
Tumpukan perangkat lunak

Pelaksanaan

Tumpukan dapat dengan mudah diimplementasikan baik melalui array atau linked list , karena
tumpukan hanyalah kasus khusus dari sebuah list. [ 19 ] Dalam kedua kasus tersebut, yang
mengidentifikasi struktur data sebagai tumpukan bukanlah implementasinya tetapi
antarmukanya: pengguna hanya diperbolehkan untuk memunculkan atau mendorong item ke
dalam array atau linked list, dengan beberapa operasi pembantu lainnya. Berikut ini akan
menunjukkan kedua implementasi tersebut menggunakan pseudocode .

Susunan

Suatu larik dapat digunakan untuk mengimplementasikan tumpukan (terbatas), sebagai berikut.
Elemen pertama, biasanya pada offset nol , adalah bagian bawah, yang mengakibatkan
array[0] elemen pertama didorong ke dalam tumpukan dan elemen terakhir dikeluarkan.
Program harus melacak ukuran (panjang) tumpukan, menggunakan variabel top yang mencatat
jumlah item yang didorong sejauh ini, oleh karena itu menunjuk ke tempat dalam larik tempat
elemen berikutnya akan dimasukkan (dengan asumsi konvensi indeks berbasis nol). Dengan
demikian, tumpukan itu sendiri dapat diimplementasikan secara efektif sebagai struktur tiga
elemen:

tumpukan struktur :
ukuran maksimum : bilangan bulat
atas : bilangan bulat
item : susunan item

prosedur inisialisasi(stk: tumpukan, ukuran: integer):

[Link] ← array baru dengan ukuran item, awalnya kosong
[Link] ← ukuran
[Link] ← 0

Operasi push menambahkan elemen dan menaikkan indeks teratas , setelah memeriksa luapan:

prosedur push(stk: tumpukan, x: item):

jika [Link] = [Link]:
laporkan kesalahan luapan
kalau tidak :
[Link][[Link]] ← x
[Link] ← [Link] + 1
Demikian pula, pop mengurangi indeks teratas setelah memeriksa underflow, dan
mengembalikan item yang sebelumnya merupakan yang teratas:

prosedur pop(stk : tumpukan):

jika [Link] = 0:
laporkan kesalahan underflow
kalau tidak :
[Link] ← [Link] − 1
r ← [Link][[Link]]
kembali r

Dengan menggunakan array dinamis , dimungkinkan untuk mengimplementasikan tumpukan

yang dapat bertambah atau berkurang sebanyak yang dibutuhkan. Ukuran tumpukan hanyalah
ukuran array dinamis, yang merupakan implementasi tumpukan yang sangat efisien karena
menambahkan item ke atau menghapus item dari akhir array dinamis memerlukan waktu O(1)
yang diamortisasi.

Daftar tertaut

Pilihan lain untuk menerapkan tumpukan adalah dengan menggunakan daftar tertaut tunggal .
Tumpukan kemudian menjadi penunjuk ke "kepala" daftar, mungkin dengan penghitung untuk
melacak ukuran daftar:

rangka struktur :
data : barang
berikutnya : bingkai atau nol

tumpukan struktur :
kepala : bingkai atau nol
ukuran : bilangan bulat

prosedur inisialisasi(stk: tumpukan):

[Link] ← nihil
ukuran stk ← 0

Pendorongan dan pelepasan item terjadi di bagian atas daftar; luapan tidak dimungkinkan dalam
implementasi ini (kecuali memori habis):

prosedur push(stk: tumpukan, x: item):

newhead ← bingkai baru
data kepala baru ← x
 [Link] ← [Link]
[Link] ← kepala baru
[Link] ← [Link] + 1

prosedur pop(stk : tumpukan):

jika [Link] = nol:
laporkan kesalahan underflow
r ← [Link]
[Link] ← [Link]
[Link] ← [Link] - 1
kembali r

Tumpukan dan bahasa pemrograman

Beberapa bahasa, seperti Perl , LISP , JavaScript, dan Python , menyediakan operasi tumpukan
push dan pop pada tipe daftar/array standar mereka. Beberapa bahasa, terutama yang ada
dalam keluarga Forth (termasuk PostScript ), dirancang berdasarkan tumpukan yang ditentukan
bahasa yang dapat dilihat dan dimanipulasi secara langsung oleh programmer.

Berikut ini adalah contoh manipulasi tumpukan dalam Common Lisp (" > " adalah perintah
penerjemah Lisp; baris yang tidak dimulai dengan " > " adalah respons penerjemah terhadap
ekspresi):

> ( setf stack ( list 'a 'b 'c )) ;; mengatur variabel "stack" ( A
B C ) > ( pop stack ) ;; mendapatkan elemen paling atas (paling
kiri), harus memodifikasi stack A > stack ;; memeriksa nilai stack
( B C ) > ( push 'new stack ) ;; mendorong bagian atas baru ke
dalam stack ( NEW B C )

Beberapa tipe kontainer C++ Standard Library memiliki operasi push_back dan pop_back
dengan semantik LIFO; selain itu, kelas templat tumpukan mengadaptasi kontainer yang ada
untuk menyediakan API terbatas dengan hanya operasi push/pop. PHP memiliki kelas SplStack
([Link] . Pustaka Java berisi kelas yang
merupakan spesialisasi dari . Berikut ini adalah contoh program dalam bahasa Java , yang
menggunakan kelas tersebut. ([Link] Stack (h
ttps://[Link]/en/java/javase/19/docs/api/[Link]/java/util/
[Link]) Vector ([Link]
i/[Link]/java/util/[Link])

impor [Link] ;

class StackDemo { public static void main ( String [] args ) {

Stack < String > stack = new Stack < String > (); [Link] ( " A"
); // Masukkan "A" ke dalam stack [Link] ( " B " ) ; //
Masukkan "B" ke dalam stack [Link] ( " C " ) ; // Masukkan " C
" ke dalam stack [Link] ( " D" ); // Masukkan "D " ke dalam
stack [Link] ( [Link] ()); // Mencetak bagian atas
stack ("D") [Link] ( ); // menghapus bagian atas ("D") [Link]
(); // menghapus bagian atas berikutnya ("C" ) } }

Beberapa prosesor, seperti Motorola 68000 memiliki mode pengalamatan yang dirancang untuk
manipulasi tumpukan. Kode sumber assembly PDP-11 sederhana berikut ini mendorong dua
angka pada tumpukan dan menambahkannya, meninggalkan hasilnya pada tumpukan.

; R0 diasumsikan menunjuk ke area tumpukan

; -(R0) melakukan pra-pengurangan penunjuk tumpukan yang
mengalokasikan item pada tumpukan
; (R0)+ pasca-peningkatan penunjuk tumpukan yang menghapus item
pada tumpukan
;
MOV #12,-(R0) ; Mendorong 12 pada tumpukan MOV #34,-(R0) ;
mendorong 34 pada tumpukan ADD ( R0 ) + ,( R0 ) ; Mengeluarkan 34
dari tumpukan dan menambahkan ke 12 ; meninggalkan hasilnya pada
tumpukan
Tumpukan perangkat keras

Penggunaan umum tumpukan pada tingkat arsitektur adalah sebagai sarana mengalokasikan
dan mengakses memori.

Arsitektur dasar tumpukan

Tumpukan yang umum adalah area memori komputer dengan asal yang tetap dan ukuran yang
bervariasi. Awalnya ukuran tumpukan adalah nol. Penunjuk tumpukan (biasanya dalam bentuk
register prosesor ) menunjuk ke lokasi yang terakhir direferensikan pada tumpukan; ketika
tumpukan memiliki ukuran nol, penunjuk tumpukan menunjuk ke asal tumpukan.

Dua operasi yang berlaku untuk semua tumpukan adalah:

Operasi push : alamat dalam penunjuk tumpukan disesuaikan dengan ukuran item data dan
item data ditulis di lokasi yang ditunjuk oleh penunjuk tumpukan.

Operasi pop atau pull : item data pada lokasi saat ini yang ditunjuk oleh penunjuk tumpukan
dibaca, dan penunjuk tumpukan dipindahkan sejauh yang sesuai dengan ukuran item data
tersebut.

Ada banyak variasi pada prinsip dasar operasi tumpukan. Setiap tumpukan memiliki lokasi tetap
di memori tempat dimulainya. Saat item data ditambahkan ke tumpukan, penunjuk tumpukan
akan dipindahkan untuk menunjukkan luas tumpukan saat ini, yang meluas menjauh dari titik
asal.

Penunjuk tumpukan dapat menunjuk ke asal tumpukan atau ke rentang alamat terbatas di atas
atau di bawah asal (tergantung pada arah pertumbuhan tumpukan); namun, penunjuk tumpukan
tidak dapat melewati asal tumpukan. Dengan kata lain, jika asal tumpukan berada di alamat
1000 dan tumpukan tumbuh ke bawah (menuju alamat 999, 998, dan seterusnya), penunjuk
tumpukan tidak boleh bertambah lebih dari 1000 (menjadi 1001 atau lebih). Jika operasi pop
pada tumpukan menyebabkan penunjuk tumpukan bergerak melewati asal tumpukan, terjadi
underflow tumpukan . Jika operasi push menyebabkan penunjuk tumpukan bertambah atau
berkurang melebihi batas maksimum tumpukan, terjadi stack overflow .

Beberapa lingkungan yang sangat bergantung pada tumpukan mungkin menyediakan operasi
tambahan, misalnya:

Duplikat : item paling atas dikeluarkan dan kemudian didorong dua kali, sehingga dua salinan
item paling atas sebelumnya kini berada di atas.

Peek : item paling atas diperiksa (atau dikembalikan), tetapi penunjuk tumpukan dan ukuran
tumpukan tidak berubah (artinya item tetap berada di tumpukan). Ini juga dapat disebut
 operasi teratas .

Tukar atau tukar : dua item paling atas pada tumpukan tempat pertukaran.

Putar (atau Gulung) : n item teratas dipindahkan pada tumpukan dengan cara berputar.
Misalnya, jika n = 3 , item 1, 2, dan 3 pada tumpukan dipindahkan ke posisi 2, 3, dan 1 pada
tumpukan, secara berurutan. Banyak varian operasi ini yang memungkinkan, dengan yang
paling umum disebut putar kiri dan putar kanan.

Tumpukan sering kali divisualisasikan tumbuh dari bawah ke atas (seperti tumpukan di dunia
nyata). Tumpukan juga dapat divisualisasikan tumbuh dari kiri ke kanan, dengan bagian atas
berada di paling kanan, atau bahkan tumbuh dari atas ke bawah. Fitur yang penting adalah
bagian bawah tumpukan berada pada posisi tetap. Ilustrasi di bagian ini adalah contoh
visualisasi pertumbuhan dari atas ke bawah: bagian atas (28) adalah "bagian bawah" tumpukan,
karena "bagian atas" tumpukan (9) adalah tempat item didorong atau dikeluarkan.

A right rotate will move the first element to the third position, the second to the first and the third
to the second. Here are two equivalent visualizations of this process:

apple banana
banana ===right rotate==> cucumber
cucumber apple

cucumber apple
banana ===left rotate==> cucumber
apple banana

A stack is usually represented in computers by a block of memory cells, with the "bottom" at a
fixed location, and the stack pointer holding the address of the current "top" cell in the stack. The
"top" and "bottom" nomenclature is used irrespective of whether the stack actually grows
towards higher memory addresses.

Pushing an item on to the stack adjusts the stack pointer by the size of the item (either
decrementing or incrementing, depending on the direction in which the stack grows in memory),
pointing it to the next cell, and copies the new top item to the stack area. Depending again on the
exact implementation, at the end of a push operation, the stack pointer may point to the next
unused location in the stack, or it may point to the topmost item in the stack. If the stack points
to the current topmost item, the stack pointer will be updated before a new item is pushed onto
the stack; if it points to the next available location in the stack, it will be updated after the new
item is pushed onto the stack.
Popping the stack is simply the inverse of pushing. The topmost item in the stack is removed
and the stack pointer is updated, in the opposite order of that used in the push operation.

Stack in main memory

Many CISC-type CPU designs, including the x86, Z80 and 6502, have a dedicated register for use
as the call stack stack pointer with dedicated call, return, push, and pop instructions that
implicitly update the dedicated register, thus increasing code density. Some CISC processors, like
the PDP-11 and the 68000, also have special addressing modes for implementation of stacks,
typically with a semi-dedicated stack pointer as well (such as A7 in the 68000). In contrast, most
RISC CPU designs do not have dedicated stack instructions and therefore most, if not all,
registers may be used as stack pointers as needed.

Stack in registers or dedicated memory

The programmable pocket

calculator HP-42S from 1988
had, like nearly all of the
company's calculators of
that time, a 4-level-stack and
could display two of four
values of the stack registers
X, Y, Z, and T at the same
time due to its two-line
display, here X and Y. In later
models like the HP-48, the
number of levels was
increased to be only limited
by memory size.

Some machines use a stack for arithmetic and logical operations; operands are pushed onto the
stack, and arithmetic and logical operations act on the top one or more items on the stack,
popping them off the stack and pushing the result onto the stack. Machines that function in this
fashion are called stack machines.

A number of mainframes and minicomputers were stack machines, the most famous being the
Burroughs large systems. Other examples include the CISC HP 3000 machines and the CISC
machines from Tandem Computers.

The x87 floating point architecture is an example of a set of registers organised as a stack where
direct access to individual registers (relative to the current top) is also possible.

Having the top-of-stack as an implicit argument allows for a small machine code footprint with a
good usage of bus bandwidth and code caches, but it also prevents some types of optimizations
possible on processors permitting random access to the register file for all (two or three)
operands. A stack structure also makes superscalar implementations with register renaming (for
speculative execution) somewhat more complex to implement, although it is still feasible, as
exemplified by modern x87 implementations.

Sun SPARC, AMD Am29000, and Intel i960 are all examples of architectures that use register
windows within a register-stack as another strategy to avoid the use of slow main memory for
function arguments and return values.

Ada juga sejumlah mikroprosesor kecil yang mengimplementasikan tumpukan langsung dalam
perangkat keras, dan beberapa mikrokontroler memiliki tumpukan berkedalaman tetap yang
tidak dapat diakses secara langsung. Contohnya adalah mikrokontroler PIC , Computer Cowboys
MuP21 , lini Harris RTX , dan Novix NC4016 . Setidaknya satu keluarga mikrokontroler, COP400 ,
mengimplementasikan tumpukan baik secara langsung dalam perangkat keras maupun dalam
RAM melalui penunjuk tumpukan, tergantung pada perangkatnya. Banyak mikroprosesor
berbasis tumpukan digunakan untuk mengimplementasikan bahasa pemrograman Forth pada
tingkat mikrokode .

Aplikasi tumpukan

Evaluasi ekspresi dan penguraian sintaksis

Kalkulator yang menggunakan notasi Polandia terbalik menggunakan struktur tumpukan untuk
menyimpan nilai. Ekspresi dapat direpresentasikan dalam notasi awalan, akhiran, atau sisipan
dan konversi dari satu bentuk ke bentuk lain dapat dilakukan menggunakan tumpukan. Banyak
kompiler menggunakan tumpukan untuk mengurai sintaksis sebelum diterjemahkan ke kode
tingkat rendah. Sebagian besar bahasa pemrograman adalah bahasa bebas konteks , yang
memungkinkannya diurai dengan mesin berbasis tumpukan.
Melacak kembali

Aplikasi penting lain dari tumpukan adalah backtracking . Ilustrasinya adalah contoh sederhana
menemukan jalur yang benar dalam labirin yang berisi serangkaian titik, titik awal, beberapa jalur,
dan tujuan. Jika jalur acak harus dipilih, maka setelah mengikuti jalur yang salah, harus ada
metode untuk kembali ke awal jalur tersebut. Ini dapat dicapai melalui penggunaan tumpukan,
karena titik terakhir yang benar dapat didorong ke tumpukan, dan dikeluarkan dari tumpukan jika
jalurnya salah.

Contoh prototipe algoritma backtracking adalah depth-first search , yang menemukan semua
titik sudut grafik yang dapat dicapai dari titik sudut awal yang ditentukan. Aplikasi backtracking
lainnya melibatkan pencarian melalui ruang yang mewakili solusi potensial untuk masalah
optimasi. Branch and bound adalah teknik untuk melakukan pencarian backtracking tersebut
tanpa mencari secara menyeluruh semua solusi potensial dalam ruang tersebut.
Manajemen memori waktu kompilasi

A typical call stack, storing local data and call information

for multiple levels of procedure calls. This stack grows
downward from its origin. The stack pointer points to the
current topmost datum on the stack. A push operation
decrements the pointer and copies the data to the stack; a
pop operation copies data from the stack and then
increments the pointer. Each procedure called in the
program stores procedure return information (in yellow) and
local data (in other colors) by pushing them onto the stack.
This type of stack implementation is extremely common, but
it is vulnerable to buffer overflow attacks (see the text).

A number of programming languages are stack-oriented, meaning they define most basic
operations (adding two numbers, printing a character) as taking their arguments from the stack,
and placing any return values back on the stack. For example, PostScript has a return stack and
an operand stack, and also has a graphics state stack and a dictionary stack. Many virtual
machines are also stack-oriented, including the p-code machine and the Java Virtual Machine.

Almost all calling conventions—‌the ways in which subroutines receive their parameters and
return results‍—‌use a special stack (the "call stack") to hold information about procedure/function
calling and nesting in order to switch to the context of the called function and restore to the
caller function when the calling finishes. The functions follow a runtime protocol between caller
and callee to save arguments and return value on the stack. Stacks are an important way of
supporting nested or recursive function calls. This type of stack is used implicitly by the compiler
to support CALL and RETURN statements (or their equivalents) and is not manipulated directly
by the programmer.

Some programming languages use the stack to store data that is local to a procedure. Space for
local data items is allocated from the stack when the procedure is entered, and is deallocated
when the procedure exits. The C programming language is typically implemented in this way.
Using the same stack for both data and procedure calls has important security implications (see
below) of which a programmer must be aware in order to avoid introducing serious security bugs
into a program.

Efficient algorithms

Several algorithms use a stack (separate from the usual function call stack of most
programming languages) as the principal data structure with which they organize their
information. These include:

Pemindaian Graham , sebuah algoritma untuk lambung cembung dari sistem titik dua dimensi.
Lambung cembung dari subset input dipertahankan dalam tumpukan, yang digunakan untuk
menemukan dan menghilangkan cekungan dalam batas ketika titik baru ditambahkan ke
lambung. [ 20 ]

Bagian dari algoritma SMAWK untuk menemukan baris minimum dari matriks monoton
menggunakan tumpukan dengan cara yang sama dengan pemindaian Graham. [ 21 ]

Semua nilai terdekat yang lebih kecil , masalah menemukan, untuk setiap angka dalam suatu
array, angka terdekat sebelumnya yang lebih kecil darinya. Satu algoritma untuk masalah ini
menggunakan tumpukan untuk memelihara kumpulan kandidat untuk nilai terdekat yang lebih
kecil. Untuk setiap posisi dalam array, tumpukan tersebut dipindahkan hingga nilai yang lebih
kecil ditemukan di atasnya, lalu nilai di posisi baru tersebut dimasukkan ke dalam tumpukan.
[ 22 ]

Algoritma rantai tetangga terdekat , sebuah metode untuk pengelompokan hierarkis

aglomeratif berdasarkan pemeliharaan tumpukan kluster, yang masing-masing merupakan
tetangga terdekat dari pendahulunya pada tumpukan. Ketika metode ini menemukan
sepasang kluster yang merupakan tetangga terdekat bersama, mereka akan dipisahkan dan
digabungkan. [ 23 ]

Keamanan

Beberapa lingkungan komputasi menggunakan tumpukan dengan cara yang dapat membuatnya
rentan terhadap pelanggaran dan serangan keamanan. Programmer yang bekerja di lingkungan
tersebut harus sangat berhati-hati untuk menghindari jebakan seperti itu dalam implementasi ini.
Sebagai contoh, beberapa bahasa pemrograman menggunakan tumpukan umum untuk
menyimpan data lokal ke prosedur yang dipanggil dan informasi penghubung yang
memungkinkan prosedur tersebut kembali ke pemanggilnya. Ini berarti bahwa program tersebut
memindahkan data ke dalam dan ke luar tumpukan yang sama yang berisi alamat pengembalian
penting untuk panggilan prosedur. Jika data dipindahkan ke lokasi yang salah di tumpukan, atau
item data berukuran besar dipindahkan ke lokasi tumpukan yang tidak cukup besar untuk
menampungnya, informasi pengembalian untuk panggilan prosedur dapat rusak, yang
menyebabkan program gagal.

Pihak jahat dapat mencoba melakukan serangan stack smashing yang memanfaatkan jenis
implementasi ini dengan memberikan input data berukuran besar ke program yang tidak
memeriksa panjang input. Program semacam itu dapat menyalin data secara keseluruhan ke
suatu lokasi di stack, dan dengan demikian, program tersebut dapat mengubah alamat
pengembalian untuk prosedur yang telah memanggilnya. Seorang penyerang dapat
bereksperimen untuk menemukan jenis data tertentu yang dapat diberikan ke program tersebut
sehingga alamat pengembalian prosedur saat ini disetel ulang untuk menunjuk ke suatu area di
dalam stack itu sendiri (dan di dalam data yang diberikan oleh penyerang), yang pada gilirannya
berisi instruksi yang menjalankan operasi yang tidak sah.

Jenis serangan ini merupakan variasi dari serangan buffer overflow dan merupakan sumber
pelanggaran keamanan yang sangat sering terjadi dalam perangkat lunak, terutama karena
beberapa kompiler paling populer menggunakan tumpukan bersama untuk panggilan data dan
prosedur, dan tidak memverifikasi panjang item data. Sering kali, programmer juga tidak menulis
kode untuk memverifikasi ukuran item data, dan ketika item data yang terlalu besar atau terlalu
kecil disalin ke tumpukan, pelanggaran keamanan dapat terjadi.

Lihat juga

Portal pemrograman
komputer

Daftar struktur data FIFO (komputasi dan elektronik)

Antre Tumpukan memori operasional (alias

tumpukan memori otomatis)
Antrean berujung ganda

Catatan

1. Sebaliknya, antrean beroperasi pertama masuk, pertama keluar, yang disebut dengan
akronim FIFO .
Referensi

1. Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford(2009) [1990].

Pendahuluan tentang Algoritma (edisi ke-3). MIT Press dan McGraw-Hill.
hlm. 232–[Link] Nomor telepon 0-262-03384-4.

2. Turing, Alan Mathison (1946-03-19) [1945]. Proposal untuk Pengembangan Mesin

Komputasi Otomatis (ACE) di Divisi Matematika .(NB. Disampaikan pada 1946-03-19 di
hadapan Komite Eksekutif Laboratorium Fisika Nasional (Inggris Raya).)

3. Carpenter, Brian Edward ; Doran, Robert William (1977-01-01) [Oktober 1975]. "Mesin Turing
yang lain" ([Link] . Jurnal Komputer . 20 (3):
269– 279. doi : 10.1093/comjnl/20.3.269 ([Link]
9) . ([Link] ([Link]
l%2F20.3.269) (11 halaman)

4. Blaauw, Gerrit Anne ; Brooks, Jr., Frederick Phillips (1997). Arsitektur komputer: Konsep dan
evolusi . Boston, Massachusetts, AS: Addison-Wesley Longman Publishing Co., Inc.

5. LaForest, Charles Eric (April 2007). "2.1 Lukasiewicz dan Generasi Pertama: 2.1.2 Jerman:
Konrad Zuse (1910–1995); 2.2 Generasi Pertama Komputer Stack: 2.2.1 Zuse Z4".
Arsitektur Komputer Stack Generasi Kedua ([Link]
ion_Stack_Computer_Architecture.pdf) (PDF) (tesis). Waterloo, Kanada: University of
Waterloo . hlm. 8, 11. Diarsipkan ([Link]
[Link]/publications/Second-Generation_Stack_Computer_Architecture.pdf) (PDF) dari
aslinya pada 2022-01-20 . Diakses pada 2022-07-02 . ([Link]
nd-Generation_Stack_Computer_Architecture.pdf) ([Link]
0155616/[Link]
[Link]) (178 halaman)

6. Samelson, Klaus (1957) [1955]. Written at Internationales Kolloquium über Probleme der
Rechentechnik, Dresden, Germany. Probleme der Programmierungstechnik (in German).
Berlin, Germany: VEB Deutscher Verlag der Wissenschaften. pp. 61–68. (NB. This paper
was first presented in 1955. It describes a number stack (Zahlenkeller), but names it linear
auxiliary memory (linearer Hilfsspeicher).)
 7. Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Written at Jena, Germany. Keller,
Stack und automatisches Gedächtnis – eine Struktur mit Potenzial ([Link]
m/handle/20.500.12116/4381/[Link]?sequence=1&isAllowed=y) [Cellar, stack and
automatic memory - a structure with potential] (PDF) (Tagungsband zum Kolloquium 14.
November 2014 in Jena). GI Series: Lecture Notes in Informatics (LNI) – Thematics (in
German). Vol. T-7. Bonn, Germany: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag
GmbH. ISBN 978-3-88579-426-4. ISSN 1614-3213 ([Link]
213) . Archived ([Link]
handle/20.500.12116/4381/[Link]?sequence=1&isAllowed=y) (PDF) from the original
on 2020-04-12. Retrieved 2020-04-12. [1] ([Link]
tps://[Link]/handle/20.500.12116/4374/browse?type=title&sort_by=4) (77 pages)

8. Bauer, Friedrich Ludwig; Samelson, Klaus (1957-03-30). "Verfahren zur automatischen

Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (http
s://[Link]/publicationDetails/originalDocument?CC=DE&NR=1094019&
KC=&FT=E) (in German). Munich, Germany: Deutsches Patentamt. DE-PS 1094019.
Retrieved 2010-10-01.

9. Bauer, Friedrich Ludwig; Goos, Gerhard [in German] (1982). Informatik – Eine einführende
Übersicht (in German). Vol. Part 1 (3 ed.). Berlin: Springer-Verlag. p. 222. ISBN 3-540-11722-
9. "Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen
Patentanmeldung vom 30. März 1957 eingeführt."

10. Samelson, Klaus; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelübersetzung"

[Sequential Formula Translation]. Elektronische Rechenanlagen (in German). 1 (4): 176–
182.

11. Samelson, Klaus; Bauer, Friedrich Ludwig (1960). "Sequential Formula Translation" ([Link]
[Link]/10.1145%2F366959.366968) . Communications of the ACM. 3 (2): 76–83.
doi:10.1145/366959.366968 ([Link] .
S2CID 16646147 ([Link] .

12. "IEEE-Computer-Pioneer-Preis – Bauer, Friedrich L." ([Link]

023258/[Link]
[Link]) Technical University of Munich, Faculty of Computer Science. 1989-
01-01. Archived from the original ([Link]
l/newsarticle/[Link]) on 2017-11-07.
13. Hamblin, Charles Leonard (May 1957). An Addressless Coding Scheme based on
Mathematical Notation ([Link]
sless%20coding%[Link]) (PDF) (typescript). N.S.W. University of Technology.
pp. 121-1 – 121-12. Archived ([Link]
[Link]/~rmclachl/DPACM/121%2520-%2520addressless%2520coding%2520schem
[Link]) (PDF) from the original on 2020-04-12. Retrieved 2020-04-12. (12 pages)

14. Kämmerer, Wilhelm [in German] (1958-12-11). Ziffern-Rechenautomat mit Programmierung

nach mathematischem Formelbild ([Link]
t?id=22616) (Habilitation thesis) (in German). Jena, Germany: Mathematisch-
naturwissenschaftliche Fakultät, Friedrich-Schiller-Universität. urn:nbn:de:gbv:27-20130731-
133019-7 . PPN:756275237. Archived ([Link]
ps://[Link]/receive/dbt_mods_00022616) from the original on 2023-10-
14. Retrieved 2023-10-14. [2] ([Link]
[Link]/servlets/MCRFileNodeServlet/dbt_derivate_00027985/[Link])
(2+69 pages)

15. Kämmerer, Wilhelm [in German] (1960). Ziffernrechenautomaten. Elektronisches Rechnen

und Regeln (in German). Vol. 1. Berlin, Germany: Akademie-Verlag.

16. Ball, John A. (1978). Algorithms for RPN calculators ([Link]

orrpn0000ball) (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley &
Sons, Inc. ISBN 978-0-471-03070-6. LCCN 77-14977 ([Link] .

17. Godse, Atul P.; Godse, Deepali A. (2010-01-01). Computer Architecture ([Link]
[Link]/books?id=mOaXS_x-iW4C&pg=PR1) . Technical Publications. pp. 1–56. ISBN 978-8-
18431534-9. Retrieved 2015-01-30.

18. Horowitz, Ellis (1984). Fundamentals of Data Structures in Pascal. Computer Science Press.
p. 67.

19. Pandey, Shreesham (2020). "Data Structures in a Nutshell" ([Link]

[Link]?abstract_id=4145204) . Dev Genius. 2020. SSRN 4145204 ([Link]
com/sol3/[Link]?abstract_id=4145204) .

20. Graham, Ronald "Ron" Lewis (1972). An Efficient Algorithm for Determining the Convex Hull
of a Finite Planar Set ([Link]
(PDF). Information Processing Letters 1. Vol. 1. pp. 132–133. Archived ([Link]
org/web/20221022132156/[Link]
f) (PDF) from the original on 2022-10-22.
21. Aggarwal, Alok; Klawe, Maria M .; Moran, Shlomo ; Shor, Peter ; Wilber, Robert (1987).
"Aplikasi geometrik algoritma pencarian matriks". Algorithmica . 2 ( 1–4 ) : 195–208 . doi :
10.1007/BF01840359 ([Link] . MR 0895444. (https://
[Link]/mathscinet-getitem?mr=0895444) S2CID 7932878 ([Link]
[Link]/CorpusID:7932878) . ([Link] (http
s://[Link]/mathscinet-getitem?mr=0895444) ([Link]
rg/CorpusID:7932878) .

22. Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993). "Algoritma paralel logaritma ganda
optimal berdasarkan pencarian semua nilai terdekat yang lebih kecil". Jurnal Algoritma . 14
(3): 344– 370. CiteSeerX [Link].5669 ([Link]
oi=[Link].5669) . doi : 10.1006/jagm.1993.1018 ([Link]
3.1018) . ([Link] (http
s://[Link]/10.1006%2Fjagm.1993.1018) .

23. Murtagh, Fionn (1983). "Survei tentang kemajuan terbaru dalam algoritma pengelompokan
hierarkis" ([Link]
ering_algorithms.pdf) (PDF) . Jurnal Komputer . 26 (4): 354– 359. doi :
10.1093/comjnl/26.4.354 ([Link] . ([Link]
[Link]/strule/old-articles/Survey_of_hierarchical_clustering_algorithms.pd
f) ([Link] .

Artikel ini memuat materi domain publik dari Paul E. Black. "Bounded stack" ([Link]
[Link]/dads/HTML/[Link]) . Dictionary of Algorithms and Data Structures .
NIST . ([Link]

Bacaan lebih lanjut

Donald Knuth . Seni Pemrograman Komputer , Volume 1: Algoritma Fundamental , Edisi Ketiga.
Addison-Wesley, 1997. ISBN 0-201-89683-4 . Bagian 2.2.1: Tumpukan, Antrean, dan Deques,
hlm. 238–243.

Langmaack, Hans [dalam bahasa Jerman] (2015) [2014-11-14]. Ditulis di Kiel, Jerman.
Friedrich L. Bauers und Klaus Samelsons Arbeiten di den 1950er-Jahren ([Link]
eam/handle/20.500.12116/33413/[Link]?sequence=1&isAllowed=y) zur Einführung der
Begriffe Kellerprinzip und Kellerautomat [ Karya Friedrich L. Bauer dan Klaus Samelson pada
tahun 1950-an tentang pengenalan istilah prinsip ruang bawah tanah dan robot ruang bawah
tanah ] (PDF) (dalam bahasa Jerman). Jena, Jerman: Institut für Informatik, Christian-
Albrechts-Universität zu Kiel. hlm. 19– 29. Diarsipkan ([Link]
205159/[Link]
d=y) (PDF) dari versi asli pada 14-11-2022 . Diakses tanggal 14-11-2022 .(11 halaman) (NB.
Diterbitkan di Fothe & Wilke .)
 Goos, Gerhard [dalam bahasa Jerman] (07-08-2017). Geschichte der deutschsprachigen
Informatik - Programmiersprachen und Übersetzerbau [ Sejarah ([Link]
de/proceedings/kps2017_submission_1.pdf) informatika di negara-negara berbahasa
Jerman - Bahasa pemrograman dan desain kompiler ] (PDF) (dalam bahasa Jerman).
Karlsruhe, Jerman: Fakultät für Informatik, Institut Teknologi Karlsruhe (KIT). Diarsipkan (http
s://[Link]/web/20220519131116/[Link]
2017_submission_1.pdf) (PDF) dari versi asli pada 19-05-2022 . Diakses tanggal 14-11-2022 .
([Link]
s/kps2017_submission_1.pdf) (11 halaman)

Tautan eksternal

Stack Machines - gelombang baru ([Link]

[Link])

Kedalaman tumpukan pembatas ([Link]

Analisis Ukuran Tumpukan untuk Program Berbasis Interupsi ([Link]

rg/paper/[Link])