alphaPlan · Strukturat e të dhënave, algoritmet dhe web-i · Fletë përmbledhëse 03

Strukturat lineare të të dhënave

Mësoje një strukturë së pari nga kontrata e saj, pastaj përdor një stack për më i fundit i pari dhe një radhë për i pari që vjen, i pari shërbehet.

Idetë për t’u mbajtur mend

01Një tip abstrakt i të dhënave është një kontratë: çfarë veprimesh ofron dhe si sillen ato, pa përmendur si janë ndërtuar.
02Kodi që mbështetet vetëm te kontrata vazhdon të punojë kur implementimi ndryshon; kodi që fut duart te mekanizmi prishet.
03Një stack (strukturë LIFO) ndjek rregullin i fundit brenda, i pari jashtë: push vendos një njësi në majë, pop e heq njësinë e majës, dhe njësitë dalin në rend të kundërt me ardhjen.
04Një radhë ndjek rregullin FIFO: enqueue shton në fund, dequeue heq nga kreu, ndaj njësitë largohen në radhën që erdhën.
05Butoni mbrapa, undo dhe stack-u i thirrjeve janë stack-e; një radhë printimi, një listë ngjarjesh dhe çdo radhë e drejtë pritjeje janë radhë.
06Një listë Python shërben për të dyja: append dhe pop() bëjnë një stack, append dhe pop(0) bëjnë një radhë.

.append(): Push te një stack, ose enqueue në fund të një radhe; të dyja shtojnë në fund të listës.
.pop(): Heq dhe kthen njësinë e fundit, majën e stack-ut.
.pop(0): Heq dhe kthen njësinë në indeksin 0, kreun e radhës.
while stack:: Vazhdon të bëjë pop derisa stack-u të zbrazet; kontrolli i palindromit e rindërton fjalën mbrapsht kështu.
record(team), points(team): I gjithë tipi abstrakt i një tabele pikësh: jep një pikë një ekipi, raporto sa pikë ka një ekip; fjalori pas tyre është implementimi.

Kur takon një strukturë të re, mëso së pari kontratën e saj: çfarë mund të shtoj, çfarë mund të nxjerr, çfarë mund të pyes, dhe në çfarë radhe dalin gjërat mbrapsht?
Përshkruaj kontratën para se të shkruash një rresht kodi ruajtjeje, pastaj zgjidh një implementim.
Kontrollo me if stack: ose if queue: para se të bësh pop, sepse pop-i nga një strukturë bosh nxjerr një gabim.
Pyet cila radhë është e drejtë për problemin tënd: më i riu i pari është stack, më i vjetri i pari është radhë.

pop(0) mbi një listë i zhvendos të gjitha njësitë e mbetura një vend majtas, ndaj kostoja rritet me gjatësinë; për një radhë të gjatë përdor collections.deque dhe popleft().
Ndërro radhën me një stack në një radhë pritjeje dhe i fundit që vjen shërbehet i pari, gjë që asnjë radhë e drejtë s'do ta lejonte.
Kodi që i intereson sa zgjat një veprim i dallon implementimet, edhe kur kontrata është e njëjtë.

Gjete diçka të paqartë, të vjetruar ose që mund të përmirësohet? Sugjero një përmirësim