Abstract data types: stacks and queues

Stack (LIFO)

A stack is a last in, first out (LIFO) structure: items are added and removed at the same end, the top. A top pointer (stack pointer) records the top item.

• Insert = push: add an item to the top. If the stack is full, a stack overflow error occurs.
• Delete = pop: remove and return the top item. If the stack is empty, a stack underflow error occurs.
• Search (for example peek to look at the top item without removing it, or checking whether an item is in the stack).

Uses: the call stack for subroutines, undo in editors, the back button in a browser, reversing data, evaluating expressions.

Queue (FIFO)

A queue is a first in, first out (FIFO) structure: items join at the rear (back) and leave from the front. Front and rear pointers track the ends.

• Insert = enqueue: add to the rear (error if full).
• Delete = dequeue: remove from the front (error if empty).
• Search: look at the front item or check whether an item is present.

Uses: print queues, keyboard buffers, process scheduling (ready queue), packets waiting to be sent.

In a fixed-length list, a linear queue can run out of space at the rear while space is free at the front; a circular queue wraps the rear pointer round to reuse those spaces.

Tracing

Stack: push 5, push 9, push 2, pop, push 7, pop, pop.

Items popped in order: 2, 7, 9. Final stack (bottom to top): 5.

Queue: enqueue A, B, C, dequeue, enqueue D, dequeue.

Items removed: A, B. Final queue (front to rear): C, D.

Worked example

A stack can hold 3 items. Trace: push 4, push 6, push 1, push 8, pop.

1. push 4: [4]
2. push 6: [4, 6]
3. push 1: [4, 6, 1]; the stack is now full
4. push 8: stack overflow, 8 is not added
5. pop: returns 1; stack is [4, 6]

Answer: Overflow on push 8; finally [4, 6] with 6 at the top.

Check yourself

1. A stack starts empty. Operations: push X, push Y, pop, push Z, push W. List the contents from bottom to top, separated by commas.
   Show answer

   X, Z, W. After pop, only X remains; then Z and W are pushed: X, Z, W.

2. A queue starts empty. Operations: enqueue 4, enqueue 8, dequeue, enqueue 1, enqueue 6, dequeue. List the contents from front to rear, separated by commas.
   Show answer

   1, 6. 4 then 8 are removed from the front; 1, 6 remain.

3. A stack starts empty. Operations: push 5, push 9, push 2, pop, push 7, pop, pop. What value does the final pop return?
   Show answer

   9. Popped in order: 2, 7, 9.

4. Which data structure is last in, first out?
   • Queue
   • Set
   • Stack
   • Dictionary
   Show answer

   Stack. The last item pushed is the first popped.

5. What error occurs when a pop is attempted on an empty stack?
   • Stack underflow
   • Stack overflow
   • Queue overflow
   • Referential integrity error
   Show answer

   Stack underflow. Underflow: nothing to remove.

6. Which application is best suited to a queue?
   • The undo feature of a word processor
   • Storing return addresses for nested function calls
   • Documents waiting to be printed
   • Reversing the letters of a word
   Show answer

   Documents waiting to be printed. Print jobs should be handled in the order they arrived.

7. A queue starts empty. 7 items are enqueued and then 3 are dequeued. How many items are in the queue?
   Show answer

   4. 7 - 3 = 4.

8. Explain why a circular queue is used when a queue is stored in a fixed-length list.
   Show answer

   In a linear queue, dequeued spaces at the front cannot be reused, so the queue can appear full; a circular queue wraps the rear pointer back to the start to reuse those spaces.. Explain the wasted space and how wrapping fixes it.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (2026)

Last updated 8 November 2026. Spotted a mistake? Tell us.