Chapter 5: Data Structures - Stacks

A data structure is a specialized format for organizing, processing, retrieving and storing data. Python has built-in data structures like Lists, Tuples, and Dictionaries. In this chapter, we will learn how to implement an abstract data type called a Stack using Python lists.

5.1 Introduction to Stacks

A Stack is a linear data structure that follows the LIFO (Last In First Out) or FILO (First In Last Out) principle.

Imagine a stack of plates in a cafeteria. You can only comfortably add a new plate to the top of the stack, and you can only remove the plate from the top of the stack. The plate that was added last is the first one to be removed.

Real-world analogies:

A pile of books.
The “Undo” (Ctrl+Z) feature in a text editor (undoes the most recent action first).
Browser history (clicking the “Back” button returns you to the most recently visited page).
Function call stack in programming execution.

5.2 Core Stack Operations

A typical stack data structure supports the following fundamental operations:

Push: Adding a new element to the top of the stack.
Pop: Removing and returning the top element from the stack.
Peek (or Top): Returning the top element of the stack without removing it.
isEmpty: Checking whether the stack contains any elements.
Size: Finding the number of elements currently in the stack.

Important Condition: Underflow

If you try to perform a Pop operation on an empty stack, it results in a condition known as Underflow. You must always check if the stack is empty before popping!

(Note: While some programming languages have a fixed-size stack which can lead to ‘Overflow’ if you try to push too many items, Python lists grow dynamically, so Overflow is rarely a concern unless the system runs entirely out of memory).

5.3 Implementing a Stack using Python Lists

Python does not have a built-in Stack class, but we can easily implement one using the versatile Python list. We design it so that the end of the list serves as the top of the stack.

Adding to the top (Push) is equivalent to list.append().
Removing from the top (Pop) is equivalent to list.pop().

Step-by-Step Implementation

Let’s build a programmatic stack handling system:

# Initialize an empty stack (represented by a list)
stack = []

# 1. Implementation of is_empty function
def is_empty(stk):
    if len(stk) == 0:
        return True
    else:
        return False

# 2. Implementation of Push operation (adding to the top)
def push(stk, item):
    stk.append(item)
    print(f"Pushed: {item}")

# 3. Implementation of Pop operation (removing from the top)
def pop(stk):
    if is_empty(stk):
        return "Underflow! Stack is empty."
    else:
        removed_item = stk.pop() # Removes and returns the last element
        return removed_item

# 4. Implementation of Peek operation (viewing the top element)
def peek(stk):
    if is_empty(stk):
        return "Stack is empty."
    else:
        top_index = len(stk) - 1 # The last index
        return stk[top_index]

# 5. Implementation of Display operation
def display(stk):
    if is_empty(stk):
        print("Stack is empty.")
    else:
        print("Current Stack Content:")
        # Displaying elements starting from the Top (the end of the list)
        top = len(stk) - 1
        for i in range(top, -1, -1):
            if i == top:
                print(f"{stk[i]} <-- Top")
            else:
                print(stk[i])

# 6. Implementation of Size operation
def size(stk):
    return len(stk)

Let’s Test It!

Let’s use the functions we just defined to simulate stack operations:

# Execution starts here
print("Is Stack empty?", is_empty(stack)) # Expected: True

print("--- Pushing Elements ---")
push(stack, 10)
push(stack, 20)
push(stack, 30)

print("\n--- Current Status ---")
display(stack)
# Output should look like:
# 30 <-- Top
# 20
# 10

print("Stack size:", size(stack)) # Expected: 3

print("Peek Top Element:", peek(stack)) # Expected: 30

print("\n--- Popping an Element ---")
popped_value = pop(stack)
print(f"Popped value: {popped_value}") # Expected: 30

print("\n--- Final Status ---")
display(stack)
# Output should look like:
# 20 <-- Top
# 10

By understanding Stacks, you are taking your first step into understanding complex software architectures, such as how programming languages manage function memory and evaluate expressions!

Keyboard shortcuts