Stacks

Overview

A stack is a linear data structure that stores data in a Last-In, First-Out (LIFO) order. This means that the last item added to the stack is the first one to be removed. Stacks are widely used in various scenarios, such as managing function calls, evaluating expressions, and undoing operations in software applications. Understanding stacks and how to implement them is crucial for problem-solving and algorithm development.

Structure of a Stack

A stack supports two primary operations:

Push: Adds an element to the top of the stack.
Pop: Removes and returns the element from the top of the stack. Other useful operations include:

Peek: Retrieves the top element without removing it.
isEmpty: Checks if the stack is empty.
isFull (optional in fixed-size implementations): Checks if the stack has reached its capacity.

Implementing a Stack

Using Arrays (Procedural Approach)

Push Operation:

Check if the stack is full (optional for dynamic arrays).
Increment the top pointer.
Add the new element at the top index.

Pop Operation:

Check if the stack is empty.
Retrieve the element at the top index.
Decrement the top pointer.

infoNote

Pseudocode Example

# Stack using a fixed-size array

MAX_SIZE = 10
stack = [None] * MAX_SIZE
top = -1  # Initialise stack as empty

def push(element):
    global top
    if top == MAX_SIZE - 1:
        print("Stack Overflow")
        return
    top += 1
    stack[top] = element

def pop():
    global top
    if top == -1:
        print("Stack Underflow")
        return None
    element = stack[top]
    top -= 1
    return element

Using a Linked List (Alternative Data Structure)

A stack can also be implemented using a linked list, where each node contains the data and a reference to the next node.

Push: Create a new node and link it as the new top.

Pop: Remove the top node and update the top pointer.

Using Object-Oriented Programming (OOP)

In OOP, stacks are typically implemented as classes.

lightbulbExample

Example in Python:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return "Stack Underflow"
        return self.items.pop()

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

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

Examples

infoNote

Using a Stack to Reverse a String:

def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    reversed_str = ''
    while not stack.is_empty():
        reversed_str += stack.pop()
    return reversed_str

infoNote

Checking for Balanced Parentheses:

def is_balanced(expression):
    stack = Stack()
    for char in expression:
        if char in "({[":
            stack.push(char)
        elif char in ")}]":
            if stack.is_empty():
                return False
            top = stack.pop()
            if not matches(top, char):
                return False
    return stack.is_empty()

def matches(opening, closing):
    pairs = {'(': ')', '{': '}', '[': ']'}
    return pairs[opening] == closing

Note Summary

infoNote

Common Mistakes

Not Checking for Underflow/Overflow:

Forgetting to check if the stack is empty before popping or peeking can cause errors.
In fixed-size implementations, failing to handle overflow when pushing can lead to out-of-bounds errors.

Confusing LIFO with FIFO:

Stacks follow a Last-In, First-Out order, not First-In, First-Out (FIFO). Ensure you're using the correct structure for the problem.

Off-by-One Errors:

Incorrectly initialisng or updating the top pointer can lead to missing elements or accessing invalid indices.

infoNote

Key Takeaways

A stack is a LIFO data structure with primary operations: push, pop, and peek.
Stacks can be implemented using arrays, linked lists, or as objects in OOP.
Understanding stack operations and common implementation patterns is more important than memorising code.
Practice reading, tracing, and writing stack-related code to strengthen your problem-solving skills.

Stacks Simplified Revision Notes for A-Level OCR Computer Science

Stacks

Overview

Structure of a Stack

Implementing a Stack

Using Arrays (Procedural Approach)

Push Operation:

Pop Operation:

Pseudocode Example

Using a Linked List (Alternative Data Structure)

Using Object-Oriented Programming (OOP)

Examples

Note Summary

Common Mistakes

Key Takeaways

500K+ Students Use These Powerful Tools to Master Stacks For their A-Level Exams.

Other Revision Notes related to Stacks you should explore