Stack and Queue

Christophorus Wilson

2301869273

Stack vs Queue

Keduanya adalah struktur data yang berfungsi untuk menyimpan data secara berurutan. Perbedaannya terdapat pada sifatnya.

Sifat dari Stack adalah LIFO (Last In First Out). Analoginya adalah seperti buku yang ditumpuk, buku yang terakhir kali diletakkan (paling atas)  adalah yang pertama kali diambil.

Sedangkan sifat dari Queue adalah FIFO (First In First Out). Analoginya seperti mengantri di kasir pada umumnya. Orang yang pertama kali masuk adalah yang pertama kali dilayani.

Stack

Stack dapat direpresentasikan menggunakan array dan linked list.

Pada array, terdapat 2 variabel TOP dan MAX. TOP adalah variabel penanda index paling kanan yang berisi. Jadi apabila variabel TOP = NULL , maka berarti array tersebut kosong. Sedangkan MAX adalah total elemen yang dapat disimpan dalam array tersebut.

Sedangkan pada linked list, pointer START digunakan sebagai variabel TOP. Jika TOP = NULL , maka berarti linked list tersebut kosong.

Perbedaan mendasar dari array dan linked list adalah array membutuhkan sebuah nilai pasti untuk menentukan batas dari isi sebuah array, namun linked list tidak membutuhkan nilai apapun karena linked list bersifat dinamis.

Stack Operations

Push()   : memasukkan elemen ke dalam stack

Pop()     : menghapus/menghilangkan elemen dari stack

Top()     : menunjukkan elemen paling atas dari sebuah stack

Infix, Postfix, Prefix

Infix       : (operand) (operator) (operand)

Contoh : 4 + 5 * 8 + 2

Untuk mengubah menjadi bentuk Postfix, maka kita membaca notasi Infix dari kiri ke kanan.

Sedangkan untuk mengubah menjadid bentuk Prefix, maka kita melakukan sebaliknya yaitu kanan ke kiri.

Postfix  : (operand) (operand) (operator)

Contoh : 4 5 8 * + 2 +

Prefix    : (operator) (operand) (operand)

Contoh : + 4 + * 5 8 2

Depth First Search

DFS adalah algoritma untuk mencari sebuah elemen di dalam sebuah graph atau tree. Algoritma ini akan terus berjalan sampai menemukan elemen tersebut sebelum melakukan backtrack (recursive).

Queue

Queue juga dapat diimplementasikan menggunakan array atau linked list.

Pada array, digunakan 2 variabel untuk menandakan index paling depan (FRONT) dan index paling belakang (REAR). Deletion dan Insertion dapat dilakukan di FRONT maupun REAR.

Sedangkan pada linked list, pointer START digunakan sebagai FRONT. Apabila FRONT = REAR = NULL , maka berarti queue tersebut kosong.

Queue Operations

Push()   : memasukkan elemen di index paling belakang

Pop()     : menghapus/menghilangkan elemen dari index paling depan

Front()  : menunjukkan elemen dari index paling depan

Circular Queue

Apabila sebuah array queue sudah penuh dan kita masih memasukkan sebuah data ke dalamnya, akan terjadi overflow dan data tersebut akan tersimpan di luar array.

Oleh karena itu kita membutuhkan Circular Queue dengan menambahkan kondisi apabila index sudah mencapai index max, maka kembali ke index awal.

Breadth First Search

Algoritma untuk mencari elemen di sebuah tree atau graph. Algoritma akan terus berjalan mengunjungi setiap node di setiap level dan node yang bertetangga.