Stacks (Cambridge (CIE) A Level Computer Science): Revision Note

Implementing a stack

How do you program a stack?

• To recap the main operations of stacks and how they work, read the ADT overview

• When programming a stack, the main operations listed below must be included in your program.

• The main operations for stacks are:

Main operations

• In pseudocode, we assume a record-based stack with fields like items, top, and capacity

• Python uses built-in lists or a class with .push() and .pop() methods

• Java uses Stack<E> from java.util.Stack

Stack in operation (Pseudocode)

TYPE Stack
    DECLARE items : ARRAY[0:4] OF INTEGER
    DECLARE top : INTEGER
    DECLARE capacity : INTEGER
ENDTYPE

// Initialise stack
DECLARE s : Stack
s.top ← -1
s.capacity ← 5

// Push 3 values onto the stack
CALL push(s, 10)
CALL push(s, 20)
CALL push(s, 30)

// Peek at the top item
OUTPUT "Top item is ", peek(s)

// Pop 2 values from the stack
DECLARE val : INTEGER
val ← pop(s)
OUTPUT "Popped value: ", val

val ← pop(s)
OUTPUT "Popped value: ", val

// Output current stack size
OUTPUT "Current size: ", size(s)

• Defines a Stack structure with a fixed-size array of 5 items, a top pointer, and a capacity

• Initialises the stack with top ← -1 to indicate it is empty

• Pushes 3 values (10, 20, 30) onto the stack one by one:

  • Each push increases top and adds the value to the items array

• Peeks at the current top of the stack:

  • Returns 30 without removing it

• Pops two values off the stack:

  • First pop returns 30, second returns 20

  • Each pop decreases top by 1

• Outputs the current size of the stack:

  • After popping twice, only one value (10) remains → size is 1

Python

class Stack:
    def __init__(self, capacity):
        self.stack = []
        self.capacity = capacity

    def isEmpty(self):
        return len(self.stack) == 0

    def isFull(self):
        return len(self.stack) == self.capacity

    def push(self, value):
        if not self.isFull():
            self.stack.append(value)
        else:
            print("Stack is full")

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            return None

    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            return None

    def size(self):
        return len(self.stack)


# Stack in operation
s = Stack(5)

# Push 3 values
s.push(10)
s.push(20)
s.push(30)

# Peek at top
print("Top item is", s.peek())

# Pop 2 values
print("Popped value:", s.pop())
print("Popped value:", s.pop())

# Output current size
print("Current size:", s.size())

Java

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();

        // Push 3 values
        s.push(10);
        s.push(20);
        s.push(30);

        // Peek at top
        System.out.println("Top item is " + s.peek());

        // Pop 2 values
        System.out.println("Popped value: " + s.pop());
        System.out.println("Popped value: " + s.pop());

        // Output current size
        System.out.println("Current size: " + s.size());
    }
}