Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri Stack :
• Elemen TOP (puncak) diketahui
• penisipan dan penghapusan elemen selalu dilakukan di TOP
• LIFO
Pemanfaatan Stack :
• Perhitungan ekspresi aritmatika (posfix)
• algoritma backtraking (runut balik)
• algoritma rekursif
Operasi Stack yang biasanya :
1. Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
2. Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
3. IsEmpty ()
4. IsFull ()
5. dan beberapas selektor yang lain
STACK ( TUMPUKAN )
Stack adalah suatu bentuk khusus dari linier list, dengan operasi penyisipan dan penghapusan dibatasi hanya pada satu sisinya, yaitu puncak stack (TOP).
Aturan penyisipan dan penghapusan elemennya tertentu :
1. Penyisipan selalu dilakukan “di atas “ TOP
2. Penghapusan selalu dilakukan pada TOP
Ilustrasi Stack
Terdapat dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.
F ATAS
E
D
C
B
A BAWAH
Dapat dilihat bahwa kotak B terletak diatas kotak A dan ada dibawah kotak C. Berdasarkan pada stack tersebut dapat disimpulkan bahwa penambahan dan pengambilan sebuah kotak hanya dapat dilakukan dengan melewati satu ujung saja, yaitu bagian atas.
Kotak F adalah kotak paling atas sehingga jika ada kotak lain yang akan disisipkan maka kotak tersebut akan diletakkan pada posisi paling atas (diatas kotak F). Demikian juga pada saat pengambilan kotak, kotak F akan diambil pertama kali.
Menyisipkan menghapus
F ATAS
E
D
C
B
A BAWAH
Perbandingan Antara Stack Dengan Linked List VS Stack Dengan Array
Berikut ini adalah perbandingan algoritma pada operasi-operasi dasar dari Stack Dengan Linked List dan Stack Dengan Array, dengan menggunakan bahasa pemrograman Pascal :
Stack Dengan Linked List Stack Dengan Array
operasi : create()
procedure create;
begin
top := nil ;
end; procedure create;
begin
top := 0;
end;
operasi : empty()
function empty : ias an;
begin
empty := false ;
if top = nil then empty := true ;
end; function empty : ias an;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full()
tidak ada istilah full pada stack.
Program tidak menentukan jumlah elemen stack yang mungkin ada. Kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. Tempat akan sesuai dengan banyaknya elemen yang mengisi stack. Function full : ias an;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push()
procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end; procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop()
procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end; procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear
procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end; procedure clear ;
begin
top := 0 ;
end;
Ada 2 operasi dasar yang ias dilaksanakan pada sebuah stack, yaitu :
• Operasi Push (menyisipkan data)
Perintah push digunakan untuk memasukkan data ke dalam stack.
Push (34)
34
9 9
25 25
3 3
• Operasi Pop (menghapus data)
Operasi pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah stack.
Penyajian tumpukan dalam bahasa Pascal dapat disajikan dalam beberapa cara, yaitu dengan tipe data array, record, atau pointer.
Penyajian tumpukan dengan tipe data pointer dapat dilakukan dengan senarai berkepala. Operasi memasukkan simpul baru pada simpul pertama, identik dengan memasukkan data pada tumpukan, atau dengan kata lain senarai berantai yang dapat dimodifikasi melalui pointer yang menunjuk pada elemen pertama serupa dengan tumpukan yang hanya dapat dimodifikasi melalui tumpukan paling atas.
Karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus.Dikatakan bahwa elemen Stack akan tersusun secara LIFO (Last In First Out).
Maka secara lojik, sebuah STACK dapat digambarkan sebagai list linier yang setiap elemennya adalah
Type ElmtS = record
Next : address >
dengan InfoType terdefinisi yang menentukan informasi yang disimpan pada setiap elemen stack, dan address adalah “alamat” dari elemen. Selain itu alamat elemen terbaru (TOP) dicatat, sedangkan alamat elemen yang paling “bawah”, yaitu yang paling lama biasanya diebut BOTTOM. TOP adalah elemen pertama list, supaya penambahan dan penghapusan dengan mudah dan efisien dapat dilakukan.
Sehingga jika S adalah sebuah Stack, dan P adalah address maka
>> Top (S) adalah alamat elemen TOP, dimana operasi penyisipan/penghapusan dilakukan.
>> Info (P) adalah informasi yang disimpan pada alamat P
>> Next (P) adalah alamat suksesor P
>> ElmtS (P) adalah sebuah elemen stack yang beralamat P
>> Stack kosong adalah Stack dengan Top (S) = Nil ( tidak terdefinisi )
Bagian Deklarasi dari algoritma pada Stack :
Deklarasi
type InfoType = … {Sebuah type terdefinisi}
type Address pointer to ElmtS
type ElmtS = record
Next : Address >
type Stack = record
{Deklarasi Nama Peubah}
S : Stack
P : Address
Operasi Operasi dan dan fungsi fungsi dasar dasar pada pada STACK
a. Test STACK kosong
function StackEmpty (S : STACK) →Boolean
{ TEST stack kosong : Mengirim true, jika tumpukan kosong, false jika tumpukan tidak kosong}
Deklarasi
Deskripsi
return (Top (S) = Nil)
b. Pembuatan STACK kosong
Procedure CreateEmptyS (Output S : STACK)
{K. Awal : sembarang,
K. Akhir : sebuah stack S yang kosong siap dipakai terdefinisi
Proses : Membuat stack kosong }
Deklarasi
Deskripsi
Top (S) ← Nil
c.Penambahan sebuah elemen pada STACK (Push)
procedure Push@ (Input/Output S : STACK Input P :
address)
{Menambahkan sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui alamatnya}
{K.Awal : Stack mungkin kosong, P terdefinisi (berarti terdefinisi informasinya, Next (P) = Nil}
{K.Akhir : Top (S) adalah P}
Deklarasi
Deskripsi
{ insert sebagai elemen pertama }
Next (P) ← TOP (S)
TOP (S) ← P
procedure Push( Input / Output S:STACK Input E: InfoType )
{ Menambahkan sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui informasinya }
{ K. Awal : Stack mungkin kosong , E terdefenisi , alokasi alamat selalu berhasil }
{ K. Akhir : TOP (S) berisi E )
Deklarasi
P : address
Deskripsi
Alokasi ( P ) { alokasi selau berhasil }
Info(P) ← E
{ insert sebagai elemen pertama }
Next(P) ← TOP(S)
TOP(S) ← P
c. Penghapusan sebuah elemen pada STACK (Pop)
procedure PopStack@(Input/Output S : STACK
Output P : address)
{K.Awal : Stack tidak kosong
K.Akhir : Alamat elemen Top (S) disimpan pada P, sehingga informasinya dapat diakses melalui P
Proses : Menghapus elemen stack, stack tidak boleh kosong dan mungkin menjadi kosong }
Deklarasi
Deskripsi
P ← TOP (S)
TOP (S) ← Next(TOP(S))
procedure PopStack(Input/Output S : STACK
Output E : InfoType)
{K.Awal : Stack tidak kosong
K.Akhir : Alamat elemen Top (S) disimpan pada E, alamat TOP yang lama didealokasi
Proses : Menghapus elemen stack, stack tidak boleh kosong dan mungkin menjadi kosong }
Deklarasi
P : address
Deskripsi
P ← TOP (S)
E ← Info(P)
TOP (S) ← Next(TOP(S))
Dealokasi (P)
Sumber : (http://sahrulwijaya.blogspot.com/2009/11/stack-tumpukan.html )
