Stack-et: i fundit brenda, i pari jashtë

I fundit brenda, i pari jashtë

Një stack (pirg) është një koleksion me një rregull të rreptë për radhën: njësia e fundit që fut është e para që nxjerr. Ai rregull ka një emër të shkurtër, LIFO, nga anglishtja last in, first out. Një stack nuk të lejon të futesh në mes; prek gjithmonë vetëm majën.

Fotografia e përditshme është një pirg pjatash. Shton një pjatë të pastër në majë, dhe kur të duhet një e merr po nga maja. Pjata në fund hyri e para dhe del e fundit. Nëse do një pjatë më poshtë, duhet të ngresh më parë ato sipër saj. Ajo pikë e vetme hyrjeje, maja, është e gjithë ideja.

Dy veprime bëjnë gjithçka. Push vendos një njësi në majë. Pop heq njësinë e majës dhe ta jep mbrapsht. Meqë të dyja veprojnë vetëm mbi majën, një stack kurrë nuk pyet "cili pozicion?", dhe kjo është ajo që e bën të shpejtë e të thjeshtë.

Ndërtimi i një stack-u nga një listë

S'të duhet asgjë e re për të bërë një stack. Një listë Python i ka tashmë dy metodat që do: .append() shton në fund, dhe .pop() heq nga fundi. Trajtoje fundin e listës si majën e stack-ut dhe je gati:

stack = []
stack.append("ha")      # push
stack.append("fli")     # push
stack.append("kodo")    # push

print(stack.pop())      # kodo   (i fundit brenda, i pari jashtë)
print(stack.pop())      # fli
print(stack.pop())      # ha

Vër re se njësitë dalin saktësisht në të kundërt të radhës në të cilën hynë. Një kujdes: pop-i nga një stack bosh nxjerr një gabim, ndaj një program i kujdesshëm kontrollon më parë, shpesh me if stack: ose duke testuar len(stack) para se të bëjë pop.

Ku shfaqen stack-et

Stack-et janë në heshtje kudo sapo e njeh formën:

• Butoni mbrapa në një shfletues web. Çdo faqe që viziton shtyhet mbi një stack. Shtypja e "mbrapa" bën pop faqen aktuale dhe të kthen te ajo e mëparshme, në radhë të kundërt me vizitat e tua.
• Komanda undo (zhbëj) në një redaktor. Çdo ndryshim shtyhet ndërsa ndodh. Undo bën pop ndryshimin më të fundit dhe e përmbys, ja pse undo ecën gjithmonë mbrapsht nëpër ndryshimet e tua.
• Stack-u i thirrjeve i vetë programit, që ndjek funksionet që po ekzekutohen tani, që të dijë ku të kthehet kur secili mbaron.

Secili prej këtyre ka nevojë për të njëjtën gjë: kthehu më parë te njësia më e fundit. Kjo është një stack, sido që të quhet në aplikacion.

Një shembull i punuar: a është një fjalë palindrom?

Një palindrom lexohet njësoj para e mbrapa, si "ana" ose "radar". Një stack jep një mënyrë të rregullt për ta kontrolluar, sepse duke shtyrë çdo shkronjë dhe pastaj duke i bërë pop të gjitha del fjala e përmbysur:

def eshte_palindrom(fjala):
    stack = []
    for shkronja in fjala:
        stack.append(shkronja)   # push çdo shkronjë

    e_permbysur = ""
    while stack:
        e_permbysur = e_permbysur + stack.pop()   # pop-i e rindërton mbrapsht

    return fjala == e_permbysur

print(eshte_palindrom("ana"))     # True
print(eshte_palindrom("python"))  # False

Cikli i parë shtyn çdo shkronjë, ndaj shkronja e fundit e fjalës përfundon në majë. Cikli while stack: pastaj bën pop derisa stack-u zbrazet, dhe meqë pop-i merr majën çdo herë, shkronjat dalin mbrapsht. Nëse drejtshkrimi i përmbysur përputhet me origjinalin, fjala është palindrom. Rregulli LIFO e bëri përmbysjen për ty, pa asnjë xhonglim me indekse.

Do ta shohësh të shpjeguar? Ja leksioni i regjistruar i Code for Albania për këtë temë.

Provo veten

1. Thuaj rregullin LIFO në një fjali, dhe shpjego pse butoni mbrapa i një shfletuesi sillet pikërisht si ai.
2. Një stack i ndërtuar mbi një listë Python përdor .append() për push dhe .pop() për të marrë njësinë e majës. Çfarë ndodh nëse bën pop nga një stack bosh, dhe si do të mbroheshe prej saj?
3. Në shembullin e palindromit, çfarë është në majë të stack-ut sapo mbaron cikli i parë, dhe pse pop-i që andej e rindërton fjalën mbrapsht?