Zrozumienie implementacji kolejki w Pythonie

Struktury danych odgrywają kluczową rolę w świecie programowania. Pomagają nam organizować nasze dane w sposób, który można efektywnie wykorzystać. Kolejka to jedna z najprostszych dostępnych struktur danych.

W tym artykule dowiemy się o kolejce i jej implementacji w Pythonie.

Co to jest kolejka?

Kolejka to liniowa struktura danych zgodna z zasadą FIFO (First In/First Out). Jest przeciwieństwem struktury danych Stack.

Możemy porównać kolejkę z rzeczywistą kolejką przy kasie biletowej w kinie. Zobaczmy ilustrację kolejki w następujący sposób.

Jeśli obserwujesz kolejkę przy ladzie, druga osoba może podejść do lady dopiero po tym, jak pierwsza osoba zakończy swoją pracę. Tutaj pierwsza osoba podchodzi do lady, a potem druga osoba. Więc tutaj ludzie przestrzegają zasady FIFO (First In/First Out). Kto przyjdzie pierwszy, ten pierwszy dokończy pracę. Podobne kolejki możemy zaobserwować w naszym codziennym życiu.

Struktura danych Queue jest również zgodna z tą samą zasadą. Teraz wiesz, czym są kolejki i jaka jest ich zasada działania. Zobaczmy, jakie operacje można wykonać na strukturze danych kolejki.

Operacje w kolejce

Podobnie jak w przypadku stosu, w strukturze danych kolejki znajdziemy dwie główne operacje.

kolejkować (dane)

Dodaje nowe dane do kolejki na końcu. Bok nazywa się tyłem.

usuń z kolejki ()

Usuwa dane z początku kolejki. Bok nazywa się przodem.

Zobaczmy ilustracje operacji kolejki dla lepszego zrozumienia. Jeden obraz mówi tysiąc słów.

Możemy napisać kilka funkcji pomocniczych, aby uzyskać więcej informacji o kolejce. Nie ma ograniczeń co do liczby funkcji pomocniczych, które będziesz mieć. Pozostańmy na razie przy najważniejszym, wymienionym poniżej.

tył()

Zwraca pierwszy element z końca kolejki.

przód()

Zwraca pierwszy element z początku kolejki.

jest pusty()

Zwraca informację, czy kolejka jest pusta, czy nie.

Czy to nie jest dla ciebie nudne? Mam na myśli tematy koncepcyjne.

Dla mnie tak!

Ale nie możemy nic zrobić bez znajomości pojęć. Musimy ją uzupełnić przed wdrożeniem. Nie martw się, czas pobrudzić sobie ręce jakimś kodem.

Zakładam, że masz zainstalowany Python na swoim komputerze, jeśli nie, możesz także wypróbować kompilator online.

Implementacja kolejki

Implementacja kolejki nie zajmie programiście więcej niż 15 minut. Jak się nauczysz, to powiesz. Być może uda Ci się zaimplementować go w ciągu kilku minut po tym samouczku.

Istnieje wiele sposobów implementacji kolejki w Pythonie. Zobaczmy krok po kroku różne implementacje kolejek.

# 1. Lista

Lista jest wbudowanym typem danych w Pythonie. Zamierzamy użyć typu danych list do zaimplementowania kolejki w klasie. Przeprowadzimy Cię przez różne kroki, aby zaimplementować strukturę danych kolejki od podstaw, bez żadnych modułów. Wskoczmy w to.

Krok 1:

Napisz klasę o nazwie Queue.

class Queue:
	pass

Krok 2:

Musi istnieć jakaś zmienna do przechowywania danych kolejki w klasie. Nazwijmy to elementami. I to jest oczywiście lista.

class Queue:

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

Krok 3:

Aby wstawić dane do kolejki, potrzebujemy metody w klasie. Metoda nazywa się enqueue, jak już omówiliśmy w poprzedniej części samouczka.

Metoda pobiera pewne dane i dodaje je do kolejki (elementów). Możemy użyć metody append typu danych list, aby dodać dane na końcu kolejki.

class Queue:

	# ...

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

Krok 4:

Kolejka musi mieć wyjście. I to się nazywa dequeue. Myślę, że już się domyśliłeś, że użyjemy metody pop typu danych list. Jeśli zgadłeś lub nie, na zdrowie!

Metoda pop typu danych list usuwa element z listy o podanym indeksie. Jeśli nie podaliśmy żadnego indeksu, to usuwa ostatni element listy.

Tutaj musimy usunąć pierwszy element listy. Musimy więc przekazać indeks 0 do metody pop.

class Queue:

	# ...

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

To wystarczy na kolejkę. Potrzebujemy jednak funkcji pomocniczych, aby sprawdzić, czy operacje na kolejce działają poprawnie, czy nie. Napiszmy również funkcje pomocnicze.

Krok 5:

Metoda rear() służy do pobrania ostatniego elementu kolejki. Ujemne indeksowanie w typie danych list pomaga nam uzyskać ostatni element kolejki.

class Queue:

	# ...

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

Krok 6:

Metoda front() służy do pobrania pierwszego elementu kolejki. Możemy uzyskać pierwszy element kolejki za pomocą indeksu listy.

class Queue:

	# ...

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

Krok 7:

Metoda is_empty() służy do sprawdzenia, czy kolejka jest pusta, czy nie. Możemy sprawdzić długość listy.

class Queue:

	# ...

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

Uff! zakończył część implementacyjną struktury danych kolejki. Musimy utworzyć obiekt, z którego będzie korzystać klasa Queue.

Zróbmy to.

class Queue:

	# ...

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

Teraz mamy obiekt Queue. Przetestujmy to za pomocą kilku serii operacji.

  • Sprawdź, czy kolejka jest pusta, czy nie, używając metody is_empty. Powinien zwrócić wartość True.
  • Dodaj liczby 1, 2, 3, 4, 5 do kolejki za pomocą metody enqueue.
  • Metoda is_empty powinna zwrócić wartość False. Sprawdź to.
  • Wydrukuj elementy przednie i tylne odpowiednio metodą przednią i tylną.
  • Usuń element z kolejki za pomocą metody dequeue.
  • Sprawdź element przedni. Powinien zwrócić element 2.
  • Teraz usuń wszystkie elementy z kolejki.
  • Metoda is_empty powinna zwrócić wartość True. Sprawdź to.

Myślę, że to wystarczy, aby przetestować naszą implementację kolejki. Napisz kod dla każdego kroku wymienionego powyżej, aby przetestować kolejkę.

Napisałeś kod?

Nie, nie martw się.

Sprawdź poniższy kod.

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())

Myślę, że uruchamiasz powyższy program. Możesz uzyskać dane wyjściowe podobne do następującego wyniku.

True
False
1 5
2 5
True

Możemy bezpośrednio użyć typu danych listy jako struktury danych kolejki. Powyższa implementacja kolejki pomaga lepiej zrozumieć implementację kolejki w innych językach programowania.

Możesz także użyć powyższej implementacji klasy kolejki w innym programie projektu, po prostu tworząc obiekt, tak jak zrobiliśmy to wcześniej.

Kolejkę zaimplementowaliśmy od podstaw z wykorzystaniem typu danych list. Czy są jakieś wbudowane moduły dla kolejki? Tak! mamy wbudowane implementacje kolejek. Zobaczmy je.

#2. deque z kolekcji

Jest zaimplementowany jako kolejka dwustronna. Ponieważ obsługuje dodawanie i usuwanie elementów z obu końców, możemy go używać jako stosu i kolejki. Zobaczmy implementację kolejki przy użyciu dequeue.

Jest implementowana przy użyciu innych struktur danych zwanych listą podwójnie połączoną. Tak więc wydajność wstawiania i usuwania elementów jest spójna. Dostęp do elementów ze środkowo połączonej listy zajął O(n) czasu. Możemy użyć go jako kolejki, ponieważ nie ma potrzeby dostępu do środkowych elementów z kolejki.

Sprawdźmy różne metody, które oferuje nam dequeue.

  • append(data) – służy do dodania danych do kolejki
  • popleft() – służy do usunięcia pierwszego elementu z kolejki

Nie ma alternatywnych metod dla frontu, rear i is_empty. Możemy wydrukować całą kolejkę zamiast metody front i rear. Następnie możemy użyć metody len, aby sprawdzić, czy kolejka jest pusta, czy nie.

W poprzednim kroku wykonaliśmy szereg kroków, aby przetestować implementację kolejki. Wykonajmy tę samą serię kroków również tutaj.

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)

Otrzymasz wynik podobny do następującego wyniku.

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

#3. Kolejka z kolejki

Python ma wbudowany moduł o nazwie kolejka, który obsługuje klasę o nazwie Kolejka do implementacji kolejki. Jest podobny do tego, który wdrożyliśmy wcześniej.

Najpierw sprawdźmy różne metody klasy Queue.

  • put(data) – dodaje lub wypycha dane do kolejki
  • get() – usuwa pierwszy element z kolejki i zwraca go
  • empty() – zwraca informację, czy stos jest pusty, czy nie
  • qsize() – zwraca długość kolejki.

Zaimplementujmy kolejkę za pomocą powyższych metod.

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())

Sprawdź wyjście powyższego kodu.

True
False
1
2
3
Size 2
4
5
True

W klasie Queue jest kilka innych metod. Możesz je eksplorować za pomocą wbudowanej funkcji dir.

Wniosek

Mam nadzieję, że zapoznałeś się ze strukturą danych kolejki i jej implementacją. To tyle jeśli chodzi o kolejkę. Możesz użyć kolejki w różnych miejscach, gdzie trzeba przetworzyć w kolejności FIFO (First In/First Out). Użyj kolejki w rozwiązywaniu problemów, gdy tylko pojawi się okazja, aby z niej skorzystać.

Chcesz opanować język Python? Sprawdź te zasoby edukacyjne.

Miłego kodowania 🙂 👨‍💻