`Video Explanation: Stack Data Structure | Illustrated Data Structures`

Definition

A Stack is a linear data structure that can hold many elements. It follows the LIFO principle:

Last In, First Out

The last item added is the first one to be removed.

In a stack, you can only directly access the top element.

Think of a stack of plates 🍽️:

You remove plates from the top first.
You put new plates on top.

Stacks are commonly implemented in two ways: array-based and linked-list-based.

Implementation	How it Works
Array/List-based	Use a dynamic array, where the end of the array acts as the top of the stack.	Array: [2, 4, 7, 3] (Top is the last item in array = 3)
Linked List-based	Use nodes with pointers, where the head node can act as the top of the stack.	Linked List: 3 ➔ 7 ➔ 4 ➔ 2 (Top is the head of list = 3)

Key Operations

In this array-based example, the rightmost element is the top of the stack.

Operation	Description	Example (Javascript)
Add	Add a new element to the top	`push(5)` → Stack: [5]
Peek / Top	Return the top element without removing it	`peek()` → returns `5` but keeps it in the stack. The stack does not change: [`5`]
Remove	Remove and return the top element	`pop()` → returns `5`, Stack becomes: []
isEmpty	Check if the stack is empty	`isEmpty()` → `true` or `false`
Size	Return the number of elements in the stack	`size()` → 1
Clear	Remove all elements from the stack	`clear()` → Stack becomes: []

// Array-based Example(Javascript)
Initially: []
Push(2) ➔ [2]           // Top element is 2
Push(4) ➔ [2, 4]        // Top element is 4
Push(7) ➔ [2, 4, 7]     // Top element is 7
Push(3) ➔ [2, 4, 7, 3]  // Top element is 3
Peek() ➔ 3              // Returns the top element 3 without removing it.
Pop() ➔ Removes 3
Now the stack is: [2, 4, 7

Implementation

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

from typing import Generic, Optional, TypeVar

T = TypeVar("T")


class Stack(Generic[T]):
    def __init__(self) -> None:
        self.items: list[T] = []

    def push(self, element: T) -> None:
        self.items.append(element)

    def pop(self) -> Optional[T]:
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self) -> Optional[T]:
        if self.is_empty():
            return None
        return self.items[-1]

    def is_empty(self) -> bool:
        return len(self.items) == 0

    def size(self) -> int:
        return len(self.items)

    def clear(self) -> None:
        self.items.clear()

import java.util.ArrayList;

public class Stack<T> {
    private final ArrayList<T> items;

    public Stack() {
        this.items = new ArrayList<>();
    }

    public void push(T element) {
        items.add(element);
    }

    public T pop() {
        if (isEmpty()) {
            return null;
        }
        return items.remove(items.size() - 1);
    }

    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return items.get(items.size() - 1);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public int size() {
        return items.size();
    }

    public void clear() {
        items.clear();
    }
}

#include<vector>

template <typename T>
class Stack {
private:
    std::vector<T> items;

public:
    void push(const T& element) {
        items.push_back(element);
    }

    bool pop(T& result) {
        if (isEmpty()) {
            return false;
        }
        result = items.back();
        items.pop_back();
        return true;
    }

    bool peek(T& result) const {
        if (isEmpty()) {
            return false;
        }
        result = items.back();
        return true;
    }

    bool isEmpty() const {
        return items.empty();
    }

    int size() const {
        return static_cast<int>(items.size());
    }

    void clear() {
        items.clear();
    }
};

#include<stdbool.h>
#include<stdlib.h>

typedef struct {
    int* items;
    int size;
    int capacity;
} Stack;

Stack* stackCreate(void) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack == NULL) {
        return NULL;
    }

    stack->capacity = 4;
    stack->size = 0;
    stack->items = (int*)malloc(stack->capacity * sizeof(int));

    if (stack->items == NULL) {
        free(stack);
        return NULL;
    }

    return stack;
}

bool stackPush(Stack* stack, int element) {
    if (stack == NULL) {
        return false;
    }

    if (stack->size == stack->capacity) {
        int newCapacity = stack->capacity * 2;
        int* resizedItems = (int*)realloc(stack->items, newCapacity * sizeof(int));

        if (resizedItems == NULL) {
            return false;
        }

        stack->items = resizedItems;
        stack->capacity = newCapacity;
    }

    stack->items[stack->size] = element;
    stack->size++;
    return true;
}

bool stackPop(Stack* stack, int* result) {
    if (stack == NULL || result == NULL || stack->size == 0) {
        return false;
    }

    stack->size--;
    *result = stack->items[stack->size];
    return true;
}

bool stackPeek(const Stack* stack, int* result) {
    if (stack == NULL || result == NULL || stack->size == 0) {
        return false;
    }

    *result = stack->items[stack->size - 1];
    return true;
}

bool stackIsEmpty(const Stack* stack) {
    return stack == NULL || stack->size == 0;
}

int stackSize(const Stack* stack) {
    if (stack == NULL) {
        return 0;
    }
    return stack->size;
}

void stackClear(Stack* stack) {
    if (stack != NULL) {
        stack->size = 0;
    }
}

void stackFree(Stack* stack) {
    if (stack != NULL) {
        free(stack->items);
        free(stack);
    }
}

class Stack<T> {
  private items: T[];

  constructor() {
    this.items = [];
  }

  push(element: T): void {
    this.items.push(element);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  size(): number {
    return this.items.length;
  }

  clear(): void {
    this.items = [];
  }
}

class Stack<T> {
    private val items = mutableListOf<T>()

    fun push(element: T) {
        items.add(element)
    }

    fun pop(): T? {
        if (isEmpty()) {
            return null
        }

        return items.removeAt(items.lastIndex)
    }

    fun peek(): T? {
        if (isEmpty()) {
            return null
        }

        return items[items.lastIndex]
    }

    fun isEmpty(): Boolean {
        return items.isEmpty()
    }

    fun size(): Int {
        return items.size
    }

    fun clear() {
        items.clear()
    }
}

final class Stack<Element> {
    private var items: [Element] = []

    func push(_ element: Element) {
        items.append(element)
    }

    func pop() -> Element? {
        return items.popLast()
    }

    func peek() -> Element? {
        return items.last
    }

    func isEmpty() -> Bool {
        return items.isEmpty
    }

    func size() -> Int {
        return items.count
    }

    func clear() {
        items.removeAll()
    }
}

using System.Collections.Generic;

public class Stack<T>
{
    private readonly List<T> items;

    public Stack()
    {
        items = new List<T>();
    }

    public void Push(T element)
    {
        items.Add(element);
    }

    public T? Pop()
    {
        if (IsEmpty())
        {
            return default;
        }

        int lastIndex = items.Count - 1;
        T value = items[lastIndex];
        items.RemoveAt(lastIndex);
        return value;
    }

    public T? Peek()
    {
        if (IsEmpty())
        {
            return default;
        }

        return items[items.Count - 1];
    }

    public bool IsEmpty()
    {
        return items.Count == 0;
    }

    public int Size()
    {
        return items.Count;
    }

    public void Clear()
    {
        items.Clear();
    }
}

type Stack[T any] struct {
    items []T
}

func (s *Stack[T]) Push(element T) {
    s.items = append(s.items, element)
}

func (s *Stack[T]) Pop() (T, bool) {
    var zero T
    if s.IsEmpty() {
        return zero, false
    }

    lastIndex := len(s.items) - 1
    value := s.items[lastIndex]
    s.items = s.items[:lastIndex]
    return value, true
}

func (s *Stack[T]) Peek() (T, bool) {
    var zero T
    if s.IsEmpty() {
        return zero, false
    }

    return s.items[len(s.items)-1], true
}

func (s *Stack[T]) IsEmpty() bool {
    return len(s.items) == 0
}

func (s *Stack[T]) Size() int {
    return len(s.items)
}

func (s *Stack[T]) Clear() {
    s.items = nil
}

Time & Space Complexity

O(1) for core operations makes Stack very efficient.

Operation	Description	Time	Space
`push(x)`	Add an element to the top	O(1) amortized	O(1)
`pop()`	Remove the top element	O(1)	O(1)
`peek()`	View the top element without removing	O(1)	O(1)
`isEmpty()`	Check if the stack is empty	O(1)	O(1)
`size()`	Return the number of elements.	O(1)	O(1)
Build Stack	Add `n` elements via repeated `push`	O(n)	O(n)
Clear Stack	Remove all elements from the stack.	O(n)	O(1)
Overall Complexity	Stack used over `n` operations	O(n)	O(n)

Use Cases

Real-Life	Description
Undo operations in text editors	Each action is pushed onto a stack. Undo removes the most recent action first.
Browser back button	The most recent previous page is visited first when the user presses Back.
Plate stack in a cafeteria	Plates are added and removed from the top, which matches LIFO behavior.

Computer Science	Description	How Stack is Used
Function Call Management (Call Stack)	Every time a function is called, a stack frame is pushed onto the call stack. When the function returns, that frame is popped.	Handles nested and recursive function calls, local variables, and return locations.
Undo/Redo in Software Editors	Applications such as code editors, design tools, and text editors often allow users to undo and redo changes.	Two stacks track actions: one for undo, another for redo after undo.
Browser History Navigation	Browsers let users move back and forward between visited pages.	Stack A (back) and Stack B (forward) track navigation history.
Syntax Parsing (Compilers, IDEs)	Compilers and interpreters use stacks to parse nested tokens like braces, parentheses, or HTML tags.	Used to track nested structures and support expression parsing.
Backtracking in Solvers/Games	Games (like Sudoku or Chess engines) or constraint solvers use stack-based backtracking.	The stack stores decisions or states. When a path fails, the algorithm pops back to the previous state.

Core Algorithmic	Description	How Stack is Used
String validation	Check for matching brackets, quotes, or tags in strings	The stack stores opening characters. Closing characters pop and validate the top of the stack.
String Reversal	Reverse characters or words in a string	Characters are pushed onto the stack and then popped to build the reversed string
Decimal to binary conversion	Convert decimal numbers to binary	Remainders from division by 2 are pushed onto stack, then popped to form binary string
Palindrome checker	Check if a string reads the same forward and backward.	Push the first half of the characters, then compare by popping while traversing the second half.
Iterative tree DFS with depth tracking	Help compute tree depth or check tree balance.	Stack tracks tree nodes and their depths without using recursion.