STACK

Stack merupakan Suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen; jumlah elemen di dalam list dapat berubah-ubah.

Linier list A yang terdiri dari T elemen pada waktu t, dinotasikan sebagai :

A = [ A1, A2, …, AT]

Jika T = 0, maka A disebut “Empty List” atau “Null List”

Suatu elemen dapat dihilangkan/dihapus dari sembarang posisi dalam linier list, dan dapat pula dimasukkan elemen baru sebagai anggota list.

Contoh :

1. File, dengan elemennya berupa record

2. Buku telepon

3. Stack

4. Queue

5. Linear link list

STACK

Stack adalah suatu bentuk khusus dari linier list, dengan operasi penyisipan dan penghapusan dibatasi hanya pada satu sisinya, yaitu puncak stack (TOP).

Elemen teratas dari stack dinotasikan sebagai TOP(S). Untuk stack S, dengan S = [S1, S2, S3, …, ST] maka TOP(S) = ST.

Jumlah elemen di dalam stack kita notasikan dengan NOEL(S).

NOEL(S) menghasilkan nilai integer.

Untuk stack S = [S1, S2, S3, …, ST] maka NOEL (S) = T.

Operator penyisipan (insertion) : PUSH

Operator penghapusan (deletion) : POP

Operasi stack : LIFO (Last In First Out), yaitu : yang terakhir masuk yang pertama keluar. Jika ada NOEL elemen didalam stack, maka elemen ke NOEL merupakan elemen puncak (TOP).

Stack Secara Umum :

S = [S1, S2, …, SNOEL] bahwa : SI berada di atas elemen SJ, untuk I > J.

SI akan dikeluarkan lebih dulu dari elemen di bawahnya. Contoh stack : Tumpukan baki dalam cafeteria. Empat operasi dasar yang berlaku pada stack :

1. CREATE(stack)

2. ISEMPTY(stack)

3. PUSH(elemen, stack)

4. POP(stack)

1. CREATE

Adalah operator yang menunjukkan suatu stack kosong dengan nama S.

Jadi : NOEL(CREATE(S)) = 0

TOP(CREATE(S)) adalah TIDAK TERDEFINISI.

2. ISEMPTY

Adalah operator yang menentukan apakah stack S kosong.

Operandnya terdiri dari type data stack. Hasilnya merupakan type data Boolean:

ISEMPTY(S) = True. Jika S hampa, yakni bila NOEL(S) = 0.

3. PUSH

adalah operator yang menambahkan elemen E pada puncak stack S.

Hasilnya merupakan stack yang lebih besar.

PUSH(E,S). E ditempatkan sebagai TOP(S).

4. POP(stack)

adalah operator yang menghapus sebuah elemen dari puncak stack S.

Hasilnya merupakan stack yang lebih kecil.

• POP(S) mengurangi NOEL(S)

• POP(CREATE(S)) → kondisi error

• POP(PUSH(E,S)) = S

APLIKASI STACK

1. Penjodohan Tanda Kurung/Matching Parantheses

ALGORITMA

a. Amati barisan elemen dari kiri ke kanan

b. • bila bertemu ‘(‘, maka ‘(‘ di push ke dalam stack.

• bila bertemu ‘)’, maka periksa stack hampa atau tidak.

bila hampa → ada ‘)’ dan tidak ada ‘(‘ (error)

bila tidak hampa → ada sepasang ‘(‘ & ‘)’ & POP elemen keluar

NOTASI POSTFIX

ALGORITMA

Amati barisan dari kiri ke kanan

1. Jika ‘(‘, maka PUSH ke dalam stack.

2. Jika ‘)’, POP elemen dalam stack sampai simbol ‘(‘. Semua di POP

merupakan output kecuali ‘(‘ tadi.

3. Jika simbol operand, langsung merupakan output.

4. Jika simbol operator, maka :

Jika elemen TOP stack dengan level >= maka POP sebagai output

teruskan sampai ‘(‘.

elemen TOP <, operator yang diamati di PUSH ke dalam stack.

5. Bila ‘;’ kita POP semua elemen dalam stack hingga hampa.

APLIKASI STACK

Notasi Postfix

Contoh :

Notasi Infix : ((A+B) * C/D+E^F)/G;

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