Data Structure and Algorithms - Stacks

Resources:

T. H. Cormen, Ed., Introduction to algorithms, 2nd. ed., 10th pr. Cambridge, Mass.: MIT Press [u.a.], 2007.
M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data structures and algorithms in Java, 6. ed. Hoboken, NJ: Wiley, 2014.
“Introduction to Stacks,” Emory.edu, 2026. https://mathcenter.oxford.emory.edu/site/cs171/stacks/ (accessed Jan. 31, 2026).
C. to, “abstract data type,” Wikipedia.org, Dec. 04, 2001. https://en.wikipedia.org/wiki/Stack_(abstract_data_type) (accessed Jan. 31, 2026).
“W3Schools.com,” W3schools.com, 2026. https://www.w3schools.com/dsa/dsa_data_stacks.php (accessed Jan. 31, 2026).
GeeksforGeeks, “Basic Operations in Stack Data Structure,” GeeksforGeeks, Jul. 07, 2023. https://www.geeksforgeeks.org/dsa/basic-operations-in-stack-data-structure-with-implementations/ (accessed Jan. 31, 2026).

1. What is Stack?

A Stack is one of the most fundamental linear data structures in computer science. If you’ve ever piled up a stack of cafeteria trays or used the “Undo” button in a text editor, you’ve already interacted with a stack in the real world.

A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means the last element added to the stack is the first one to be removed. Think of it like a stack of books: you place a new book on top, and if you want to take one out, you take the one from the top first.

2. Core Operations of a Stack

To be considered a stack, a data structure must support these primary operations:

Push: Adds an element to the top of the stack.
Pop: Removes the topmost element from the stack.
Peek (or Top): Returns the value of the top element without removing it.
isEmpty: Checks if the stack is empty.
isFull: (In fixed-size arrays) Checks if the stack has reached its capacity.

3. How it Works?

The stack maintains a pointer (often called top) that keeps track of the index of the last element added.

When you Push, the top pointer increments, and the new element is placed at that position.
When you Pop, the element at the top is removed (or returned), and the top pointer decrements.

4. Complexity Analysis

Because we only ever interact with the “top” of the data structure, stacks are incredibly efficient:

Time Complexity: All basic operations (Push, Pop, Peek) are O(1).
Space Complexity: O(n), where n is the number of elements stored.

5. Real-World Applications

Function Calls (The Call Stack): Modern programming languages use a stack to manage active functions. When a function is called, it’s pushed onto the stack; when it finishes, it’s popped.
Expression Evaluation: Used by compilers to evaluate mathematical expressions (like converting Infix to Postfix).
Backtracking: Used in algorithms to solve puzzles like mazes or the N-Queens problem.
Undo/Redo: Your browser history and text editors use stacks to track your previous states.

6. Code Implementation

Github Link: https://github.com/computingnotes/DataStructureAndAlgorithms/blob/main/DSA_Stacks.ipynb

Data Structure and Algorithms – Stacks