Describe stacks (LIFO) and queues (FIFO), implement their core operations, and identify suitable applications of each

What this dot point is asking

SEAB wants you to describe stacks and queues, implement their core operations, and identify where each is used. The central idea is that both restrict where items can be added and removed: a stack works last in, first out, and a queue works first in, first out, and these disciplines match many real processing orders.

The answer

Stacks: last in, first out (LIFO)

A stack allows access only at one end, the top. The most recently added item is the first removed:

• push(x) - add x to the top.
• pop() - remove and return the top item.
• peek() - look at the top without removing it.
• isEmpty() - test if empty.

class Stack:
    def __init__(self):
        self.items = []
    def push(self, x):
        self.items.append(x)
    def pop(self):
        if self.is_empty():
            raise IndexError("stack underflow")
        return self.items.pop()
    def is_empty(self):
        return len(self.items) == 0

Popping an empty stack is underflow; pushing onto a full fixed-size stack is overflow.

Queues: first in, first out (FIFO)

A queue adds at the rear and removes from the front, like people in a line:

• enqueue(x) - add x to the rear.
• dequeue() - remove and return the front item.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    def enqueue(self, x):
        self.items.append(x)
    def dequeue(self):
        if self.is_empty():
            raise IndexError("queue underflow")
        return self.items.popleft()
    def is_empty(self):
        return len(self.items) == 0

Circular buffers for array queues

In a fixed-size array, dequeuing from the front would leave a gap, and shifting everything forward is $O(n)$. A circular buffer instead advances front and rear indices that wrap around the array end, so both operations stay $O(1)$ with no shifting.

When to use each

All four core operations are $O(1)$. Choose by the order you need:

• Stack - when the most recent item must come out first: call stacks, undo, bracket matching, depth-first search.
• Queue - when items must be served in arrival order: print spooling, request handling, breadth-first search.

Examples in context

Example 1. The browser back button. Each page you visit is pushed onto a stack; pressing back pops the most recent one, returning you to where you just were. The last-in-first-out order is exactly what "go back to the previous page" means, which is why a stack models browsing history.

Example 2. A printer queue. Documents sent to a shared printer are enqueued and printed in the order they arrived, so the first job submitted prints first. First-in-first-out fairness is the whole point of a print spooler, and the same queue discipline schedules requests arriving at a web server.

Try this

Q1. A stack has push(1), push(2), push(3), pop() applied. What is returned and what is on top afterward? [2 marks]

• Cue. pop returns 3 (last in); 2 is now on top.

Q2. Define stack overflow. [1 mark]

• Cue. Attempting to push onto a stack that is already full, with no space for another item.

Q3. Why is a queue, not a stack, used for breadth-first search? [2 marks]

• Cue. BFS must process nodes in the order discovered (level by level), which is first-in-first-out - a queue; a stack would process them depth-first.