Queue dan Stack: Struktur Data Berbasis Antrian dan Tumpukan di Python

Dalam dunia pemrograman, Queue dan Stack adalah dua jenis struktur data yang sangat penting dan sering digunakan. Kedua struktur data ini memiliki cara penyimpanan dan pengambilan elemen yang berbeda. Dalam artikel ini, kita akan membahas Queue (antrian) dan Stack (tumpukan) di Python, perbedaan antara keduanya, serta cara implementasinya dalam Python.

Apa Itu Queue dan Stack?

Queue (Antrian)

Queue adalah struktur data yang mengikuti prinsip FIFO (First In, First Out). Ini berarti elemen yang pertama kali dimasukkan ke dalam antrian akan menjadi elemen pertama yang diambil. Bayangkan antrian di kasir supermarket, di mana orang yang pertama kali datang adalah yang pertama kali dilayani.

Prinsip kerja Queue:

1. Enqueue: Menambahkan elemen ke dalam antrian (biasanya dilakukan di akhir).
2. Dequeue: Mengambil elemen dari antrian (biasanya dilakukan di depan).

Stack (Tumpukan)

Stack adalah struktur data yang mengikuti prinsip LIFO (Last In, First Out). Dalam stack, elemen yang terakhir dimasukkan adalah yang pertama kali diambil. Ini seperti tumpukan piring, di mana piring yang terakhir diletakkan di atas adalah yang pertama kali diambil.

Prinsip kerja Stack:

1. Push: Menambahkan elemen ke dalam tumpukan (biasanya dilakukan di atas).
2. Pop: Mengambil elemen dari tumpukan (biasanya dilakukan dari atas).

Queue di Python

Di Python, kita bisa mengimplementasikan queue menggunakan struktur data built-in seperti list atau collections.deque. Meskipun kita bisa menggunakan list, struktur data deque dari modul collections lebih efisien karena operasi enqueue dan dequeue pada list dapat memakan waktu O(n) jika dilakukan di awal list, sementara deque mendukung operasi tersebut dalam waktu O(1).

1. Menggunakan collections.deque untuk Implementasi Queue

Modul collections menyediakan deque, yang dirancang untuk efisiensi dalam operasi di kedua ujung struktur data (baik di depan maupun di belakang).

from collections import deque

# Membuat Queue (antrian)
queue = deque()

# Enqueue: Menambahkan elemen ke belakang antrian
queue.append('A')  # Menambahkan A ke dalam antrian
queue.append('B')  # Menambahkan B ke dalam antrian
queue.append('C')  # Menambahkan C ke dalam antrian

print("Queue setelah enqueue:", queue)

# Dequeue: Mengambil elemen dari depan antrian
first_element = queue.popleft()  # Mengambil A dari antrian
print(f"Elemen yang dikeluarkan (dequeue): {first_element}")
print("Queue setelah dequeue:", queue)

Output:

Queue setelah enqueue: deque(['A', 'B', 'C'])
Elemen yang dikeluarkan (dequeue): A
Queue setelah dequeue: deque(['B', 'C'])

Pada contoh di atas, kita menggunakan metode append() untuk menambahkan elemen ke belakang queue (enqueue), dan popleft() untuk mengeluarkan elemen dari depan queue (dequeue).

2. Menggunakan List untuk Implementasi Queue

Walaupun tidak seefisien deque, kita bisa menggunakan list untuk implementasi queue. Namun, perlu diperhatikan bahwa menghapus elemen pertama dengan pop(0) di list Python akan memiliki waktu eksekusi O(n), karena semua elemen lainnya harus digeser.

# Menggunakan list untuk Queue
queue = []

# Enqueue
queue.append('A')  # Menambahkan A ke dalam antrian
queue.append('B')  # Menambahkan B ke dalam antrian
queue.append('C')  # Menambahkan C ke dalam antrian

print("Queue setelah enqueue:", queue)

# Dequeue
first_element = queue.pop(0)  # Mengambil A dari antrian
print(f"Elemen yang dikeluarkan (dequeue): {first_element}")
print("Queue setelah dequeue:", queue)

Output:

Queue setelah enqueue: ['A', 'B', 'C']
Elemen yang dikeluarkan (dequeue): A
Queue setelah dequeue: ['B', 'C']

Namun, menggunakan list untuk queue dengan operasi pop(0) tidak direkomendasikan untuk aplikasi yang membutuhkan efisiensi tinggi, karena akan menggeser seluruh elemen setelah operasi pop(0).

Stack di Python

Stack lebih mudah diimplementasikan menggunakan list di Python, karena list mendukung operasi append() untuk menambah elemen di atas stack (push) dan pop() untuk menghapus elemen dari atas stack (pop) dengan waktu O(1).

1. Menggunakan List untuk Implementasi Stack

# Menggunakan list untuk Stack
stack = []

# Push: Menambahkan elemen ke dalam stack
stack.append('A')  # Menambahkan A ke stack
stack.append('B')  # Menambahkan B ke stack
stack.append('C')  # Menambahkan C ke stack

print("Stack setelah push:", stack)

# Pop: Mengambil elemen dari stack
top_element = stack.pop()  # Mengambil C dari stack
print(f"Elemen yang dikeluarkan (pop): {top_element}")
print("Stack setelah pop:", stack)

Output:

Stack setelah push: ['A', 'B', 'C']
Elemen yang dikeluarkan (pop): C
Stack setelah pop: ['A', 'B']

Pada contoh di atas, kita menggunakan append() untuk melakukan operasi push dan pop() untuk operasi pop. Stack akan selalu mengambil elemen yang paling terakhir dimasukkan.

Perbedaan antara Queue dan Stack

Kapan Harus Menggunakan Queue dan Stack?

Gunakan Queue ketika:

• Anda ingin mengelola data yang harus diproses sesuai urutan kedatangannya (misalnya antrian pelanggan).
• Operasi pertama yang masuk harus menjadi yang pertama keluar (FIFO).

Gunakan Stack ketika:

• Anda perlu mengelola data yang diproses dengan urutan terbalik, seperti dalam algoritma rekursif, backtracking, atau implementasi undo/redo.
• Elemen yang terakhir masuk harus menjadi yang pertama keluar (LIFO).

Kesimpulan

Queue dan Stack adalah dua struktur data dasar yang sangat berguna dalam banyak aplikasi komputer. Queue sering digunakan dalam pengolahan antrian data atau pemrosesan tugas dengan urutan tertentu (FIFO), sedangkan Stack banyak digunakan dalam pengelolaan data yang membutuhkan urutan terbalik, seperti dalam algoritma rekursi dan undo/redo (LIFO). Python memberikan kemudahan dalam mengimplementasikan keduanya, baik dengan menggunakan list atau deque dari modul collections, tergantung pada kebutuhan efisiensi dan penggunaan.

Pemahaman yang baik tentang cara kerja dan aplikasi Queue dan Stack akan sangat membantu dalam menyelesaikan berbagai masalah algoritma dan desain perangkat lunak.

source: chatgpt