Pratybos
Penkios užduotys.
1. (*History) Peek() (Item, bool)
Grąžina viršūnę jos nenuimdama.
Kodėl tai atskiras veiksmas, o ne Pop po kurio Push? Kuo skiriasi tavo
History būsena abiem atvejais?
2. Suderintos skliaustų poros
Balanced(s string) bool — patikrina, ar (), [] ir {} suderinti.
Klasikinis steko uždavinys. Kiek atminties reikia blogiausiu atveju? Įvertink per įvesties ilgį.
3. Augantis žiedas
Mūsų Ring grąžina false, kai pilnas. Perdaryk taip, kad jis augtų
dvigubai, kai prisipildo.
Suskaičiuok perkopijuotus elementus 100 000 įrašų. Palygink su 2 pamokos
append matavimu — ar skaičius tas pats? Paaiškink.
4. Eilė iš dviejų stekų
Realizuok Queue naudodamas tik du History.
Suskaičiuok, kiek elementų pajuda vienam išėmimui. Blogiausiu atveju jis O(n) — bet amortizuotai O(1). Pamatuok abu ir parodyk skirtumą.
5. Kur skaitiklis vėl apgaus
3 žingsnis parodė, kad veiksmų skaitiklis nemato atminties.
Sugalvok antrą atvejį, kurio jis nemato. Pamatuok jį kitu būdu ir parodyk, kad skaičius meluoja.
(Užuomina: du variantai gali atlikti tiek pat palyginimų ir vis tiek skirtis greičiu. Ketvirtoji pamoka apie tai neužsimena. Šeštoji — taip.)