Tutorial 4

🚶🏻‍♂️

Queue

9618 A-Level

i

Note: for AS, the syllabus states you won't be asked to write a queue from scratch - but they do have "fill in the blank" type questions where they give you most of the code and ask you to complete it

For A2, you can be asked to write an entire queue from scratch, including the enqueue and dequeue modules

It may be useful to search (CTRL + F) for "queue" questions in the (combined) past papers

If you find any bugs/edge cases in this code, please contact me

A queue is a FIFO (first-in, first-out) data structure - we will need a pointer to both the front and end of the queue - often called head and tail pointers respectively

There are two operations queues support:

  1. Enqueue: if the queue is not full, add the element to the end and increment the tail pointer
  2. Dequeue: if the queue is not empty, remove and return the first element from the queue

There are two types of queue we will look at in this tutorial:

  1. Linear queue: elements enqueued sequentially - if the tail pointer equals the queue size, we can't add any more elements, even if we have removed others from the front
  2. Circular queue: elements enqueued sequentially - if the tail pointer equals the queue size and the queue isn't full, then the tail pointer will "wrap around" to the front of the queue, much like a clock wrapping around from hour 12 back to hour 1 when it reaches that time

1

Linear Queue

As stated, while a linear queue is simple, there is a problem - when we dequeue elements, the front pointer is incremented and these indexes hence become unavailable

More detailed comments can be seen in the code

CONSTANT QUEUE_SIZE = 3 DECLARE FrontPointer, EndPointer : INTEGER DECLARE Queue : ARRAY[1:QUEUE_SIZE] OF STRING CALL ResetQueue() CALL Enqueue("Archimedes") CALL Enqueue("Bohr") CALL Enqueue("Copernicus") CALL Enqueue("Dirac") CALL OutputQueue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() CALL OutputQueue() PROCEDURE ResetQueue() FrontPointer ← 0 //don't have to clear data - just reset pointers since when we enqueue, any existing data in that position will be overwritten EndPointer ← 0 ENDPROCEDURE PROCEDURE Enqueue(data : STRING) //if queue not full IF EndPointer < QUEUE_SIZE THEN //handle case of empty queue IF FrontPointer = 0 THEN FrontPointer ← 1 ENDIF EndPointer ← EndPointer + 1 Queue[EndPointer] ← data //add data to current position OUTPUT "Enqueued \"", data, "\" at index ", EndPointer ELSE OUTPUT "Can't enqueue \"", data, "\" - queue full" ENDIF ENDPROCEDURE FUNCTION Dequeue() RETURNS STRING //check queue not empty - handles empty cases when no data has been enqueued and when all data has been dequeued IF FrontPointer > 0 AND FrontPointer <= EndPointer THEN DECLARE data : STRING data ← Queue[FrontPointer] //get front item FrontPointer ← FrontPointer + 1 RETURN data ELSE OUTPUT "Queue empty - nothing to dequeue" RETURN "" ENDIF ENDFUNCTION PROCEDURE OutputQueue() DECLARE index : INTEGER OUTPUT "--- Queue Contents ---" //make sure item has been added, to avoid index 0 out of bounds error IF FrontPointer > 0 THEN FOR index ← FrontPointer TO EndPointer OUTPUT "Index ", index, ": ", Queue[index] NEXT index ENDIF OUTPUT "----------------------" ENDPROCEDURE

2

Circular Queue

Unlike a linear queue, both the front (head) and end (tail) pointer can wrap-around back to the beginning of the queue, hence we can reuse indexes that we have previously dequeued from

To keep track of whether the queue is full, the easiest way it to just use another variable as a counter storing the number of items currently in the queue - we will increment when we successfully enqueue and decrement when we successfully dequeue

More detailed comments can be seen in the code

CONSTANT QUEUE_SIZE = 5 DECLARE FrontPointer, EndPointer, NumItemsInQueue : INTEGER DECLARE Queue : ARRAY[1:QUEUE_SIZE] OF STRING CALL Enqueue("Australia") CALL Enqueue("Bahrain") CALL Enqueue("China") CALL Enqueue("Denmark") OUTPUT Dequeue() CALL Enqueue("Ecuador") CALL Enqueue("Finland") CALL OutputQueue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() OUTPUT Dequeue() CALL Enqueue("Greenland") CALL Enqueue("Hungary") CALL Enqueue("Iceland") CALL Enqueue("Jordan") CALL Enqueue("Kazakhstan") CALL OutputQueue() PROCEDURE ResetQueue() //don't have to clear data - just reset pointers since when we enqueue, any existing data in that position will be overwritten FrontPointer <-- 0 EndPointer <-- 0 NumItemsInQueue <-- 0 ENDPROCEDURE PROCEDURE Enqueue(item : STRING) //check queue not full IF NumItemsInQueue < QUEUE_SIZE THEN EndPointer <-- EndPointer + 1 //wrap-around if required IF EndPointer > QUEUE_SIZE THEN EndPointer <-- 1 ENDIF Queue[EndPointer] <-- item //add item at end of queue NumItemsInQueue <-- NumItemsInQueue + 1 OUTPUT "Enqueued ", item, " at index ", NUM_TO_STR(EndPointer) ELSE OUTPUT "Queue full - can't enqueue ", item ENDIF ENDPROCEDURE FUNCTION Dequeue() RETURNS STRING //check queue not empty IF NumItemsInQueue > 0 THEN FrontPointer <-- FrontPointer + 1 //wrp around if required IF FrontPointer > QUEUE_SIZE THEN FrontPointer <-- 1 ENDIF NumItemsInQueue <-- NumItemsInQueue - 1 RETURN Queue[FrontPointer] ELSE RETURN "Queue empty - can't dequeue" ENDIF ENDFUNCTION PROCEDURE OutputQueue() DECLARE currentPos, numOutput : INTEGER OUTPUT "--- Output Queue ---" currentPos <-- FrontPointer numOutput <-- 0 //loop until we have output all items in queue WHILE numOutput < NumItemsInQueue DO currentPos <-- currentPos + 1 IF currentPos > QUEUE_SIZE THEN currentPos <-- 1 ENDIF numOutput ← numOutput + 1 OUTPUT "Index ", currentPos, ": ", Queue[currentPos] ENDWHILE OUTPUT "--------------------" ENDPROCEDURE

Extension details/answers will be added: web server, simulate traffic at traffic lights, keyboard buffer - words split by space