Summary #2

Data Structure: Stack & Queue

➤ Stack
➧ Pengertian dan Analogi
Stack merupakan sebuah data structure penting yang menyimpan elemen-elemennya dengan urutan yang teratur.

Sepertinya halnya dengan sebuah tumpukan piring. Jika anda ingin mengambil sebuah piring, anda secara otomatis mengambil piring dari urutan yang paling atas (terakhir) terlebih dahulu. Begitu pula apabila anda ingin meletakkan piring yang baru, maka anda akan meletakkannya di urutan paling atas (terakhir) terlebih dahulu.

➧ Konsep
    -  Stack merupakan sebuah data structure linier yang dapat diimplementasikan menggunakan array         maupun linked list
    -  Elemen-elemen dari stack hanya bisa ditambahkan atau dihapus dari 1 ujung, yakni dari bagian           atas
    -  Data-datanya disimpan dengan cara Last In First Out (LIFO) atau bisa dibilang Terakhir                 Datang, Keluar Pertama

➧ Stack Menggunakan Array
   ⧫ Stack mempunyai 2 variabel:
      ◉ TOP   : Yang digunakan untuk menyimpan alamat dari elemen yang paling atas dari stack                                 tersebut
      ◉ MAX : Yang digunakan untuk menyimpan jumlah maksimum dari elemen-elemen yang bisa                           disimpan oleh stack tersebut
   ⧫ IF TOP = NULL, menandakan stack tersebut kosong
   ⧫ IF TOP = MAX-1, menandakan stack tersebut penuh

   ⧫ TOP = 4, menandakan akan dilakukannya proses insertion atau deletion

➧ Stack Menggunakan Linked List
   ⧫ Teknik Stack menggunakan array lebih mudah, namun kekurangannya bahwa Array harus di              deklarasikan ukurannya untuk menyimpan elemen-elemen tersebut untuk mendapatkan ukuran            yang pasti.
   ⧫ Di Stack menggunakan Linked List, setiap titik (node) memiliki 2 bagian:
      - Satu yang menyimpan data
      - Dan satu lagi yang menyimpan alamat dari node selanjutnya
   ⧫ Pointer START dalam Linked List digunakan dalam TOP
   ⧫ Semua proses insertion dan deletion dilakukan di titik (node) yang ditunjukkan oleh TOP
   ⧫ IF TOP = NULL, menandakan bahwa stack tersebut kosong

➧ Operasi-operasi Didalam Stack
   ● push(x) : menambahkan suatu item x ke datas tumpukan stack
   ● pop() : menghapus sebuah item dari atas tumpukan stack
   ● top() : menampilkan/mengembalikan item teratas dari tumpukan stack


➤ Queue 
➧ Pengertian dan  Analogi 
Sama seperti stack, queue juga menyimpan elemen-elemen datanya dalam urutan yang teratur, namun dengan cara yang berbeda.

Analoginya seperti orang yang mengantri di halte bus, atau mengantri untuk mengambil sembako. Orang yang pertama ngantri, dia juga yang akan keluar pertama.

➧ Konsep
   - Queue juga dapat diimplementasikan dengan Array ataupun Linked List
   - Elemen-elemen dalam queue ditambahkan di satu ujung yang disebut rear dan dihapus dari ujung       yang lain yang disebut front.
   - Data-datanya disimpan dalam urutan First In First Out (FIFO), atau Datang Pertama, Keluar         Pertama.

➧ Queue Menggunakan Array
   ⧫ Queue memiliki 2 variabel
      ◉ Front dan rear yang menunjukkan posisi dimana proses deletion dan insertion dapat dapat                   dilakukan masing-masing. Sebagai contoh:

           Yang dimana pada gambar diatas, front = 0, dan rear = 4

➧ Queue Menggunakan Linked List
   ⧫ Mirip seperti stack, menggunakan array lebih mudah, namun kekurangannya bahwa Array harus        di deklarasikan ukurannya untuk menyimpan elemen-elemen tersebut untuk mendapatkan ukuran        yang pasti.
   ⧫ Di Queue menggunakan Linked List, setiap elemen memiliki 2 bagian:
      - Satu yang menyimpan data
      - Dan satu lagi yang menyimpan alamat dari elemen selanjutnya
   ⧫ Pointer START pada linked list digunakan sebagai FRONT
   ⧫ Semua insertion akan dilakukan di rear dan semua deletion akan dilakukan di ujung front
   ⧫ IF FRONT = REAR = NULL, itu menandakan bahwa queue tersebut kosong

➧ Operasi-operasi didalam Queue
   ● push(x) : menambahkan item x ke bagian belakang (back) dari queue tersebut
   ● pop() : menghapus elemen pada bagian depan (front) dari queue tersebut
   ● front() : menampilkan/mengembalikan item tersepan dari queue tersebut


➤ Depth First Search
Depth First Search (DFS) merupakan sebuah algoritma untuk traversing atau searching pada tree atau suatu graph. Bermulai dari akar dari tree (atau sebuah titik pada suatu graph) dan menjelajahi sejauh mungkin di sepanjang setiap cabang sebelum backtracking.
DFS memiliki banyak fungsi, seperti mencari articulation point dan bridge pada graph, mencari komponen yang terhubung, topological sorting, dll.
DFS dapat diimplementasikan menggunakan fungsi recursive ataupun dengan cara iterative menggunakan stack, hasilnya mungkin akan sedikit berbeda pada order tertentu, namun kedua cara tersebut benar.


➤ Breadth First Search
Breadth First Search (BFS) juga merupakan sebuah algoritma unutk melakukan traversing atau searching pada tree atau graph. Bermulai dari akar suatu tree (atau sebuah titik pada suatu graph) dan menjelajahi semua titik yang bertetangga pada setiap level sampai menemukan tujuannya.
Contoh pengaplikasian BFS yakni mencari komponen yang tersambung pada graph, mencari jalur terpendek (shortest path) pada sebuah graph, metode Ford-Fulkerson untuk menghitung aliran maksimum (maximum flow), dll.


➤ Perbedaan DFS dengan BFS
DFS menggunakan stack sedangkan BFS menggunakan queue.