Implementasi Antrian(Queue) menggunakan Tumpukan(Stacks)

source: https://i.stack.imgur.com/LQJBQ.png

“Implement Queue using Stacks” atau Implementasi Antrian menggunakan Tumpukan adalah teknik di mana kita menggunakan dua stack untuk membuat struktur data queue. Algoritma ini memanfaatkan atribut stack, yaitu LIFO (Last In, First Out), untuk mengimplementasikan queue, yang memiliki atribut FIFO (First In, First Out).

Ada dua metode utama untuk mengimplementasikan queue menggunakan stack:

1. Metode 1:
— Kita memiliki dua stack, `stack1` dan `stack2`.
— Ketika kita mencoba untuk memasukkan elemen ke dalam queue (operasi `enqueue`), kita memasukkan elemen ke `stack1`.
— Ketika kita mencoba untuk menghapus elemen dari queue (operasi `dequeue`), kita memindahkan semua elemen dari `stack1` ke `stack2`, lalu menghapus elemen dari `stack2`.

2. Metode 2:
— Kita juga memiliki dua stack, `stack1` dan `stack2`.
— Ketika kita mencoba untuk memasukkan elemen ke dalam queue, kita memasukkan elemen ke `stack1`.
— Ketika kita mencoba untuk menghapus elemen dari queue, kita memindahkan elemen dari `stack1` ke `stack2` hingga `stack1` kosong.
— Kemudian, kita menghapus elemen dari `stack2`.

Berikut adalah contoh implementasi algoritma ini dalam bahasa PHP:

<?php
class QueueUsingStacks {
    private $stack1;
    private $stack2;

    public function __construct() {
        $this->stack1 = [];
        $this->stack2 = [];
    }

    public function enqueue($item) {
        array_push($this->stack1, $item);
    }

    public function dequeue() {
        if (empty($this->stack2)) {
            while (!empty($this->stack1)) {
                array_push($this->stack2, array_pop($this->stack1));
            }
        }

        if (empty($this->stack2)) {
            // Jika masih kosong, berarti antrian juga kosong
            return null;
        }

        return array_pop($this->stack2);
    }
}

// Contoh penggunaan
$queue = new QueueUsingStacks();
$queue->enqueue("Apple");
$queue->enqueue("Banana");
$queue->enqueue("Orange");

echo $queue->dequeue()."<br>"; // Output: Apple
echo $queue->dequeue()."<br>"; // Output: Banana
echo $queue->dequeue()."<br>"; // Output: Orange

output

Dalam contoh di atas, kita membuat dua array, `stack1` dan `stack2`, yang berfungsi sebagai stack.
Fungsi `enqueue` memasukkan data ke `stack1`, dan fungsi `dequeue` menghapus data dari `stack2`. Jika `stack2` kosong, kita memindahkan semua data dari `stack1` ke `stack2` sebelum menghapus data dari `stack2`.