Having studied the principle of a stack, we will list the principle of operation for a queue:
A queue models a real-life queue, for example, a queue (line) of people in a cafeteria waiting to order and pay for food.
The queue (line) of people can be thought of as a list with a :
Head or Front– the first person in the line, and the first to be served.
Tail or End – the last person in the line and the last to be served.
Every time an lunch order is processed, the head of the queue leaves the line, the entire line moves up , and the next person becomes the new head.
The queue ADT consists of a list of items and at least 3 reference variables which keep track of the location of the head, tail and the size of the queue. Operations on the queue are shown below:
| Operation | Explanation | Example |
| Add(..) or Enqueue(..) | Adds/Enqueues an item to the end of the queue and updates the tail to point to the newly added item. if the queue is full, the item is not added and an error message displayed. If the queue is empty, add the new item at the head. In this case the head and tail point to the newly added item. | A person joins the end of the line at the cafeteria. If the line is full, the person cannot enter the line. If the line is empty, the person goes straight to the head, i.e the cash register. |
| Remove(..) or Dequeue(..) | Removes/Dequeues and returns the item at the head of the queue. If the que is empty, the remove operation fails , an error message is displayed. An appropriate dummy/null value is returned. | Accept payment from the person at the cash register and send them on their way. If there are more people in the line, the line moves up and the person at the front of the line is at the cash register. |
| Peek(..) | returns the item at the head of the queue. If the que is empty, the peek operation fails , an error message is displayed. An appropriate dummy/null value is returned. | |
| Size(…) | Returns the size of the queue | |
| IsEmpty() | Returns true if the queue is empty, i.e, size==0 |
Characteristics of a Queue
In creating a coded implementation of a queue using an array, we observe the following characteristics:
State:
| Variable | Description | Value at initialization |
| size | Integer to keep track of the size f the queue. | 0 |
| head | Integer to keep track of the front of the queue. This value stores the array index of the head/front | 0 |
| tail | Integer to keep track of the tail/end of the queue. This value stores the array index of the tail/end | -1 |
| MAX_SIZE | This stores he maximum size of the array; the array length | Sufficiently large, chosen by the programmer. |
Behavior:
Items are added/enqueued using the tail index, items are removed/dequeued using the head index.
During the enqueue operation
If the queue is full
Cannot add, display error message
Else
Increment tail index
Place new data at tail index
Increment size
During the dequeue Operation
If the queue is empty
Display error message, return dummy value e.g -999
Else
Store the data that was at the head in a new variable, X
Increment the head index
Decrement size
Return X
During the Peek Operation
If the queue is empty
Display error message, return dummy value e.g -999
Else
Return the data stored at head index
( updated – 14th October 2020)
© 2020 Vedesh Kungebeharry. All rights reserved
Island Class 