Skip to content

Stacks and Queues

1.4.2 Data structures · Paper 1 · 3 flashcards · 7 questions

Stacks

Definition
A stack is a LIFO (Last In, First Out) data structure. The last element added is the first one to be removed.
Key Point
Stack Operations:
• Push - Add element to top
• Pop - Remove element from top
• Peek/Top - View top element without removing
• IsEmpty - Check if stack is empty
Worked Example
Worked Example: Stack Operations
pseudocode 
// Create empty stack
stack = []

// Push operations
stack.push("A")          // Stack: ["A"]
stack.push("B")          // Stack: ["A", "B"]
stack.push("C")          // Stack: ["A", "B", "C"]

// Pop operations
item = stack.pop()       // Returns "C", Stack: ["A", "B"]
item = stack.pop()       // Returns "B", Stack: ["A"]

// Peek (does not remove)
top = stack.peek()       // Returns "A", Stack unchanged: ["A"]
Real-world analogy: A stack of plates - you add and remove from the top.

Implementing a Stack with an Array

A stack is usually held in an array, with one pointer that records where the top of the stack is. Pushing and popping only ever change the pointer and the element it points to.

Definition
Overflow is an attempt to push an item on to a stack that is already full. Underflow is an attempt to pop an item from a stack that is empty. Both must be checked for before the operation is carried out.
Worked Example
Worked Example: Push and Pop with a Pointer
pseudocode 
// Stack held in an array of 6 elements, indexes 0 to 5
array items[6]
top = -1                     // index of the last item added; -1 means empty

procedure push(item):
    if top == 5 then
        print("Stack is full")       // overflow
    else
        top = top + 1                // move the pointer up
        items[top] = item            // store the item there
    end if
end procedure

function pop():
    if top == -1 then
        print("Stack is empty")      // underflow
        return null
    else
        item = items[top]            // read the top item
        top = top - 1                // move the pointer down
        return item
    end if
end function
A popped item is not erased from the array. The pointer moves down, and the old value is overwritten by the next push.
Exam Tip
Read how the question sets up the pointer:
• It may hold the index of the last item added (as above) or the index of the next free space
• An empty stack may be shown by -1 or by 0
• Use the question's own names for the array and the pointer, and check for a full stack before a push and an empty stack before a pop

Queues

Definition
A queue is a FIFO (First In, First Out) data structure. The first element added is the first one to be removed.
Key Point
Queue Operations:
• Enqueue - Add element to rear
• Dequeue - Remove element from front
• Front - View front element
• IsEmpty - Check if queue is empty
Worked Example
Worked Example: Queue Operations
pseudocode 
// Create empty queue
queue = []

// Enqueue operations
queue.enqueue("A")       // Queue: ["A"]
queue.enqueue("B")       // Queue: ["A", "B"]
queue.enqueue("C")       // Queue: ["A", "B", "C"]

// Dequeue operations
item = queue.dequeue()   // Returns "A", Queue: ["B", "C"]
item = queue.dequeue()   // Returns "B", Queue: ["C"]
Real-world analogy: A line of people - first to arrive is first to be served.

Circular Queue

Definition
A circular queue uses a fixed-size array where the end wraps around to the beginning, reusing empty space.
Worked Example
Circular Queue with Pointers:
pseudocode 
// Array implementation with front and rear pointers
queue = new Array[5]     // Fixed size 5
front = 0                // Points to first element
rear = -1                // Points to last element
size = 0                 // Current number of elements

procedure enqueue(item):
    if size < 5 then
        rear = (rear + 1) mod 5    // Wrap around using modulo
        queue[rear] = item
        size = size + 1
    else
        print("Queue is full")
    end if
end procedure

procedure dequeue():
    if size > 0 then
        item = queue[front]
        front = (front + 1) mod 5  // Wrap around
        size = size - 1
        return item
    else
        print("Queue is empty")
    end if
end procedure