STACK

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 (suksesor langsung) 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 mengandung T elemen pada suatu saat, sebagai A = [A1, A2, ...AT]. Jika T = 0, maka A disebut list hampa atau 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 ini kita bahas tentang stack tersebut. Selanjutnya (berikutnya) kita bahas tentang antrean (queue) dan selanjutnya lagi tentang linked list.

STACK atau TUMPUKAN
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 [S 1 , S 2 , ..., S T ], maka TOP(S) adalah S T . 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 penghapusan dan 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 terdefinisi

mula-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]

|     |
| B |
| A | S         NOEL(S) = 2, TOP(S) = B

Selanjutnya bila PUSH elemen C, diperoleh Stack S = [A,B,C]

| C |
| B |
| A | S         NOEL(S) = 3, TOP(S) = C

Kemudian bila kita POP elemen C, diperoleh Stack S = [A,B]

|     |
| B |
| A | S         NOEL(S) = 2, TOP(S) = B

Kita dapat pula PUSH 2 elemen D dan E. Akan dihasilkan Stack S = [A,B,D,E]

| E |
| D |
| B |
| A | 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 banyak elemen dapat masuk ke dalam stack. Untuk suatu stack S[S 1 , S 2 ,..., S NOEL ], kita katakan bahwa elemen S i , berada di atas elemen S j , jika i lebih besar dari j. Suatu elemen tidak dapat kita POP ke luar, sebelum semua elemen di atasnya dikeluarkan.

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 S menjadi 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 dalam hal 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 didefinisikan sebelumnya).

Sebaliknya, kesalahan underflow akan terjadi jika stack sudah dalam keadaan hampa, kita lakukan operasi pengeluaran atau penghapusan (POP).

===