Algorithms C++ Edition (2015)

Part 2: Switching List Types

Chapter 2b: The Queue, as an Array

The Data Structure

Just like the Array Stack, you’ll need your actual array. But this time, we’ll need four integers: the front index, the back index, the max size and the current item count.

// Abstract Data Type: Queue, as an Array

// The Queue Has:

// - the Actual Array (with Size and Data Type)

// - the Index of the Front Item (Integer)

// - the Index of the Back Item(Integer)

// - the Max Size of the Queue (Integer)

// - the Current Item Count (Integer)

CompositeStructure ArrayQueue {

Integer FRONT

Integer BACK

Integer MAXSIZE

Integer COUNT

(choose a data type) ARRAY[MAXSIZE]

}

Now, let’s look at how the Enqueue() and Dequeue() methods work, in detail:

Array Queue: Enqueue() Function

The Enqueue() function from an Array Queue adds items into that queue. It does this in the following procedure, in this particular order:

1) Check if there’s room in the array for the extra item

2) If there’s no room in the array, either report a queue overflow error (if fixed-size array) or increase the array size (if variable array)

3) If there’s room in the array, we add the item to the queue. Set the new item’s index as the current Back Index (so the item is the very last item in the Queue)

4) Increment the Back Index. If the Back Index becomes bigger than or equal to the Array Size, set the Back Index to 0 (it’s now at the start of the Circular Array).

4) And Finally, Increment the Item Count

After the enqueue() procedure successfully inserts an item, you should have that item as the last item in the circular array, regardless of what index it has. Also, the item count should be increased by 1.

Array Queue: Dequeue() Function

The Dequeue() method from an Array Queue removes an item from that queue. The function returns that item as the Function Output. It does this in the following procedure, in this particular order:

1) Check the Array Count if there are any items to dequeue

2) If not, either return NULL or report a queue underflow error

3) If there’s an item to dequeue, create a Local Variable. Set it to be your return item (it should be the item at the front of the queue!). Remove the item at the Front of the Queue afterwards

4) Increment the Front Index. If the Front Index becomes bigger than or equal to the Array Size, set the Front Index to 0 (it’s now at the start of the Circular Array).

5) Decrement the Item Count

6) And Finally, the function returns your item and ends.

After the dequeue() procedure successfully removes and retrieves an item, the item should be the first item from the array. Also, the item count should be decreased by 1.

Remember: function returns should be the very last thing in a function procedure - as it ends the function.