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.

StrukturaIdejaIz svakodnevice
stog (engl. stack)zadnji koji je ušao, prvi izlazihrpa tanjura: uzimaš onaj na vrhu
red (engl. queue)prvi koji je ušao, prvi izlazired 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.

Program
stog = []
stog.append("tanjur 1")
stog.append("tanjur 2")
stog.append("tanjur 3")
print(stog[-1])
print(stog.pop())
print(stog.pop())
print(len(stog))
Ispis
tanjur 3 tanjur 3 tanjur 2 1
Pazi

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 dequeuvozi 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 in range(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()?

Pitanje

Zašto za red koristimo deque, a ne listu s pop(0)?

Pitanje

Što radi red.append(red.popleft())?

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.

Riješi u evaluatoru

Poništi

★☆☆ lagano

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?

Ulaz
U prvom retku M. Zatim M redaka s naredbama.
Izlaz
Zbroj brojeva na popisu.
Ograničenja
1 ≤ M ≤ 100 000, 1 ≤ x ≤ 10⁶
Ulaz
5 DODAJ 3 DODAJ 8 PONISTI DODAJ 4 DODAJ 1
Izlaz
8
Riješi u evaluatoru

Menza

★★☆ srednje

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

Riješi u evaluatoru

Vrući krumpir

★★★ teže

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

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Zagrade Infokup 2013 · državno · 8. r. OŠ
  2. Red Infokup 2016 · državno · 8. r. OŠ
  3. Košara Infokup 2015 · školsko · 8. r. OŠ

8Što smo naučili

  • Stog: zadnji unutra, prvi van. U Pythonu je to lista: append, pop i [-1].
  • Red: prvi unutra, prvi van. Koristi deque: append i popleft.
  • pop(0) na listi je spor, a popleft() na deque-u je brz.
  • Krug: red.append(red.popleft()).
Najčešće greške

pop() na praznom stogu · pop(0) umjesto popleft() · zaboravljen import deque