Understanding Stacks

What Is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last item added to the stack is the first one removed.

Real-Life Examples of a Stack

• A stack of plates — you remove the top plate first

• Browser navigation (Back button)

• Undo/Redo features in editors

These examples show how natural and intuitive stack behavior is.

How a Stack Works

A stack supports two main operations:

• Push: Add an element to the top of the stack

• Pop: Remove the top element

Other common operations include:

• Peek/Top: View the top element without removing it

• IsEmpty: Check if the stack is empty

Visual Representation of a Stack

Top -> [30]
        [20]
        [10]
Bottom

If you push 40:

Top -> [40]
        [30]
        [20]
        [10]
Bottom

If you pop:

Top -> [30]
        [20]
        [10]
Bottom

Implementing a Stack Using an Array

public class Stack
{
    private int[] items;
    private int top;

    public Stack(int size)
    {
        items = new int[size];
        top = -1;
    }

    public void Push(int value)
    {
        items[++top] = value;
    }

    public int Pop()
    {
        return items[top--];
    }

    public int Peek()
    {
        return items[top];
    }

    public bool IsEmpty()
    {
        return top == -1;
    }
}

Array-based stacks are fast but fixed in size.

Implementing a Stack Using a Linked List

public class Node
{
    public int Data;
    public Node Next;
}

public class LinkedStack
{
    private Node top;

    public void Push(int value)
    {
        Node newNode = new Node { Data = value, Next = top };
        top = newNode;
    }

    public int Pop()
    {
        int value = top.Data;
        top = top.Next;
        return value;
    }

    public int Peek()
    {
        return top.Data;
    }

    public bool IsEmpty()
    {
        return top == null;
    }
}

Linked list stacks grow dynamically, making them flexible.

Time Complexity of Stack Operations

All basic operations take O(1) time:

• Push

• Pop

• Peek

• IsEmpty

This makes stacks very efficient.

Real-Life Applications of Stacks

Stacks are used everywhere in computer science:

1. Function Call Stack

Every time a function calls another function, it is added to the stack.
When the function returns, it is removed.

2. Undo/Redo in Editors

Your last action is stored on a stack.
Pressing undo pops it.

3. Balanced Parentheses Problem

Used in compilers and expression validation.

4. Expression Conversion

• Infix ? Postfix

• Postfix ? Evaluation

5. Browser Back Button

Pages you visit are stored in a stack.

Example: Checking for Balanced Parentheses

bool IsBalanced(string expr)
{
    Stack<char> stack = new Stack<char>();

    foreach (char c in expr)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            stack.Push(c);
        }
        else if (c == ')' || c == ']' || c == '}')
        {
            if (stack.Count == 0) return false;

            char top = stack.Pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '['))
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

Summary

Stacks are simple yet powerful. They form the foundation of many advanced algorithms and system behaviors.

Key takeaways:

• Follows the LIFO principle

• Push and pop happen at the top

• Very fast operations (O(1))

• Used in recursion, expression evaluation, undo/redo, and browser navigation