Essential algorithms for GCSE and A Level Computer Science

Higher order data structures

Supported by some programming languages within the command set, programmers often implement these structures using the fundamental data structures as building blocks.

What is a queue?

A queue is a linear data structure.  Items are “enqueued” at the back of the queue and “dequeued” from the front of the queue. It is also possible to “peek” at the front item without deleting the item.

Imagine a queue at a checkout. The person at the front of the queue is served first, and people join the back of the queue.  This strict process can also allow for people to jump the queue — when implemented in computer science, this is known as a priority queue.  In special circumstances, new items can join the front or the back of the queue.

A queue is known as a first-in, first-out or FIFO structure.

A queue has a “back pointer” that always points to the last item in the queue, sometimes referred to as a tail pointer.  A queue also has a “front pointer” that always points to the first item in the queue, sometimes referred to as a head pointer.

An attempt to enqueue an item to an already-full queue is called a queue overflow, while trying to dequeue an item from an empty queue is called a queue underflow. Both should be considered before proceeding to enqueue or dequeue the item in question.

Queues can be implemented using an array or object-oriented

technique.

Queue videos

What extra is in the book?

This algorithm / data structure has its own dedicated chapter in the book, which includes:

  1. Overview
  2. Typical applications / uses
  3. Typical operations
  4. The algorithm written out in simple-structured English
  5. The algorithm written out in pseudocode
  6. Full code listing Python
  7. Full code listing in Visual Basic
  8. Diagrammatic walk-through
  9. Efficiency discussion with reference to Big-O notation

A hard copy of the book is available on our shop and a free PDF copy is included for all premium subscribers.