ADT Stack

You have stacked plates, books, or roti on a plate before. The plate you put down last is the one you pick up first — you never pull one out from the middle. That single habit is the whole idea of a stack.

In computing, a stack is a collection where every item is added and removed from the same end, called the top. Because the last item in is the first item out, we call this rule LIFO — Last In, First Out. The computer keeps a single number, the top pointer, that always remembers where the top is.

By the end of this page you will be able to describe a stack in exam language, trace push and pop operations on paper, write the algorithms in pseudocode and in Python, and explain how a stack can be built from a linked list. These are the exact skills Paper 4 tests.

Imagine the stack as a vertical pile that grows upwards. The top pointer always points at the most recently added item. When the stack is empty the pointer is set to -1, because there is no item at any index yet.

Here is the complete class. Every method is short; read it once, then read the line-by-line notes below.

class Stack:
    def __init__(self, size=10):
        self.items = [None] * size   # fixed-size storage
        self.maxSize = size          # capacity
        self.top = -1                # empty stack

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

    def isFull(self):
        return self.top == self.maxSize - 1

    def push(self, item):
        if self.isFull():
            return "Stack Overflow"
        self.top += 1                # move pointer up first
        self.items[self.top] = item  # then store the value

    def pop(self):
        if self.isEmpty():
            return "Stack Underflow"
        item = self.items[self.top]  # read value first
        self.items[self.top] = None
        self.top -= 1                # then move pointer down
        return item

    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.items[self.top]

    def display(self):
        return self.items

Push in Cambridge pseudocode:

PROCEDURE Push(NewItem : INTEGER)
    IF TopPointer < MaxSize - 1 THEN
        TopPointer <- TopPointer + 1
        Stack[TopPointer] <- NewItem
    ELSE
        OUTPUT "Stack full"
    ENDIF
ENDPROCEDURE

Pop as a function (returns -1 when empty):

FUNCTION Pop() RETURNS INTEGER
    IF TopPointer = -1 THEN
        RETURN -1            // stack empty
    ELSE
        ThisItem <- Stack[TopPointer]
        TopPointer <- TopPointer - 1
        RETURN ThisItem
    ENDIF
ENDFUNCTION

Peek shows the top value but leaves the stack unchanged — useful when you want to look before you leap. isEmpty is the guard pop relies on. Overflow and underflow are the two error states.

Each node stores a value and a pointer to the next node. The stack keeps one pointer, top, aimed at the head. Push creates a new node whose next points to the old top, then moves top to the new node. Pop does the reverse.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None          # pointer to next node

class Stack:
    def __init__(self):
        self.top = None           # top = head node

    def push(self, item):
        newNode = Node(item)
        newNode.next = self.top   # link to old top
        self.top = newNode        # new node becomes top

    def pop(self):
        if self.top is None:
            return "Stack Underflow"
        item = self.top.value
        self.top = self.top.next  # head moves to next node
        return item

    def peek(self):
        return "Stack is empty" if self.top is None else self.top.value

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python solution.