stack

STACK

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

APLIKASI STACK PADA STRUKTUR DATA

Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain. Sebagai bagian dari struktur data, aplikasi stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat palindrome, penguji tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi postfix.
Pada perhitungan aritmatika, notasi infix adalah notasi yang menempatkan operator ditengah dua operand sedangkan notasi Postfix adalah notasi yang menempatkan operator setelah dua operand. Penggunaan notasi infix merupakan hal yang lumrah digunakan dalam perhitungan aritmatika dibandingkan dengan penggunaan notasi Postfix, akan tetapi bagi mesin kompilasi notasi Postfix merupakan notasi yang digunakan untuk melakukan suatu perhitungan.
Operasi-operasi Stack

Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat diterapkan seperti membuat stack, penambahan eleme ke dalam stack, menghapusan elemen dari dalam stack, dan operasi lain yang berhubungan dengan stack tersebut. Adapun operasi-operasi dasar dari suatu stack adalah :

a) Create(Stack)
Operasi Create(Stack) digunakan untuk membuat suatu stack baru dengan nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0, TOP(S) = NULL (tidak terdefinisikan)

b) IsEmpty(Stack)
Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

a. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0
b.False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan NOEL(S) > 0

c) Push(Stack, Elemen)
Operasi ini merupakan operasi untuk menambahkan satu elemen dengan nilai X pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai X, penerapan operasi push pasa suatu stack S akan berakibat overflow jika NOEL(S) dari stack tersebut telah bernilai maksimum.

d) Pop(Stack)
Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi pop dapat menyebabkan kondisi underflow jika suatu stack S yang berada dalam kondisi minimum dikenakan operasi pop.
Notasi Infix dan Postfix

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.

Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi perhitungan yaitu :

1) Notasi prefix, jika operator ditempatkan sebelum dua operand
2) Notasi infix, jika operator ditempatkan diantara dua operand
3) Notasi postfix, jika operator ditempatkan setelah dua operand

Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang lain, akan tetapi notasi Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.

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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s