Du veiksmai, dvi struktūros

Dvi struktūros, viena pamoka. Jos abi riboja masyvą taip, kad liktų tik du veiksmai — ir būtent dėl to ribojimo jos naudingos.

Stekas — paskutinis įėjo, pirmas išėjo

Peržiūrėjai keturis albumus ir spaudi „atgal". Grįžti turi į tą, kurį žiūrėjai paskutinį.

  push A   push B   push C        pop → C
  ┌───┐    ┌───┐    ┌───┐         ┌───┐
  │   │    │ B │    │ C │         │ B │
  │ A │    │ A │    │ B │         │ A │
  └───┘    └───┘    │ A │         └───┘
                    └───┘

Abu veiksmai liečia tik viršūnę. Slice tai daro puikiai: append prideda gale, s[:len(s)-1] nuima nuo galo. Nieko stumdyti nereikia, nes galas yra vienintelė vieta, kurią masyve keisti pigu.

Push ir Pop — O(1). Čia ginčytis nėra dėl ko.

Eilė — pirmas įėjo, pirmas išėjo

Grojaraščio „kas toliau": pridedi į galą, imi iš priekio.

Ir štai kur prasideda pamoka. Pridėti į galą pigu — tai tas pats append. Bet imti iš priekio masyve yra kaip tik tai, ką antroje pamokoje pavadinom brangiu veiksmu.

Spėk prieš skaitydamas toliau

Trys būdai išimti pirmą elementą iš []Item:

A. q = q[1:] — pastumti slice antraštę į priekį. B. copy(q, q[1:]) ir sutrumpinti — pastumti visus elementus. C. žiedinis buferis — vienas masyvas, dvi rodyklės, judančios ratu.

Prieš kitą žingsnį užsirašyk: kiek elementų pajudins kiekvienas variantas, kai iš 100 000 dydžio eilės išimsi viską?

Trečioji pamoka parodė, kad akivaizdus spėjimas gali būti neteisingas. Šitas irgi.