Stack (data structure)
A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle, where elements are added (pushed) and removed (popped) only from one end called the top. Stacks support three primary operations: push (add element to top), pop (remove and return top element), and peek/top (inspect top element without removal), all in O(1) time. They are fundamental to function call management (call stack), expression evaluation (operator precedence, postfix notation), depth-first search, backtracking algorithms, and undo mechanisms in text editors.
Stack Operations, Complexities, and Implementation Comparison
| Operation | Time Complexity | Array Implementation | Linked List Implementation | Notes |
|---|---|---|---|---|
| push(x) | O(1) amortised | Increment top, assign | Create node, set head | Array may resize |
| pop() | O(1) | Return top, decrement | Return head, update head | Raises exception if empty |
| peek() / top() | O(1) | Return A[top] | Return head.data | Does not remove element |
| isEmpty() | O(1) | Check top == -1 | Check head == null | Essential guard before pop |
| size() | O(1) | Return top+1 | Maintain counter | Optional, O(n) if uncached |
| search(x) | O(n) | Linear scan | Linear traversal | Not a primary stack operation |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Queue (data structure)
A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue), mirroring a real-world waiting line. All primary operations (enqueue, dequeue, front/peek) run in O(1) time when implemented with a circular array or doubly linked list. Queues are essential for breadth-first search, CPU and disk scheduling, inter-process communication (message passing), print spooling, and buffering in streaming and network protocols.
Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicit or via recursion) to track the path. It is fundamental in computer science for solving problems involving connected components, cycle detection, and pathfinding. DFS is widely used in topological sorting, maze generation, and solving puzzles like Sudoku.
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
The term "stack" in computing derives from the physical metaphor of a stack of plates or trays where only the top item is accessible. It was formalised in computing by Friedrich Bauer and Klaus Samelson who patented a "Kellerprinzip" (cellar principle) stack-based processor architecture in Germany in 1957. The English term "stack" was used by Charles Leonard Hamblin in 1957 for his stack-based Reverse Polish Notation calculator design.