stakoperationer

Stakoperationer (även kallade stackoperationer) är operationer som utförs på en stack, en LIFO-datalagring där det senaste tillagda elementet tas bort först. En stack används ofta som en temporär arbetsyta i programvarukomponenter och algoritmer.

De grundläggande operationerna är push, pop, topp (eller peek), isEmpty och size. Push lägger till ett element högst upp i stacken. Pop tar bort och returnerar det översta elementet. Topp/peek returnerar det översta elementet utan att ta bort det. IsEmpty kontrollerar om stacken är tom och size anger antalet element i stacken. Vissa implementationer erbjuder även clear för att tömma stacken.

Stackar kan implementeras med en dynamisk array eller en länkad lista. I en dynamisk array är push och pop i allmänhet O(1) amortiserad tid, om det behövs omallokering kan det vara O(n) vid tillväxt. I en länkad lista är push och pop vanligtvis O(1). Minne används i proportion till antalet element.

Vanliga användningsområden inkluderar:

- uttrycksutvärdering i kalkyler och kompilatorer, särskilt vid postorder- och prefixnotation

- backtracking i sök-, pussel- och representationsproblem

- hantering av funktionsanropsstapel i programkörningar och interpreters

- undo- och redo-funktioner i mjukvara

- navigationshistorik i webb- och applikationsgränssnitt