Memahami implementasi Queue di Python

Struktur data memainkan peran kunci dalam dunia pemrograman. Mereka membantu kami mengatur data kami dengan cara yang dapat digunakan secara efisien. Queue adalah salah satu struktur data paling sederhana yang tersedia.

Pada artikel ini, kita akan belajar tentang Queue dan implementasinya di Python.

Apa itu Antrian?

Queue adalah struktur data linier yang mengikuti prinsip First In/First Out (FIFO). Ini berlawanan dengan struktur data Stack.

Antrean ini bisa kita bandingkan dengan antrean di loket tiket bioskop. Mari kita lihat ilustrasi antrian sebagai berikut.

Jika Anda mengamati antrean di konter, orang kedua dapat pergi ke konter hanya setelah orang pertama menyelesaikan pekerjaannya. Di sini orang pertama datang ke konter dan kemudian orang kedua. Jadi disini orang mengikuti prinsip FIFO (First In/First Out). Siapa pun yang datang lebih dulu, dia akan menyelesaikan pekerjaannya terlebih dahulu. Kita bisa melihat antrian serupa dalam kehidupan kita sehari-hari.

Struktur data Queue juga mengikuti prinsip yang sama. Sekarang, Anda sudah tahu apa itu antrian dan prinsipnya. Mari kita lihat operasi yang dapat dilakukan pada struktur data antrian.

Operasi dalam Antrean

Mirip dengan stack, kita akan menemukan dua operasi utama dalam struktur data antrian.

enqueue(data)

Menambahkan data baru ke antrean di bagian akhir. Bagian samping disebut belakang.

dequeue()

Menghapus data dari depan antrian. Sisi disebut depan.

Mari kita lihat ilustrasi operasi antrean untuk pemahaman yang lebih baik. Satu gambar berbicara seribu kata.

Kami dapat menulis beberapa fungsi pembantu untuk mendapatkan info lebih lanjut tentang antrean. Tidak ada batasan jumlah fungsi pembantu yang akan Anda miliki. Mari kita berpegang pada yang paling penting yang pernah disebutkan di bawah ini untuk saat ini.

belakang()

Mengembalikan elemen pertama dari akhir antrian.

depan()

Mengembalikan elemen pertama dari awal antrian.

kosong()

Mengembalikan apakah antrian kosong atau tidak.

Apakah itu tidak membosankan bagimu? Maksud saya topik konseptual.

Bagi saya Ya!

Tapi, kita tidak bisa melakukan apapun tanpa mengetahui konsepnya. Kita harus mengetahuinya secara lengkap sebelum pelaksanaannya. Jangan khawatir ini saatnya mengotori tangan kita dengan beberapa kode.

Saya menganggap Anda telah menginstal python di PC Anda jika tidak, Anda juga dapat mencoba kompiler online.

Implementasi Antrian

Menerapkan antrian tidak akan memakan waktu lebih dari 15 menit untuk seorang programmer. Setelah Anda belajar, Anda akan mengatakannya. Mungkin Anda dapat menerapkannya dalam beberapa menit setelah tutorial ini.

  Cara Mengimpor Akun Email Lama Ke Gmail

Ada beberapa cara untuk mengimplementasikan antrian dengan Python. Mari kita lihat implementasi antrian yang berbeda langkah demi langkah.

#1. Daftar

Daftar ini adalah tipe data bawaan di Python. Kami akan menggunakan tipe data daftar untuk mengimplementasikan antrian di kelas. Kami akan memandu Anda melalui berbagai langkah untuk mengimplementasikan struktur data antrean dari awal tanpa modul apa pun. Mari kita lompat ke dalamnya.

Langkah 1:

Tulis kelas yang disebut Queue.

class Queue:
	pass

Langkah 2:

Harus ada beberapa variabel untuk menyimpan data antrian di kelas. Sebut saja elemen. Dan itu daftar tentu saja.

class Queue:

	def __init__(self):
		self.elements = []

Langkah3:

Untuk memasukkan data ke dalam antrian, kita membutuhkan metode di kelas. Metode ini disebut enqueue seperti yang sudah kita bahas di bagian tutorial sebelumnya.

Metode mengambil beberapa data dan menambahkannya ke antrian (elemen). Kita bisa menggunakan metode append dari tipe data list untuk menambahkan data di akhir antrian.

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

Langkah4:

Antrian harus memiliki jalan keluar. Dan itu disebut dequeue. Saya rasa Anda sudah menebak bahwa kita akan menggunakan metode pop dari tipe data daftar. Jika Anda menebak atau tidak, tepuk tangan!

Metode pop dari tipe data daftar menghapus elemen dari daftar indeks yang diberikan. Jika kami tidak memberikan indeks apa pun, maka elemen terakhir dari daftar akan dihapus.

Di sini, kita perlu menghapus elemen pertama dari daftar. Jadi, kita harus meneruskan indeks 0 ke metode pop.

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

Itu cukup untuk antrian. Namun, kita membutuhkan fungsi pembantu untuk menguji apakah operasi antrian bekerja dengan baik atau tidak. Mari kita tulis juga fungsi pembantu.

Langkah5:

Metode rear() digunakan untuk mendapatkan elemen terakhir dari antrian. Pengindeksan negatif dalam tipe data daftar membantu kita mendapatkan elemen terakhir dari antrean.

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

Langkah6:

Metode front() digunakan untuk mendapatkan elemen pertama dari antrian. Kita bisa mendapatkan elemen pertama dari antrian menggunakan indeks daftar.

class Queue:

	# ...

	def front(self):
		return self.elements[0]

Langkah7:

Metode is_empty() digunakan untuk memeriksa apakah antrian kosong atau tidak. Kami dapat memeriksa panjang daftar.

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

Fiuh! menyelesaikan bagian implementasi dari struktur data antrian. Kita perlu membuat objek untuk digunakan oleh kelas Queue.

  Cara Berbagi Lokasi Langsung Anda Di Google Maps Dengan Teman

Ayo lakukan.

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

Sekarang, kami memiliki objek Queue. Mari kita uji dengan beberapa rangkaian operasi.

  • Periksa apakah antrian kosong atau tidak menggunakan metode is_empty. Itu harus mengembalikan True.
  • Tambahkan angka 1, 2, 3, 4, 5 ke antrian menggunakan metode enqueue.
  • Metode is_empty harus mengembalikan False. Periksa.
  • Cetak elemen depan dan belakang masing-masing menggunakan metode depan dan belakang.
  • Hapus elemen dari antrian menggunakan metode dequeue.
  • Periksa elemen depan. Itu harus mengembalikan elemen 2.
  • Sekarang, hapus semua elemen dari antrian.
  • Metode is_empty harus mengembalikan True. Periksa.

Saya pikir itu cukup untuk menguji implementasi antrian kami. Tulis kode untuk setiap langkah yang disebutkan di atas untuk menguji antrean.

Apakah Anda menulis kode?

Tidak, jangan khawatir.

Periksa kode di bawah ini.

class Queue:

	def __init__(self):
		self.elements = []

	def enqueue(self, data):
		self.elements.append(data)
		return data

	def dequeue(self):
		return self.elements.pop(0)

	def rear(self):
		return self.elements[-1]

	def front(self):
		return self.elements[0]

	def is_empty(self):
		return len(self.elements) == 0

if __name__ == '__main__':
	queue = Queue()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

Saya pikir Anda menjalankan program di atas. Anda bisa mendapatkan output yang mirip dengan hasil berikut.

True
False
1 5
2 5
True

Kita bisa langsung menggunakan tipe data daftar sebagai struktur data antrian. Implementasi antrian di atas membantu Anda lebih memahami implementasi antrian dalam bahasa pemrograman lain.

Anda juga dapat menggunakan implementasi antrian kelas di atas dalam program proyek yang berbeda hanya dengan membuat objek seperti yang kita lakukan sebelumnya.

Kami telah mengimplementasikan antrian dari awal menggunakan tipe data daftar. Apakah ada modul bawaan untuk antrian? Ya! kami memiliki implementasi antrean bawaan. Mari kita lihat mereka.

#2. deque dari koleksi

Ini diimplementasikan sebagai antrian ujung ganda. Karena mendukung penambahan dan penghapusan elemen dari kedua ujungnya, kita dapat menggunakannya sebagai tumpukan dan antrean. Mari kita lihat implementasi antrian menggunakan dequeue.

Itu diimplementasikan menggunakan struktur data lain yang disebut daftar tertaut ganda. Jadi kinerja penyisipan dan penghapusan elemen konsisten. Mengakses elemen dari daftar tertaut tengah membutuhkan waktu O(n). Kita dapat menggunakannya sebagai antrean karena tidak perlu mengakses elemen tengah dari antrean.

  Cara Mengubah Apakah Percakapan iMessage Baru Menggunakan Nomor Telepon atau Alamat Email Anda

Mari kita periksa berbagai metode yang ditawarkan dequeue kepada kita.

  • append(data) – digunakan untuk menambahkan data ke antrian
  • popleft() – digunakan untuk menghapus elemen pertama dari antrian

Tidak ada metode alternatif untuk front, rear, dan is_empty. Kami dapat mencetak seluruh antrian sebagai pengganti metode depan dan belakang. Selanjutnya, kita dapat menggunakan metode len untuk memeriksa apakah antrian kosong atau tidak.

Kami telah mengikuti serangkaian langkah untuk menguji implementasi antrian sebelumnya. Mari ikuti rangkaian langkah yang sama di sini juga.

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

Anda akan mendapatkan hasil yang mirip dengan output berikut.

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. Antrian dari antrian

Python memiliki modul built-in bernama queue yang melayani kelas bernama Queue untuk implementasi queue. Ini mirip dengan yang telah kami terapkan sebelumnya.

Pertama, mari kita checkout metode yang berbeda dari kelas Queue.

  • put(data) – menambah atau mendorong data ke antrian
  • get() – menghapus elemen pertama dari antrian dan mengembalikannya
  • empty() – mengembalikan apakah stack kosong atau tidak
  • qsize() – mengembalikan panjang antrian.

Mari terapkan antrian dengan metode di atas.

from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

Periksa output dari kode di atas.

True
False
1
2
3
Size 2
4
5
True

Ada beberapa metode lain di kelas Queue. Anda dapat menjelajahinya menggunakan fungsi bawaan dir.

Kesimpulan

Saya harap Anda telah belajar tentang struktur data antrian dan penerapannya. Itu saja untuk antrian. Anda dapat menggunakan antrean di berbagai tempat yang perlu diproses dalam urutan FIFO(First In/First Out). Gunakan antrian dalam pemecahan masalah setiap kali Anda mendapatkan kasus untuk menggunakannya.

Tertarik untuk menguasai Python? Lihat sumber belajar ini.

Selamat Coding 🙂 👨‍💻