Strukture podataka zauzimaju ključnu poziciju u programiranju. One omogućavaju organizovanje podataka na način koji je efikasan za upotrebu. Redovi predstavljaju jednu od najosnovnijih struktura podataka.
U ovom članku ćemo se posvetiti redovima i njihovoj implementaciji u Pajtonu.
Šta je red?
Red je linearna struktura podataka koja funkcioniše po principu „prvi ušao, prvi izašao“ (FIFO – First In, First Out). On je suprotnost steku.
Red možemo zamisliti kao red ljudi koji čekaju na šalteru bioskopske blagajne. Ilustrujmo to na sledeći način:
Na šalteru, osoba koja je prva došla, prva će biti uslužena. Tek kada ona završi, sledeća osoba dolazi na red. Ljudi se ovde ponašaju po FIFO principu. Ko prvi stigne, prvi će obaviti posao. Slične situacije se mogu videti i u drugim aspektima svakodnevnog života.
Struktura podataka red sledi isti princip. Sada kada znate šta su redovi i kako funkcionišu, hajde da pogledamo operacije koje se mogu izvršavati nad redovima.
Operacije nad redom
Slično steku, i kod redova imamo dve glavne operacije:
enqueue(podaci)
Ova operacija dodaje nove podatke na kraj reda. Kraj reda se naziva rep.
dequeue()
Ova operacija uklanja podatke sa početka reda. Početak reda se naziva glava.
Radi boljeg razumevanja, pogledajmo ilustracije operacija nad redom. Jedna slika vredi hiljadu reči.
Možemo napisati i dodatne pomoćne funkcije za dobijanje više informacija o redu. Broj pomoćnih funkcija nije ograničen, ali fokusirajmo se za sada na one najvažnije, navedene u nastavku:
rear()
Vraća poslednji element u redu.
front()
Vraća prvi element u redu.
isEmpty()
Vraća informaciju o tome da li je red prazan.
Da li vam je dosadilo? Mislim na teorijske teme.
Meni jeste!
Ali, moramo savladati teoriju pre nego što pređemo na implementaciju. Bez brige, uskoro ćemo se posvetiti kodu.
Podrazumeva se da imate instaliran Pajton na računaru. Ako nemate, možete koristiti i neki online kompajler.
Implementacija reda
Implementacija reda ne bi trebalo da traje duže od 15 minuta. Kada savladate osnove, moći ćete da ga implementirate za nekoliko minuta nakon ovog uputstva.
Postoji nekoliko načina za implementaciju reda u Pajtonu. Pogledajmo različite implementacije korak po korak.
#1. Lista
Lista je ugrađeni tip podataka u Pajtonu. Koristićemo tip podataka lista za implementaciju reda unutar klase. Proći ćemo kroz različite korake za implementaciju strukture podataka red od nule, bez upotrebe dodatnih modula. Hajde da počnemo.
Korak 1:
Napišite klasu pod nazivom Queue.
class Queue: pass
Korak 2:
Potrebna nam je varijabla za čuvanje podataka u redu. Nazovimo je „elements“. Naravno, to je lista.
class Queue:
def __init__(self):
self.elements = []
Korak 3:
Da bismo ubacili podatke u red, potreban nam je metod u klasi. Metod se zove „enqueue“, kao što smo već spomenuli.
Metod prihvata podatke i dodaje ih na kraj reda („elements“). Možemo koristiti metod „append“ tipa podataka lista za dodavanje podataka na kraj.
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
Korak 4:
Red mora imati i izlaz. To se postiže pomoću metoda „dequeue“. Pretpostavljam da ste već pogodili da ćemo koristiti metod „pop“ tipa podataka lista. Ako ste pogodili, odlično!
Metod „pop“ tipa podataka lista briše element sa liste na određenom indeksu. Ako ne navedemo indeks, on briše poslednji element liste.
U ovom slučaju, želimo da obrišemo prvi element liste, pa moramo proslediti indeks 0 metodu „pop“.
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
To je sasvim dovoljno za osnovni red. Međutim, trebaju nam pomoćne funkcije da bismo testirali da li operacije nad redom rade ispravno. Napisaćemo i te pomoćne funkcije.
Korak 5:
Metod „rear()“ se koristi za dobijanje poslednjeg elementa u redu. Negativno indeksiranje u tipu podataka lista nam pomaže da dobijemo poslednji element.
class Queue:
# ...
def rear(self):
return self.elements[-1]
Korak 6:
Metod „front()“ se koristi za dobijanje prvog elementa u redu. Prvi element reda možemo dobiti pomoću indeksa liste.
class Queue:
# ...
def front(self):
return self.elements[0]
Korak 7:
Metod „is_empty()“ se koristi za proveru da li je red prazan. Možemo da proverimo dužinu liste.
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
Uf! Završili smo implementaciju strukture podataka red. Sada moramo da kreiramo objekat klase „Queue“.
Hajde da to uradimo.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Sada imamo objekat „Queue“. Testirajmo ga sa nekoliko operacija.
- Proverite da li je red prazan ili ne pomoću metoda „is_empty“. Trebalo bi da vrati True.
- Dodajte brojeve 1, 2, 3, 4, 5 u red pomoću metoda „enqueue“.
- Metod „is_empty“ bi trebalo da vrati False. Proverite.
- Odštampajte prednji i zadnji element koristeći metode „front“ i „rear“.
- Uklonite element iz reda pomoću metoda „dequeue“.
- Proverite prednji element. Trebalo bi da vrati element 2.
- Sada uklonite sve elemente iz reda.
- Metod „is_empty“ bi trebalo da vrati True. Proverite.
Mislim da je ovo dovoljno za testiranje naše implementacije reda. Napišite kod za svaki gore navedeni korak da biste testirali red.
Jeste li napisali kod?
Ako niste, ne brinite.
Pogledajte kod ispod.
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())
Pretpostavljam da pokrećete gornji program. Možete dobiti izlaz sličan sledećem rezultatu.
True False 1 5 2 5 True
Možemo direktno koristiti tip podataka lista kao strukturu podataka red. Ova implementacija pomaže vam da bolje razumete implementaciju reda u drugim programskim jezicima.
Takođe, možete koristiti ovu implementaciju klase red u drugim programima jednostavnim kreiranjem objekta, kao što smo to radili ranije.
Implementirali smo red od nule koristeći tip podataka lista. Da li postoje ugrađeni moduli za red? Da! Imamo ugrađene implementacije redova. Pogledajmo ih.
#2. deque iz kolekcija
Realizovan je kao dvostrani red (deque – double-ended queue). Pošto podržava dodavanje i uklanjanje elemenata sa oba kraja, možemo ga koristiti i kao stek i kao red. Hajde da vidimo implementaciju reda pomoću „deque“.
Implementiran je pomoću druge strukture podataka, koja se zove dvostruko povezana lista. Dakle, performanse ubacivanja i brisanja elemenata su konzistentne. Pristup elementima iz sredine dvostruko povezane liste traje O(n) vremena. Možemo ga koristiti kao red, jer nema potrebe za pristupom elementima iz sredine reda.
Pogledajmo različite metode koje nam „deque“ nudi.
- append(podaci) – koristi se za dodavanje podataka u red
- popleft() – koristi se za uklanjanje prvog elementa iz reda
Ne postoje alternative za metode „front“, „rear“ i „isEmpty“. Možemo odštampati ceo red da bismo zamenili metode „front“ i „rear“. Takođe, možemo koristiti metod „len“ da bismo proverili da li je red prazan.
Pratili smo niz koraka za testiranje implementacije reda u prethodnom primeru. Hajde da sledimo iste korake i ovde.
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)
Dobićete rezultat sličan sledećem izlazu.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Red iz modula queue
Pajton ima ugrađen modul pod nazivom „queue“, koji sadrži klasu pod imenom „Queue“ za implementaciju reda. Slična je onoj koju smo mi ranije implementirali.
Prvo, hajde da pogledamo različite metode klase „Queue“.
- put(podaci) – dodaje ili gura podatke u red
- get() – uklanja prvi element iz reda i vraća ga
- empty() – vraća da li je red prazan ili ne
- qsize() – vraća dužinu reda.
Hajde da implementiramo red sa gore navedenim metodama.
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())
Proverite izlaz gornjeg koda.
True False 1 2 3 Size 2 4 5 True
Postoje i druge metode u klasi „Queue“. Možete ih istražiti pomoću ugrađene funkcije „dir“.
Zaključak
Nadam se da ste naučili o strukturi podataka red i njenoj implementaciji. To je sve u vezi sa redovima. Možete koristiti red na različitim mestima gde je potrebno obraditi podatke po FIFO principu (prvi ušao/prvi izašao). Koristite red pri rešavanju problema kada god je to potrebno.
Da li ste zainteresovani za savladavanje Pajtona? Pogledajte ove resurse za učenje.
Srećno kodiranje 🙂 👨💻