Stack atau Tumpukan

STACK atau TUMPUKAN

1. DEFINISI STACK

Stack atau tumpukan adalah bentuk khusus dari linear list. Pada stack, penghapusan serta
pemasukan elemennya hanya dapat dilakukan di satu posisi, yakni posisi akhir dari list.
Posisi ini disebut puncak atau top dari stack. Elemen stack S pada posisi ini dinyatakan
dengan TOP(S).
Jelasnya, bila stack S [S1, S2, …, ST], maka TOP(S) adalah ST. Banyaknya elemen stack
S pada suatu saat tertentu biasa kita sebut sebagai NOEL(S). Jadi untuk stack kita di atas,
NOEL(S) = T. Seperti halnya pada semua linear list, pada stack dikenal operasi penghapusandan pemasukan.
Operator penghapusan elemen pada stack disebut POP, sedangkan operator pemasukan
elemen, disebut PUSH. Untuk menggambarkan kerja kedua operator di atas, berikut ini
suatu contoh bermula dari stack hampa S[ ], yang kita gambar sebagai:
S NOEL(S) = 0, TOP(S) tidak terdefinisimula-mula kita PUSH elemen A, diperoleh Stack S = [A]
A S NOEL(S) = 1, TOP(S) = A
Apabila kemudian kita PUSH elemen B, diperoleh Stack S = [A,B]
S NOEL(S) = 2, TOP(S) = B
Selanjutnya bila PUSH elemen C, diperoleh Stack S = [A,B,C]
S NOEL(S) = 3, TOP(S) = B
Kemudian bila kita POP elemen C, diperoleh Stack S = [A,B]
S NOEL(S) = 2, TOP(S) = B
Kita dapat pula PUSH 2 elemen D dan E. Akan dihasilkan Stack S = [A,B,D,E]
S NOEL(S) = 4, TOP(S) = E, dan seterusnya.
Terlihat bahwa kedua operasi di atas, pada stack adalah bersifat ‘terakhir masuk pertama
keluar’ atau ‘last in first out (LIFO)’. Pada hakekatnya kita tidak membatasi berapa banyakelemen dapat masuk ke dalam stack. Untuk suatu stack S[S1, S2,..., SNOEL], kita katakanbahwa elemen Si, berada di atas elemen Sj, jika i lebih besar dari j. Suatu elemen tidak dapatkita POP ke luar, sebelum semua elemen di atasnya dikeluarkan.


2. OPERASI PADA STACK

Terdapat empat operasi pada stack, yakni CREATE (stack), ISEMPTY(stack), PUSH
(elemen, stack), dan POP (stack). CREATE(S) adalah operator yang menyebabkan stack Smenjadi satu stack hampa. Jadi NOEL(CREATE(S)) adalah 0, dan TOP(CREATE(S))
tak terdefinisi.
Sedangkan operator ISEMPTY(S) bermaksud memeriksa apakah stack S hampa atau
tidak. Operandnya adalah data bertipe stack, sedangkan hasilnya merupakan data bertipe
boolean. ISEMPTY(S) adalah true, jika S hampa, yakni bila NOEL(S) = 0, dan false dalamhal lain. Jelas bahwa ISEMPTY(CREATE(S)) adalah true.
Operator PUSH (E,S) akan bekerja menambahkan elemen E pada stack S. E ditempatkan
sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan
elemen TOP(S) dari dalam stack. POP(S) akan mengurangi nilai NOEL(S) dengan 1.
Suatu kesalahan akan terjadi apabila, kita mencoba melakukan POP(S) terhadap stack S
yang hampa.
Kesalahan overflow akan terjadi jika kita melakukan operasi pemasukan data (PUSH)
pada stack yang sudah penuh (dalam hal ini jika banyaknya elemen yang kita masukkan kedalam sebuah stack sudah melampaui batas kemampuan memori atau telah didefinisikansebelumnya).Sebaliknya, kesalahan underflow akan terjadi jika stack sudah dalam keadaan hampa,kita lakukan operasi pengeluaran atau penghapusan (POP).


3 DEKLARASI STACK DALAM COBOL DAN PASCAL

Meskipun stack amat luas digunakan, banyak bahasa pemrograman tidak mempunyai
tipe data stack secara built-in. Dalam hal ini, Pemrogram harus memanipulasi sendiri
fasilitas yang dimiliki bahasa pemrograman tersebut, untuk dapat melakukan operasi
stack terhadap variabel stack.
Mungkin cara yang paling sederhana adalah membentuk stack dalam bentuk semacam
array. Jelas kita harus membedakan suatu stack dengan suatu array yang sesungguhnya.
Pemrogram harus memaksakan berlakunya aturan LIFO bagi stack. Selain itu juga,
penempatan stack dalam bentuk array mengakibatkan suatu keterbatasan, yakni bahwa
elemen stack harus homogen. Keterbatasan lain yang timbul adalah keharusan Pemrogram untuk menentukan batas atas dari subscript array, walaupun stack secara teori tidak memilikibatas maksimum dalam jumlah elemen. Jika diinginkan, seharusnya kita dapat membuatstack yang panjangnya tak hingga.
Satu hal yang nyata membedakan stack dengan array adalah banyaknya elemen stack
yang dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah
array selalu tetap.
Sekarang marilah kita bicarakan deklarasi dari variabel S yang bertipe data stack.
Diasumsikan bahwa elemen dari S masing-masing bertipe data integer dan panjang stack
maksimum adalah 100 elemen. Kita mendeklarasikan sebuah array yang dilengkapi
dengan variabel TOP-PTR.
Variabel TOP-PTR ini menyatakan subscript dari elemen TOP(S) dari stack. Kita
menamakan kombinasi dari array dan indikator untuk TOP tersebut dengan nama STACKSTRUCT.
Dengan penyajian seperti ini, berlaku bahwa NOEL(S) = TOP-PTR,
ISEMPTY(S) adalah true bila TOP-PTR = 0, dan false bila TOP-PTR lebih besar dari 0.
Dalam COBOL
01 STACK-STRUCT.
02 S PIC 9(5)
OCCURS 100 TIMES.
02 TOP-PTR PIC 9(3)
Dalam Pascal
type stackstruct;
record Stack: Array [ 1..100] of integer;
topptr : integer
end
var S : stackstruct;
Kompilator tidak dapat mengerti aturan LIFO yang kita inginkan. Untuk itu Pemrogram
harus berhati-ati dan tidak memberi indeks pada S di sembarang tempat, selain
dengan nilai TOP-PTR.
Operasi PUSH dan POP dapat kita program sebagai berikut: kita gunakan EON
untuk menyatakan elemen yang di-PUSH ke dalam S dan EOFF untuk elemen yang di-
POP ke luar S. NOEL-MAX menyatakan panjang maksimum stack. Jadi di sini NOELMAX= 100.
Dalam paragraf COBOL:
PUSH.
IF TOP-PTR < NOEL-MAX
THEN COMPUTE TOP-PTR = TOP-PTR+1
MOVE EON TO S( TOP-PTR )
ELSE overflow condition.
POP.
IF TOP-PTR > 0
THEN MOVE S( TOP-PTR ) TO EOFF
COMPUTE TOP-PTR = TOP-PTR-1
ELSE overflow condition.
Dalam procedure Pascal:
procedure PUSH (eon : integer);
begin
if (s.topptr < noelmax)
then
begin s.topptr < = s.topptr + 1;
s.Stack [s.topptr] :=eon
end
else OVERFLOW-CONDITION
end
procedure POP (var eoff:integer);
begin
if (s.topptr>0)
then
begin eoff;= s.Stack [s.topptr];
s.topptr ;= s.topptr - 1
end
else UNDERFLOW-CONDITION
end;
Stack sangat luas pemakaiannya dalam menyelesaikan berbagai macam problema.
Kompilator, sistem operasi, dan berbagai program aplikasi banyak menggunakan konsep
stack tersebut. Salah satu contoh adalah problema Penjodohan Tanda Kurung atau matching parantheses.
Sebuah kompilator mempunyai tugas, salah satu di antaranya adalah menyelidiki
apakah Pemrogram telah dengan cermat mengikuti aturan tata bahasa, atau sintaks dari
bahasa pemrograman yang bersangkutan. Misalnya untuk parantheses kiri (tanda kurung
buka) yang diberikan, harus dipastikan adanya parantheses kanan (tanda kurung tutup)
yang bersangkutan.
Stack dapat digunakan dalam prosedur matching yang digunakan. Algoritmanya
sederhana, kita amati barisan elemen dari kiri ke kanan. Bila kita bertemu dengan suatu
parantheses kiri, maka parantheses kiri tersebut kita PUSH ke dalam sebuah stack. Selanjutnya bila kita bertemu dengan suatu parantheses kanan, kita periksa stack, apakah hampa atautidak. Kalau stack hampa, berarti terdapat parantheses kanan tanpa adanya parantheses kiri.
Suatu kesalahan, atau error, apabila stack tidak hampa, berarti tidak diperoleh sepasangparantheses kiri, dan kanan, kita POP elemen ke luar stack.
Jika sampai berakhirnya barisan elemen, stack tidak hampa berarti terdapat parantheses
kiri yang tidak tertutup dengan parantheses kanan. Lagi suatu kesalahan. Kita akan membuatprogramnya dalam COBOL. Barisan elemen yang diamati kita tampung karakter demikarakter dalam variabel array bernama STRING. Stack ditempatkan dalam array STACK.
Kita asumsikan bahwa jumlah maksimum karakter dalam barisan elemen adalah 80 dan
barisan berakhir dengan karakter titik-koma.


4 APLIKASI STACK

Struktur datanya didefinisikan sebagai berikut:
01 STACK-STRUCT.
02 S PIC 9(5) PIC X
OCCURS 80 TIMES.
PIC 99 VALUE 0.
02 TOP-PTR
01 STRING.
02 CHAR PIC X
OCCURS 80 TIMES.
01 NEXT-CHAR PIC 99
Struktur di atas kita manipulasi dengan prosedur sebagai berikut:
PERFORM SCAN-NEXT-CAR
VARYING NEXT-CHAR FROM 1 BY 1
UNTIL NEXT-CHAR > 80
OR CHAR (NEXT-CHAR) = “;”.
IF TOP-PTR NOT = 0 THENinvalid syntax,
parenthesis kiri tak tertutup
ELSE Valid syntax.
SCAN-NEXT-CHAR
IF CHAR (NEXT-CHAR) = “(”
PERFORM PUSH
ELSE
IF CHAR (NEXT-CHAR) = “)”
PERFORM POP
PUSH
COMPUTE TOP-PTR = TOP-PTR + 1
MOVE CHAR (NEXT-CHAR) TO STACK (TOOP-PTR).
IF TOP-PTR > 0
COMPUTE TOP-PTR - 1
ELSE invalid syntax, tak ada parenthesis
Silakan Anda buat programnya dalam bahasa pemrograman yang Anda kuasai.



5. DAFTAR LINEAR

Sebuah daftar linear atau linear list, merupakan suatu struktur data umum yang terbentuk
dari barisan hingga (yang terurut) dari satuan data ataupun dari record. Untuk mudahnya,
elemen yang terdapat di dalam daftar disebut dengan simpul atau node. Daftar disebut
linear (lurus), karena elemen tampak seperti berbaris, yakni bahwa setiap simpul, kecuali
yang pertama dan yang terakhir, selalu memiliki sebuah elemen penerus langsung (suksesorlangsung) dan sebuah elemen pendahulu langsung (predesesor langsung).
Di sini, banyak simpul atau elemen, tersebut dapat berubah-ubah, berbeda dengan
array yang banyak elemennya selalu tetap. Kita menyatakan linear list A yang mengandungT elemen pada suatu saat, sebagai A = [A1, A2, …AT]. Jika T = 0, maka A disebut list hampaatau null list.
Suatu elemen dapat dihilangkan atau dihapus (deletion) dari sembarang posisi dalam
linear list, dan suatu elemen baru dapat pula dimasukkan (insertion) sebagai anggota list
pada posisi sembarang (di mana saja).File, merupakan salah satu contoh dari daftar linear yang elemen-elemennya berupa
record. Selain file, contoh lain dari daftar linear adalah stack atau tumpukan, queue atau
antrean, dan daftar berkait atau linear linked list atau one-way list. Pada Bab 3 ini kita bahastentang stack tersebut. Selanjutnya pada Bab 4 kita bahas tentang antrean tentang linked list.


Sumber : seri diktat kuliah, pengantar struktur data Universitas Gunadarma