Stak (datastruktur) Implementering i en liste | Implementering i en tabel | Navigationsmenu4808341-0
Datastrukturer
datalogidatastrukturkølisteprogrammeringssprog
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003ELuku003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="da" dir="ltr"u003Eu003Cpu003EI u003Ca href="/wiki/Wikipedia:Fokusm%C3%A5ned/marts_2019" title="Wikipedia:Fokusmåned/marts 2019"u003Emarts 2019u003C/au003E fokuserer vi på u003Cbu003Eu003Ca href="/wiki/Kategori:Mad_og_drikke" title="Kategori:Mad og drikke"u003Emad og drikkeu003C/au003Eu003C/bu003E.u003Cbr /u003EDu kan desuden deltage i årets u003Ciu003Eu003Ca href="/wiki/Bruger:Ramloser/for%C3%A5rskonkurrence_2019" title="Bruger:Ramloser/forårskonkurrence 2019"u003Eforårskonkurrenceu003C/au003Eu003C/iu003E.nu003Ciu003Eu003Csmallu003E(u003Ca href="/wiki/Hj%C3%A6lp:Sitenotice" title="Hjælp:Sitenotice"u003ELæs her om sitenoticeu003C/au003E)u003C/smallu003Eu003C/iu003Enu003C/pu003Eu003C/divu003Eu003C/divu003Eu003C/divu003E";());
Stak (datastruktur)
Spring til navigation
Spring til søgning
For alternative betydninger, se Stak. (Se også artikler, som begynder med Stak)
For alternative betydninger, se Stak. (Se også artikler, som begynder med Stak)En stak er i datalogi en datastruktur, hvor dataelementerne er placeret (i det mindste logisk, om ikke faktisk) oven på hinanden. Det er kun det øverste element, der er tilgængeligt; det vil f.eks. sige det nyest placeret på stakken. Et tilgængeligt dataelement kan fjernes, hvorefter det næstnyeste element på stakken bliver det tilgængelige element.
Stakken kan ses analogt til f.eks. en stak datalogibøger, hvor man normalt kun har adgang til den øverste bog (tyngden af de enkelte bøger gør det umuligt at håndtere flere bøger på en gang).
Den bygger på princippet først-ind-sidst-ud. Er i modsætning til en kø, der er først-ind-først-ud.
Der er tre grundlæggende:
- Push: Læg et nyt element på stakken
- Pop: Læs og fjern det øverste element fra stakken
- Peek: Læs det øverste element på stakken
De engelske navne for operationerne er de mest gængse.
Implementering i en liste |
Det er enkelt at implementere en stak i en liste.
- Push: Indsæt et element først i listen
- Pop: Fjern første element i listen
- Peek: Læs første element i listen og lad det blive i listen
Bemærk, at det ikke er nødvendigt, at gennemlæse elementerne i listen. Det betyder, ar operationerne kan udføres i konstant tid uanset stakken størrelse.
Implementering i en tabel |
Hvis stakken skal implementeres i en tabel, kan det ske på denne måde:
En variabel i indeholder nummeret på det første frie indeks. Som udgangspunkt er i nul. I de fleste programmeringssprog indekseres fra nul.
- Push: Elementet tabel[i] sættes lig det nye dataelement og i forøges med 1.
- Pop: Hvis i er nul er stakken allerede tom. Der trækkes 1 fra i.
- Peek: Læs elementet tabel[i].
Elementerne slettes ikke fysisk ved pop. Indekset fortæller blot at stakken er lavere.
| Operation | Relativ tid |
|---|---|
| Find | O(1) |
| Indsæt | O(1) |
| Slet | O(1) |
|
Kategori:
- Datastrukturer
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.060","walltime":"0.091","ppvisitednodes":"value":49,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":1596,"limit":2097152,"templateargumentsize":"value":15,"limit":2097152,"expansiondepth":"value":3,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":1,"limit":400,"timingprofile":["100.00% 72.180 1 -total"," 83.59% 60.334 1 Skabelon:Autoritetsdata"," 12.13% 8.754 1 Skabelon:Datastruktur"," 4.01% 2.893 1 Skabelon:Harflertydig"],"scribunto":"limitreport-timeusage":"value":"0.028","limit":"10.000","limitreport-memusage":"value":817616,"limit":52428800,"cachereport":"origin":"mw1267","timestamp":"20190305075642","ttl":2592000,"transientcontent":false);mw.config.set("wgBackendResponseTime":127,"wgHostname":"mw1320"););
