Stackar
↑Snabböversikt
Section titled “Snabböversikt”En stack följer LIFO: sist in, först ut. Det senast tillagda värdet tas bort först.
| Operation | Vad händer? | Typisk tid |
|---|---|---|
| Push | Lägg till ett värde | O(1) amorterat |
| Pop | Ta bort från toppen | O(1) |
| Peek | Läs nästa värde utan att ta bort det | O(1) |
Prova operationerna
Section titled “Prova operationerna”Prova själv
Senast in först ut (LIFO)
Vi lägger till och tar bort i toppen. Det senast tillagda värdet lämnar först.
Så fungerar ordningen
Section titled “Så fungerar ordningen”- Lägg till flera värden i följd.
- Titta på nästa värde. Det ligger överst på stacken.
- Ta bort ett värde. Nästa värde ändras, men de andra ligger kvar i sin ordning.
- Fortsätt tills samlingen är tom.
var items = new Stack<int>();items.Push(10);items.Push(20);Console.WriteLine(items.Peek()); // 20Console.WriteLine(items.Pop()); // 20#include <stack>#include <iostream>std::stack<int> items;items.push(10);items.push(20);std::cout << items.top() << '\n'; // 20items.pop(); // pop returns void in C++När använder man den?
Section titled “När använder man den?”Stackar passar ångrahistorik, djupet-först-sökning och tolkning av nästlade uttryck. Även rekursiva anrop hanteras med en anropsstack.
Viktig regel
Section titled “Viktig regel”En vanlig stack tar bort objektet som ligger överst. Det är LIFO: sist in, först ut. Stacken sorterar inte värden. Den bevarar ordningen som du lade in objekten i.
Vanliga användningar
Section titled “Vanliga användningar”Stackar används bland annat för ångra-funktioner, parsning, djupet-först-sökning och metodanrop. En webbläsares bakåtknapp liknar en stack, men verklig webbläsarhistorik fungerar mer avancerat.
Resurskostnad
Section titled “Resurskostnad”Push och pop är normalt konstanta operationer. En arraybaserad stack kan ibland behöva allokera större lagring, men insättningar blir ofta amorterat konstanta. Kontrollera alltid fallet där stacken är tom.