Stacks

This lesson covers stacks — an essential abstract data type (ADT) in the OCR A-Level Computer Science (H446) specification. Stacks are used extensively in computing, from function call management to expression evaluation.

---

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last item added to the stack is the first item to be removed — like a stack of plates.

Real-World Analogies

• A stack of plates: you add to the top and take from the top.
• The "Back" button in a browser: returns to the most recently visited page.
• An undo feature: reverts the most recent action first.

---

Stack Operations

Operation	Description	Time Complexity
push(item)	Add an item to the top of the stack	O(1)
pop()	Remove and return the top item	O(1)
peek() / top()	Return the top item without removing it	O(1)
isEmpty()	Check whether the stack is empty	O(1)
isFull()	Check whether the stack is full (array-based only)	O(1)
size()	Return the number of items in the stack	O(1)

---

Array-Based Implementation

The most common implementation uses an array and a top pointer (an integer tracking the index of the top element).

Pseudocode (OCR Style)

const MAX_SIZE = 10
array stack[MAX_SIZE]
top = -1                 // -1 indicates empty stack

function push(item)
    if top == MAX_SIZE - 1 then
        print("Stack Overflow")
    else
        top = top + 1
        stack[top] = item
    end if
end function

function pop()
    if top == -1 then
        print("Stack Underflow")
        return null
    else
        item = stack[top]
        top = top - 1
        return item
    end if
end function

function peek()
    if top == -1 then
        print("Stack is empty")
        return null
    else
        return stack[top]
    end if
end function

function isEmpty()
    return top == -1
end function

Python Implementation

class ArrayStack:
    def __init__(self, max_size):
        self.stack = [None] * max_size
        self.max_size = max_size
        self.top = -1

    def push(self, item):
        if self.top == self.max_size - 1:
            raise OverflowError("Stack Overflow")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.top == -1:
            raise IndexError("Stack Underflow")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.top == -1:
            return None
        return self.stack[self.top]

    def is_empty(self):
        return self.top == -1

    def size(self):
        return self.top + 1

---

Pointer-Based (Linked List) Implementation

A stack can also be implemented using a linked list, where each node contains data and a pointer to the next node. The top of the stack is the head of the linked list.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedStack:
    def __init__(self):
        self.top = None
        self._size = 0

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("Stack Underflow")
        item = self.top.data
        self.top = self.top.next
        self._size -= 1
        return item

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

Comparison of Implementations