Stack vs Queue
Stack er en ordnet liste, hvor indsættelse og sletning af listeelementer kun kan udføres i den ene ende kaldet toppen. På grund af denne grund betragtes stakken som en Last in First out (LIFO) datastruktur. Kø er også en ordnet liste, hvor indsættelse af listeelementer udføres i den ene ende kaldet bagsiden, og sletning af elementer udføres i den anden ende kaldet forsiden. Denne indsættelses- og sletningsmekanisme gør køen til en First in First out (FIFO) datastruktur.
Hvad er Stack?
Som tidligere nævnt er stak en datastruktur, hvor elementer tilføjes og fjernes fra kun den ene ende kaldet toppen. Stabler tillader kun to grundlæggende operationer kaldet push og pop. Trykoperationen tilføjer et nyt element til toppen af stakken. Pop-operationen fjerner et element fra toppen af stakken. Hvis stakken allerede er fuld, når en push-operation udføres, betragtes det som et stak-overløb. Hvis en pop-handling udføres på en allerede tom stak, betragtes det som et stak underflow. På grund af det lille antal operationer, der kan udføres på en stak, betragtes det som en begrænset datastruktur. I overensstemmelse med den måde, push- og pop-operationerne er defineret, er det desuden klart, at elementer, der blev tilføjet sidst i stakken, går først ud af stakken. Derfor betragtes stakken som en LIFO-datastruktur.
Hvad er kø?
I en kø tilføjes elementer fra den bagerste del af køen og fjernes fra den forreste del af køen. Da de elementer, der tilføjes først, fjernes fra køen først, bevarer den FIFO-rækkefølgen. På grund af denne rækkefølge af tilføjelse og fjernelse af elementer, repræsenterer kø ideen om en betalingslinje. Generelle operationer, der understøttes af en kø, er en-kø- og de-kø-operationer. En-kø-operation vil tilføje et element bagerst i køen, mens de-kø-operationen fjerner et element fra forsiden af køen. Generelt har køer ikke en begrænsning på antallet af elementer, der kan tilføjes til køen udover hukommelsesbegrænsningerne.
Hvad er forskellen mellem stak og kø?
Selv om både stakke og køer er slags ordnede lister, har de nogle vigtige forskelle. I stakke kan tilføjelse eller sletning af elementer kun ske fra den ene ende kaldet toppen, mens i køer tilføjes elementer fra den ene ende kaldet bagsiden, og sletning af elementer udføres fra den anden ende kaldet forsiden. I en stak vil elementer, der er tilføjet sidst til stakken, blive fjernet først fra stakken. Derfor betragtes stakken som en LIFO-datastruktur. I køer vil elementer, der tilføjes først, blive fjernet fra køen først. Derfor betragtes køen som en FIFO-datastruktur.
Relateret link:
Forskel mellem stak og bunke
