Stack dan Queue

STACK (Tumpukan)

Stack merupakan bentuk khusus dari suatu struktur data, dimana node yang ditambahkan ke dalam list dan diambil dari list hanya pada kepalanya, atau dengan prinsip pengolahannya adalah last-in first-out (LIFO). Pada struktur ini hanya ada dua fungsi utama, yaitu push (memasukkan node ke dalam stack), dan pop (mengambil node dari stack).

Pengertian tumpukan :

Secara sederhana tumpukan bisa diartikan sebagai kumpulan data yang seolah-oleh diletakkan di atas data yang lain. Dalam suatu tumpukan akan dapat dilakukan operasi penambahan (penyisipan) dan pengambilan (penghapusan) data melalui ujung yang sama, ujung ini merupakan ujung atas tumpukan.

Operasi dalam tumpukan :

Ada 2 operasi dasar yang bisa dilaksanakan pada sebuah tumpukan, yaitu :

1. Menyisipkan Data (Push), perintah push digunakan untuk memasukkan data ke dalam tumpukan
2. Menghapus Data (Pop), operasi pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan. Untuk dapat mengetahui kosong tidaknya suatu tumpukan adalah dengan suatu fungsi yang menghasilkan suatu data bertipe boolean. 

Pemanfaatan tumpukan :

Pemanfaatan tumpukan antara lain untuk menulis ungkapan dengan menggunakan notasi tertentu.

Contoh :

( A + B ) * ( C - D )

Tanda kurung selalu digunakan dalam penulisan ungkapan numeris untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.

Dari contoh ( A + B ) akan dikerjakan terlebih dahulu, kemudian baru ( C - D ) dan terakhir hasilnya akan dikalikan.

A + B * C - D

B * C akan dikerjakan terlebih dahulu, hasil yang didapat akan berbeda dengan hasil notasi dengan tanda kurung.


QUEUE (Antrian)

Queue adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi depan atau front).
Jika pada tumpukan dikenal dengan menggunakan prinsip LIFO (Last In First Out), maka pada antrian prinsip yang digunakan adalah FIFO (First In First Out).

Implementasi antrian dengan array

Karena antrian merupakan suatu kumpulan data, maka tipe data yang sesuai untuk menyajikan antrian adalah mengguanakan array atau list (senarai berantai).

Antrian tersebut berisi 6 elemen yaitu A, B, C, D, E, dan F. Elemen A terletak dibagian depan antrian dan elemen F terletak di bagian belakang antrian.

Jika terdapat elemen baru yang akan masuk, maka elementersebut akan diletakkan disebelah kanan F.

Jika ada elemen yang akan dihapus, maka A akan dihapus terlebih dahulu.

Antrian dengan penambahan elemen baru, yaitu G dan H.

Antrian dengan penghapusan elemen antrian, yaitu A dan B.

Seperti dalam tumpukan atau stack, maka di alam antrian juga dikenal 2 operasi dasar yaitu menambah elemen baru yang akan diletakkan di bagian belakang antrian dan menghapus elemen yang terletak di bagian epan antrian. Selain itu juga harus dilihat kondisi antrian mempunyai isi atau masih kosong.

Implementasi antrian dengan pointer

Pada prinsipnya, antrian dengan pointer akan sama dengan ntrian yang menggunakan array. Penambahan akan selalu dilakukan pada elemen dengan posisi paling depan. Antrian sebenarnya merupakan bentuk khusus dari suatu senarai berantai (linked list).

Pada antrian bisa digunakan 2 variabel yang menyimpan posisi elemen paling depan dan elemen paling belakang. Jika menggunakan senarai berantai maka dengan 2 pointer yang menunjuk elemen kepala (paling depan) dan elemen ekor (paling belakang) dapat dibentuk antrian.