Stos

Stos is the term used in Polish computer science for the data structure known in English as a stack. It is a last-in, first-out (LIFO) structure in which elements are added and removed from the top. The core operations are push (insert an element on top), pop (remove and return the top element), and peek or top (look at the top element without removing it). Additional common operations include isEmpty or size to query the state of the structure.

Stos can be implemented in several ways. An array-based stack uses a contiguous array and a top index to track the current top element, which often yields fast access and compact memory. A linked-list implementation uses nodes connected by pointers, with a head or top pointer indicating the top element; this allows dynamic growth without reallocations. Stacks may be bounded (fixed capacity) or dynamic (resize as needed). Time complexity for push, pop, and top is typically O(1); however, array-based implementations may incur occasional O(n) costs during resizing.

Common uses of stos include managing function call frames during program execution (the call stack), evaluating expressions in postfix notation, implementing backtracking algorithms, and providing undo mechanisms in interactive applications. They are also used to perform depth-first search in graphs and to support recursion by simulating the call stack when direct recursion is not available.

In computer science, terms like stack overflow and stack underflow describe errors when a bounded stack becomes full or empty, respectively.