Algoritma Queue

Queue merupakan struktur data linear dan sebuah koleksi yang sekuensial. Elemen pada queue ditambahkan pada akhir (tail/rear) dan dihapus pada awal koleksi (front/head).

Operasi pada Queue

Seperti halnya antrian yang bisa kita temui sehari - hari, antrian dimulai dari belakang ke depan. Elemen pada queue ditambahkah dari belakang (rear/tail) dan keluar dari depan (front/head). Queue disebut juga sebagai FIFO, dimana yang masuk pertama kali akan keluar pertamakali juga.

Operasi Enqueue (Enter)

Enqueue adalah proses memasukkan elemen ke dalam antrian, setiap elemen paling belakang dalam sebuah antrian ditandai/disebut rear.

Operasi Dequeue (Leave)

Dequeue adalah proses dimana elemen dalam antrian keluar dari antrian tersebut dan elemen dibelakangnya maju menjadi elemen terdepan front .

Kode Program Queue

Pada contoh program berikut kamu akan menemukan banyak method - method yang sama dengan contoh program stack khususnya pada bagian method untuk Container. Disini kita akan menggunakan method - method tersebut untuk memudahkan membaca kode program. Kamu bisa menghapusnya jika tidak terlalu diperlukan.

Kerangka Program

Contoh program yang dibuat disini terdiri dari:

1. Sebuah structure struct bernama Queue untuk menyimpan data elemen antrian kita.
2. Method yang umum ditemukan pada abstract data type Container (container interface) yaitu Size(), Empty(), Clear(), dan Full().
3. Method untuk operasi queue diantaranya yaitu Enqueue(), Dequeue(), dan method tambahan Front() untuk menunjukkan elemen terdepan, Rear() untuk menunjukkan elemen paling belakang, dan New() untuk membuat antrian baru.
4. Fungsi tampilData() untuk menampilkan data pada antrian.
5. Fungsi main() yang merupakan fungsi utama program.

package main
import "fmt"

type Queue struct {
  store []interface{}
}

/* Method untuk operasi yang umum ditemukan
   di Container ditulis disini*/

/* Method operasi yang umum ditemukan
   pada operasi Queue ditulis disini*/

// Tampil data fungsi
func tampilData(q *Queue) {
}

// Fungsi utama program
func main() {
}

Method untuk Container

Empat method ini bisa kamu hapus di program yang kamu buat jika tidak terlalu diperlukan, disini hanya untuk memudahkan untuk memahami program. Kita tidak akan membuat Container Interface.

//Size method mengecek ukuran container/wadah
func (q *Queue) Size() int {
  return cap(q.store)
}

//Empty method untuk mengecek apakah store kosong
func (q *Queue) Empty() bool {
  return len(q.store) == 0
}

//Clear method untuk menghapus semua data pada store
func (q *Queue) Clear() {
  q.store = make([]interface{}, 0, q.Size())
}

/* Full method untuk mengetahui apakah container sudah full */
func (q *Queue) Full() bool {
  return q.Rear()+1 == q.Size()
}

Penjelasan dari statement dalam method - method diatas diantaranya:

1. Method Size(), digunakan untuk mengetahui ukuran maksimal dari antrian. disini kita menggunakan fungsi built in golang cap() untuk mengetahui kapasitas dalam slice store yang digunakan untuk menampung data antrian yang kita buat. Method ini akan mengembalikan nilai maksimal kapasitas yang dapat ditampung.
2. Method Empty(), digunakan untuk mengetahui apakah antrian kosong. disini kita juga menggunakan fungsi built in len() untuk mengetahui jumlah elemen pada slice store dan membandingkannya dengan 0. Method ini akan mengembalikan nilai boolean true jika tidak ada elemen dalam slice dan false jika terdapat satu atau lebih elemen dalam slice.
3. Method Clear(), digunakan untuk mengosongkan elemen pada Queue. disini kita menggunakan fungsi built in golang yaitu make() untuk membuat slice baru dengan nilai elemen 0 dan kapasitas sesuai kapasitas array yang sudah ditentukan pada program yang kita buat.
4. Method Full(), digunakan untuk mengecek apakah antrian masih bisa menampung data elemen baru. Disini kita membandingkan jumlah elemen dalam antrian (data index terakhir +1 q.Rear()+1 ) dan nilai jumlah kapasitas antrian. Method ini akan mengembalikan nilai boolean true jika elemen pada stack sudah penuh, atau false jika masih ada ruang untuk menampung data elemen dalam antrian.

Method Untuk Queue

5 Method ini merupakan method yang akan kita gunakan untuk mengakses data dan memproses data dalam queue. Kamu bisa mengurangi menjadi dua atau tiga method, tapi disini saya lebih nyaman untuk menggunakan kelima method dibawah ini.

// Rear Menunjukkan index data terakhir dalam antrian
func (q *Queue) Rear() int {
  return len(q.store) - 1
}

// Front menunjukkan index data pertama dalam antrian
func (q *Queue) Front() int {
  return 0
}

// Enqueue Memasukkan data kedalam antrian
func (q *Queue) Enqueue() {
  if q.Full() {
    fmt.Println("\nANTRIAN SUDAH PENUH !")
    return
  }

  data := "data inputan pengguna"
  fmt.Print("Masukkan data :")
  fmt.Scanln(&data)

  q.store = append(q.store, data)
}

// Dequeue mengeluarkan data dari antrian
func (q *Queue) Dequeue() {
  if q.Empty() {
    fmt.Println("Leave : data pada antrian sudah kosong")
    return
  }
  // menghapus data pertama dimasukkan
  q.store = append(q.store[:q.Front()], q.store[q.Front()+1:]...)
}

/* New method untuk membuat container
dengan kapasitas yang bisa ditampung */
func (q *Queue) New(max int) {
  q.store = make([]interface{}, 0, max)
}

Adapun penjelasan kelima method diatas yaitu:

1. Method Rear(), untuk mengetahui posisi elemen terakhir dalam antrian. Disitu kita hanya mengurangkan jumlah elemen pada antrian dengan 1. Method ini mengembalikan nilai integer yang menunjukkan posisi elemen terakhir pada antrian.
2. Method Front(), untuk menunjukkan posisi terdepan dalam antrian. Disitu kita hanya megembalikan nilai integer 0 dimana sudah umum dalam sebuah slice pada index 0 adalah index elemen paling awal.
3. Method Enqueue(), untuk menambahkan elemen baru dalam antrian.
   • di awal blok kita mengecek apakah antrian bisa menampung elemen baru if q.Full().
   • jika sudah penuh maka keluar dari fungsi (return) dan jika masih ada ruang untuk elemen baru maka lanjut ke statemen berikutnya untuk melakukan proses penambahan data.
   • Data yang akan dimasukkan kedalam antrian berupa input data dari pengguna fmt.Scanln(&data) kemudian menyimpan data tersebut kedalam antrian dengan menggunakan fungsi built in golang yaitu append(). fungsi tersebut akan menambahkan elemen ke slice store urutan akhir.
4. Method Dequeue(), untuk menghapus elemen awal dalam antrian.
   • diawal block kita mengecek apakah antrian kosong (if q.Empty()), jika kosong berti tidak ada elemen yang bisa dihapus. maka keluar dari fungsi Dequeue() menggunakan statement return.
   • Jika masih ada elemen dalam antrian maka lanjutkan ke proses penghapusan elemen paling awal.
   • sama dengan penambahan, penghapusan disini juga menggunakan fungsi built in append(). bedanya disini kita memecah nilai dalam variabel store menjadi 2 bentuk.
     • bentuk pertama yaitu slice tanpa data (index awal sampai dengan 0 ) [:q.Front()]
     • bentuk kedua yaitu slice dari index pertama hingga terakhir pada store ([q.Front()+1]:)
   • Kemudian menggabungkan kedua slice menggunakan fungsi append() dan menyimpannya kembali dalam variabel store pada antrian.
5. Method New(), untuk membuat Queue baru beserta nilai maksimal elemen dalam antrian. Slice yang dibuat bertipe interface{} Yang artinya kita bisa menyimpan data tipe apapun entah itu integer, string, boleean dll. Penentuan nilai kapasitasnya diperoleh dari variabel argumen max pada fungsi tersebut.

Fungsi untuk menampilkan data

Untuk memudahkan kita melihat bagaimana proses penambahan dan pengurangan data dalam antrian ketika program dijalankan, maka kita perlu menampilkan data setiap kali peroses dalam antrian tersebut dilakukan.

Fungsi ini pada dasarnya menampilkan pesan ketika antrian kosong dan menampilkan data baik itu semua data pada antrian dan posisi elemen Front() dan Rear() pada antrian.

// Tampil data fungsi
func tampilData(q *Queue) {
  if q.Empty() {
    fmt.Printf("\nData antrian kosong\n\n")
    return
  }
  fmt.Printf("\nData : %v \nData Front `%v` index no %d\nData Rear `%v` index no %d\n",
    q.store, q.store[q.Front()], q.Front(), q.store[q.Rear()], q.Rear(),
  )
}

Fungsi main()

Fungsi main() merupakan fungsi utama program kita, disini kita memanggil semua method dan fungsi yang telah kita buat untuk dapat kita gunakan saat program kita jalankan.

func main() {
  queue := &Queue{}
  queue.New(3)
  input := "menu inputan pengguna"
  for {
    tampilData(queue)
    fmt.Print("Masukkan perintah [e]nqueue [d]equeue [c]lear [q]uit:")
    fmt.Scanln(&input)
    switch input {
    case "e", "enqueue":
      queue.Enqueue()
    case "d", "dequeue":
      queue.Dequeue()
    case "c", "clear":
      queue.Clear()
    case "q", "quit":
      fmt.Println("Bye Bye !")
      return
    }
  }
}

Adapun argumen yang kita tulis dalam fungsi utama diantaranya:

1. membuat objek Queue menggunakan struktur yang telah kita buat sebelumnya.
2. menentukan jumlah maksimal elemen yang bisa ditampung oleh antrian menggunakan method New(), disini nilai 3 adalah maksimal elemennya. Kamu bisa merubahnya menjadi berapapun yang kamu inginkan.
3. Mendeklarasikan variabel input untuk menampung perintah yang diinputkan pengguna.
4. input perintah tersebut diambil didalam perulangan yang tak terhingga for{}, menggunakan fungsi Scanln()
5. adapun perintah yang tersedia dideklarasikan dalam block switch diantaranya yaitu, Enqueue(), Dequeue() dan Clear().
6. Dan tentunya untuk keluar dari program yaitu menggunakan statement return