Understanding the Basics of Stacks in Programming
Concetps, Pseudocode, Examples

What is a Stack?

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

You can think of a stack like a stack of plates — you add a plate to the top and remove from the top.

Key Operations on a Stack

• push(element) – Adds an element to the top of the stack
• pop() – Removes and returns the top element of the stack
• peek() or top() – Returns the top element without removing it
• isEmpty() – Checks whether the stack is empty

Real-Life Examples

• Undo feature in text editors
• Backtracking in puzzles like mazes
• Call stack during function execution

Example 1: Pushing and Popping from Stack

initialize stack as empty list

procedure push(stack, item):
    add item to end of stack

procedure pop(stack):
    if stack is empty:
        return "Underflow"
    return remove and return last element from stack

procedure peek(stack):
    if stack is empty:
        return "Empty Stack"
    return last element in stack

# Execution
stack = []
push(stack, 10)
push(stack, 20)
push(stack, 30)
print(pop(stack))     # 30
print(peek(stack))    # 20

30
20

Question:

What happens if we call pop() on an empty stack?

Answer:

This leads to an underflow condition. In such cases, it’s a good practice to first check isEmpty() before popping.

Example 2: Reversing a String Using Stack

This is a classic problem that demonstrates how a stack can reverse the order of characters.

procedure reverse_string(input_string):
    stack = empty list

    for each character in input_string:
        push(stack, character)

    reversed_string = ""
    while stack is not empty:
        reversed_string = reversed_string + pop(stack)

    return reversed_string

# Execution
input_string = "hello"
print(reverse_string(input_string))

olleh

Question:

Why does using a stack reverse the string?

Answer:

Because a stack retrieves elements in reverse order due to its LIFO nature. The last character pushed becomes the first character popped.

Example 3: Checking Balanced Parentheses

This is a common use-case where stacks are used to verify if the opening and closing brackets are correctly balanced.

procedure is_balanced(expression):
    stack = empty list

    for each char in expression:
        if char is opening bracket:
            push(stack, char)
        else if char is closing bracket:
            if stack is empty:
                return false
            pop(stack)

    return stack is empty

# Execution
print(is_balanced("((()))"))     # true
print(is_balanced("(()"))        # false

true
false

Important Points to Remember

• Stack is best when you need to access elements in reverse order.
• It’s used extensively in recursion and function call management.
• Always check for overflow (in fixed-size stacks) and underflow (empty stacks).

Practice Questions

• Implement a stack using only arrays or lists.
• Use a stack to evaluate a postfix expression.
• Design a stack that supports finding the minimum element in O(1) time.