Python stazaCjelina 5 · Strukture podataka (napredno)Lekcija 30
Stog i red (stack i queue)
Hrpa tanjura i red u menzi: dvije jednostavne ideje koje rješavaju iznenađujuće mnogo zadataka. Prva lekcija napredne cjeline.
Pythonoko 50 minuta4 zadatka za evaluator
1Nova cjelina: alati za podatke
Napredna cjelina
Ova cjelina je dodatak za učenike koji su prošli cjeline 1–4 i žele znati još više. Za natjecanja u osnovnoj školi cjeline 1–4 su dovoljne: s njima se može doći do samog vrha državnog natjecanja.
Ovdje učimo gotove alate koji neka rješenja čine kraćima i bržima. Isti alati postoje i u C++-u (stack, queue, deque, map, priority_queue), pa će ti kasnije biti lakše ako prijeđeš na C++.
Dosad smo podatke spremali u liste, rječnike i skupove. Za neke zadatke postoje posebne strukture koje određeni posao rade puno jednostavnije ili puno brže. U ovoj lekciji upoznajemo dvije: stog i red.
Struktura
Ideja
Iz svakodnevice
stog (engl. stack)
zadnji koji je ušao, prvi izlazi
hrpa tanjura: uzimaš onaj na vrhu
red (engl. queue)
prvi koji je ušao, prvi izlazi
red u menzi: prvi dođe, prvi je poslužen
2Stog: lista kojoj diramo samo kraj
Za stog u Pythonu ne treba ništa novo: to je obična lista kojoj dodajemo i uzimamo samo na kraju. stog.append(x) stavlja x na vrh, stog.pop() skida i vraća element s vrha, a stog[-1] samo gleda vrh. Uvjet if stog: je istinit kad stog nije prazan.
pop() na praznoj listi javlja grešku. Prije skidanja provjeri if stog:.
3Stog u akciji: zagrade
Klasičan zadatak za stog: jesu li zagrade u izrazu ispravno zatvorene? Otvorene zagrade stavljamo na stog. Kad naiđe zatvorena, na vrhu stoga mora biti njezin par. Na kraju stog mora biti prazan.
z–
stog–
dobro–
Klikni „Sljedeći korak“ i prati što se događa.
Ključna ideja
Stog pamti „što je još otvoreno”, a uvijek nas zanima samo ono što je otvoreno zadnje. To je znak da treba stog.
4Red: deque
Red bismo mogli napraviti listom: dodajemo s append, a uzimamo s početka s pop(0). Ali pop(0) je spor: nakon njega Python mora pomaknuti sve ostale elemente za jedno mjesto. Za red od 100 000 ljudi to je 100 000 pomicanja za svakog posluženog.
Zato Python ima deque (čita se „dek”, od engl. double-ended queue, red s dva kraja) iz modula collections. Dodavanje i uzimanje s oba kraja je brzo.
Naredba
Što radi
from collections import deque
uvozi deque (jednom, na početku programa)
red = deque()
prazan red
red.append(x)
dodaje x na kraj
red.popleft()
skida i vraća prvi element
red.appendleft(x)
dodaje x na početak
red.pop()
skida i vraća zadnji element
red[0]
gleda prvi element
Program
from collections import deque
red = deque()
red.append("Ana")
red.append("Ivo")
red.append("Mia")
print(red.popleft(), "je poslužena")
red.append("Luka")
print(len(red), "čekaju")
print("Sljedeći je", red[0])
Ispis
Ana je poslužena
3 čekaju
Sljedeći je Ivo
Pazi
Ime je popleft, a ne pop_left ili popLeft.
5Red u krug
Djeca stoje u krugu i dodaju loptu. Krug je red u kojem onaj s početka odlazi na kraj: red.append(red.popleft()). Tako možemo simulirati igre u krugu.
Program
from collections import deque
red = deque([1, 2, 3, 4, 5])
for korak inrange(3):
red.append(red.popleft())
print(list(red))
Ispis
[4, 5, 1, 2, 3]
Stani i razmisli
Što ispisuje program ako umjesto 3 koraka napravimo 5?
Pogledaj odgovor
Opet [1, 2, 3, 4, 5]. Nakon 5 koraka svatko je jednom otišao na kraj, pa je krug isti kao na početku.
Na natjecanju
U Pythonu na natjecanju smiješ koristiti cijelu standardnu biblioteku: collections, heapq i bisect su uvijek dostupni.
6Provjeri se
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Pitanje
Na stog su redom stavljeni 1, 2 i 3. Što vraća pop()?
Stog: zadnji unutra, prvi van.
Pitanje
Zašto za red koristimo deque, a ne listu s pop(0)?
pop(0) je spor za dugačke liste; popleft() na deque-u je brz.
Pitanje
Što radi red.append(red.popleft())?
Tako simuliramo krug.
7Zadaci
Zagrade
★★☆ srednje
Zadan je niz zagrada (), [] i {}. Jesu li ispravno zatvorene? Svaka zatvorena zagrada mora zatvoriti zadnju još otvorenu zagradu iste vrste, a na kraju sve moraju biti zatvorene.
Ulaz
Jedan redak s nizom zagrada.
Izlaz
DA ili NE.
Ograničenja
1 ≤ duljina ≤ 100 000
Ulaz
{[]}()
Izlaz
DA
Ulaz
([)]
Izlaz
NE
Treba ti pomoć?
Kao u primjeru iz lekcije, samo s tri vrste zagrada. Rječnik par kaže koja otvorena pripada kojoj zatvorenoj.
Na početku je popis prazan. Naredba DODAJ x dodaje broj x, a naredba PONISTI briše zadnji dodani broj koji još nije poništen. PONISTI dolazi samo kad popis nije prazan. Koliki je zbroj brojeva na popisu nakon svih naredbi?
Naredba DOLAZI ime stavlja učenika na kraj reda u menzi, a POSLUZI poslužuje prvog u redu. Za svaki POSLUZI ispiši ime posluženog. POSLUZI dolazi samo kad netko čeka.
Ulaz
U prvom retku M. Zatim M redaka s naredbama.
Izlaz
Imena posluženih, svako u svom retku.
Ograničenja
1 ≤ M ≤ 400 000
Ulaz
5
DOLAZI Ana
DOLAZI Ivo
POSLUZI
DOLAZI Mia
POSLUZI
Izlaz
Ana
Ivo
Treba ti pomoć?
S listom i pop(0) program je točan, ali za stotine tisuća naredbi prespor. Upotrijebi deque i popleft().
N djece, označene od 1 do N, stoji u krugu, a krumpir je kod djeteta 1. Krumpir se doda K puta, svaki put sljedećem djetetu u krugu. Dijete kod kojeg je tada krumpir ispada, a krumpir dobiva sljedeće dijete. Igra traje dok ne ostane jedno dijete. Koje?
Ulaz
Jedan redak s brojevima N i K.
Izlaz
Oznaka djeteta koje ostane.
Ograničenja
1 ≤ N ≤ 5000, 1 ≤ K ≤ 300
Ulaz
5 2
Izlaz
4
Treba ti pomoć?
Djeca su u deque-u, a krumpir je kod onoga na početku. Dodavanje: append(popleft()). Ispadanje: popleft().