QUEUES
SCHOOL OF COMPUTING MITCH M. ANDAYA
QUEUES
• A queue is a list in which
insertions occur at one
end and deletions occur
at the other end.
• The end of the queue
where insertions take
place is the rear of the
queue.
• While the end where
deletions take place is • A queue obeys the first-
the front of the queue. in first-out (FIFO) rule.
Queues
QUEUES
• Operations on Queues
– Inserting an item or element at the rear of a queue.
– Removing or deleting an item or element from the front of a
queue.
– Examining the item or element at the front of the queue.
– Determining if the queue is empty.
– Determining if the queue is full assuming that there is a
limitation on the number of items a queue can have.
Queues
ARRAY IMPLEMENTATION OF QUEUES
• The simplest way to represent a queue is by using a one-
dimensional array.
• To declare a queue for integers:
int queue[n];
where n is the maximum number of allowable entries.
• This implies that the array implementation of queues puts
a limit on the number of items the queue may have.
Queues
ARRAY IMPLEMENTATION OF QUEUES
• Adding elements to the queue: 4, 2, 6, 8, 9, 5, 7, 3, 1
queue[9]
queue[8] 1
queue[7] 3 3
queue[6] 7 7 7
queue[5] 5 5 5 5
queue[4] 9 9 9 9 9
queue[3] 8 8 8 8 8 8
queue[2] 6 6 6 6 6 6 6
queue[1] 2 2 2 2 2 2 2 2
queue[0] 4 4 4 4 4 4 4 4 4
Queues
ARRAY IMPLEMENTATION OF QUEUES
• Removing elements from the queue:
queue[9]
queue[8] 1 1 1 1 1 1
queue[7] 3 3 3 3 3 3 The program should
queue[6] 7 7 7 7 7 7
therefore keep
track of which cell
queue[5] 5 5 5 5 5 5 holds the element
queue[4] 9 9 9 9 9 at the front of the
queue[3] 8 8 8 8 queue and which
cell holds the
queue[2] 6 6 6 element at the rear.
queue[1] 2 2
queue[0] 4
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] • To keep track of which cell
queue[8] 1 rear = 8 holds the element at the rear,
an integer variable (rear) will
queue[7] 3 hold the index of the element
queue[6] 7 at the rear of the queue.
queue[5] 5
queue[4] front = 4 • Similarly, an integer variable
(front) will hold the index of
queue[3] front is always 1
the element at the front.
less than the
queue[2] actual front of
the queue
queue[1] Actually, front is equal to one
queue[0] less than the actual front of
the queue.
Queues
ARRAY IMPLEMENTATION OF QUEUES
• How to determine if the queue is empty?
queue[9]
queue[8] 1 rear = 8 1 rear = 8 1 rear = 8 1 rear = 8 rear = 8 front = 8
queue[7] 3 3 3 front = 7
queue[6] 7 7 front = 6
queue[5] 5 front = 5
queue[4] front = 4
queue[3] To delete the
queue[2] front most
item, simply
queue[1] increment
queue[0] front.
The queue is considered empty if front = rear.
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] • The algorithm for removing an
queue[8] 1 rear = 8 item from the queue (assuming
the value of the item to be
queue[7] 3 removed will be placed in a
queue[6] 7 variable called item):
queue[5] 5
if (front == rear)
queue[4] front = 4 cout << "Queue is empty!";
queue[3] front is always 1 else
less than the
queue[2] actual front of {
the queue ++front;
queue[1]
item = queue[front];
queue[0] }
Queues
ARRAY IMPLEMENTATION OF QUEUES
• How to determine if the queue is full?
• Assume that the array queue has a
queue[9] 4 rear = 9 maximum of 10 cells.
queue[8] 1 rear = 8
Once an item is added and it occupied the
queue[7] 3 last array cell (queue[9] in this example),
then the queue is considered full.
queue[6] 7
queue[5] 5 So the queue is full if:
queue[4] front = 4
rear = n - 1
queue[3]
queue[2] where n is the maximum number of cells in
the array.
queue[1]
queue[0] Take note that even though rear = n -1, the
array is not physically full.
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] • The algorithm for inserting an
queue[8] rear = 8
1 item into the queue (assuming
the variable item holds the
queue[7] 3 rear = 7 item to be inserted):
queue[6] 7
queue[5] 5 if (rear == n - 1)
queue[4] front = 4 cout << "Queue is full!";
queue[3] else
queue[2] {
queue[1]
++rear;
queue[rear] = item;
queue[0]
}
Queues
ARRAY IMPLEMENTATION OF QUEUES
• The problem in this approach is the
queue[9] rear = 9
4 wastage of memory.
queue[8] 1
If the queue is full, it does not necessarily
queue[7] 3 mean that there are n elements in the
queue.
queue[6] 7
queue[5] 5 Some cells are wasted since even though
there is still space in the array, items can
queue[4] front = 4 no longer be added since they would fall
beyond the array space.
queue[3]
queue[2] • A simple solution to this problem is to
slide the queue back to the beginning of
queue[1] the array space.
queue[0] • However, if the queue is large, this
process is time consuming.
Queues
ARRAY IMPLEMENTATION OF QUEUES
• A more efficient solution is to use circular arrays.
queue[9] 9 9 9 9
• If rear = n - 1 (the
queue[8] 1 1 1 1 1
highest index)
queue[7] 3 3 3 3 3 and an item is to
queue[6] 7 7 7 7 7 be added, then
that item is sent
queue[5] 5 5 5 5 5
to the low index
queue[4] end of the array.
queue[3]
queue[2] 8 • The queue
queue[1] 6 6 therefore crawls
in a circular space
queue[0] 4 4 4
Queues
ARRAY IMPLEMENTATION OF QUEUES
• Removing Elements in a Circular Array
queue[9] 9 9 front = 9
queue[8] 5 front = 8
queue[7] front = 7
queue[6]
queue[5]
queue[4]
queue[3]
queue[2]
queue[1] 2 rear = 1 2 rear = 1 2 rear = 1 2 rear = 1 rear = 1 front = 1
queue[0] 4 4 4 front = 0
Take note that the queue is still empty when front = rear.
Queues
ARRAY IMPLEMENTATION OF QUEUES
• Earlier, deleting an item from the
queue[9] 9 queue simply means that front
should be updated by:
queue[8] 5
queue[7] front = 7 ++front;
queue[6] However, in a circular queue, front
queue[5] may be equal to n - 1 (the last
index in the array).
queue[4]
In this case, front should not be
queue[3] incremented (it will go beyond the
queue[2] array range.
queue[1] 2 rear = 1 Instead, it should be updated by
making it equal to 0:
queue[0] 4
front = 0;
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] 9 • The algorithm for removing an
item from the queue:
queue[8] 5
queue[7] front = 7 if (front == rear)
cout << "Queue is empty!";
queue[6] else
queue[5] {
if (front == n - 1)
queue[4]
front = 0;
queue[3] else
++front;
queue[2]
queue[1] 2 rear = 1 item = queue[front];
}
queue[0] 4
Queues
ARRAY IMPLEMENTATION OF QUEUES
• Adding Elements in a Circular Array
queue[9] 9 9 9 9 9
queue[8] 5 5 5 5 5
queue[7] front = 7 front = 7 front = 7 front = 7 10 front = 7 rear = 7
queue[6] 6 rear = 6 6
queue[5] 8 rear = 5 8 8
queue[4] 3 rear = 4 3 3 3
queue[3] 1 rear = 3 1 1 1 1
queue[2] 7 7 7 7 7
queue[1] 2 2 2 2 2
queue[0] 4 4 4 4 4
Take note that the queue is full when front = rear.
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] 9 • The problem now is that the
queue is full if front = rear (the
queue[8] 5 same condition for an empty
queue[7] front = 7 queue).
queue[6] 6 rear = 6
• To determine if the queue is
queue[5] 8 full without any ambiguity, one
queue[4] 3 solution is to limit the queue to
a maximum size of one less
queue[3] 1 than the size of the array.
queue[2] 7
queue[1] 2
• This implies that one element
of the array should be
queue[0] 4 sacrificed.
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] 9 • So to determine if the queue is
full:
queue[8] 5
queue[7] front = 7 1. Increment rear first.
queue[6] 6 rear = 6
queue[5] 8 2. Check if front = rear. If it is,
then the queue is full.
queue[4] 3
queue[3] 1 • To determine if the queue is
queue[2] 7 empty:
queue[1] 2
1. Check if front = rear. If it is,
queue[0] 4 then the queue is empty.
Queues
ARRAY IMPLEMENTATION OF QUEUES
queue[9] 9 • The algorithm for determining if
the queue is full:
queue[8] 5
queue[7] front = 7 temp = rear;
queue[6] 6 rear = 6
if (temp == n - 1)
queue[5] 8 temp = 0;
else
queue[4] 3
++temp;
queue[3] 1
if (temp == front)
queue[2] 7
queue is full;
queue[1] 2 else
queue is not full;
queue[0] 4
Queues
ARRAY IMPLEMENTATION OF QUEUES
• The algorithm for inserting
queue[9] 9
items to the queue:
queue[8] 5
queue[7] front = 7 if (queue_full() == 1)
queue[6] 6 rear = 6 cout << "Queue is full!";
else
queue[5] 8
{
queue[4] 3 if (rear == n - 1)
queue[3] 1 rear = 0;
queue[2] 7 else
++rear;
queue[1] 2
queue[rear] = item;
queue[0] 4 }
Queues
OPERATIONS ON QUEUES
• Assume the following global declaration:
const int MAX_SIZE = 100;
and the following local declarations in
main():
int queue[MAX_SIZE];
int front, rear;
Queues
OPERATIONS ON QUEUES
• Function to Check if Queue is Full (returns 1 if full and 0 if not full)
int queue_full (intint front,
front , int rear)
rear )
{
if (rear == MAX_SIZE - 1)
rear = 0;
else
++rear;
if (rear == front)
return (1);
else
return (0);
}
Queues
OPERATIONS ON QUEUES
• Function to Check if Queue is Empty (returns 1 if
empty and 0 if not empty)
int
int queue_empty (int front,, int rear)
int front rear )
{
if (front == rear)
return (1);
else
return (0);
}
Queues
OPERATIONS ON QUEUES
• Function to Insert an Item into the Queue
void insert_item (intint queue[ ]],, int front
front,, int
int *ptr_rear,
*ptr_rear, int item )
int item)
{
front , *ptr_rear)
if (queue_full (front, *ptr_rear == 1)
cout << "\nThe Queue is Full!";
else
{
if (*ptr_rear == MAX_SIZE - 1)
*ptr_rear = 0;
else
++(*ptr_rear);
queue[*ptr_rear] = item;
cout << "\nItem Inserted in the Queue.";
}
}
Queues
OPERATIONS ON QUEUES
• Function to Remove an Item from the Queue (and return the value of the item)
int queue[ ],
int remove_item (int ], int *ptr_front,
*ptr_front , int rear)
rear )
{
int item;
*ptr_front , rear
if (queue_empty(*ptr_front, rear) ==1)
cout << "\nThe Queue is Empty!";
else
{
if (*ptr_front == MAX_SIZE - 1)
*ptr_front = 0;
else
++(*ptr_front);
item = queue[*ptr_front];
cout << "\n\nItem Removed from the Queue.";
return (item);
}
}
Queues
OPERATIONS ON QUEUES
• Function to determine the item at the front of the queue:
int
int front_item (int
int queue[ ],
], int front,
front , int rear)
rear)
{
if (queue_empty(front, rear) == 1)
cout << "\nThe Queue is Empty.";
else
if (front == MAX_SIZE - 1)
return (queue[0]);
else
return (queue[front+1]);
}
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
• An alternative representation of queues is by using linked lists.
• A pointer variable (front) points at the element at the front of the
queue and another one (rear) points at the element at the rear of
the queue
front 111 222 333 444
rear
• If front and rear are both equal to null, then the queue is said to
be empty. There is no such condition as a full queue in using
linked lists.
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
front 111 222 333 444
rear
• To declare the pointers front and rear:
struct NODE
{
int value;
NODE *next;
};
NODE *front, *rear;
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
• The algorithm for inserting an item into the queue (assume the
pointer ptr will point to the new node and the variable item
contains the value of this node). The first step is to create a node
for the new item:
ptr = (NODE *) malloc (sizeof(NODE));
ptr -> value = item;
ptr -> next = NULL;
front 111 222 333 444
rear
ptr 555
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
• The next step is to attach the node at the rear of the queue:
rear -> next = ptr;
rear = ptr;
front 111 222 333 444
rear
rear
ptr 555
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
• However, if the queue is empty (front and rear are both equal to
NULL), then front and rear should be made to point to the new
node:
if (front == NULL && rear == NULL)
{
front = ptr; ptr 555
rear = ptr;
}
else
{
rear -> next = ptr;
rear = ptr;
}
Queues
LINKED LIST IMPLEMENTATION OF QUEUES
• The following is the algorithm for removing an item from the queue:
if (front == NULL && rear == NULL)
cout << "Queue is Empty!";
else
{
item = front -> value;
ptr = front; front 111 222 333 444
front = front -> next;
rear
if (front == NULL)
rear = NULL;
free(ptr);
}
Queues
OPERATIONS ON QUEUES
• Assume the following global declaration:
struct NODE
{
int value;
NODE *next;
};
and the following local declaration in main():
NODE *front, *rear;
Queues
OPERATIONS ON QUEUES
• Function to Check if Queue is Empty (returns 1 if
empty and 0 if not empty)
*front,, NODE *rear
NODE *front
int queue_empty (NODE *rear))
{
if (front == NULL && rear == NULL)
return (1);
else
return (0);
}
Queues
OPERATIONS ON QUEUES
• Function to Insert an Item into the Queue
void insert_item (NODE **ptr_front,, NODE **ptr_rear
NODE **ptr_front **ptr_rear,, int item)
{
NODE *ptr;
ptr = (NODE *) malloc (sizeof(NODE));
ptr->value = item;
ptr->next = NULL;
if (queue_empty(*ptr_front, *ptr_rear) == 1)
{
*ptr_front = ptr;
*ptr_rear = ptr;
}
Queues
OPERATIONS ON QUEUES
else
{
(*ptr_rear) -> next = ptr;
*ptr_rear = ptr;
}
cout << "\nItem Inserted in the Queue.";
}
Queues
OPERATIONS ON QUEUES
• Function to Remove an Item from the Queue
int remove_item (NODE **ptr_front, NODE **ptr_rear)
{
NODE *ptr;
int item;
if (queue_empty(*ptr_front, *ptr_rear)==1)
cout << "\nQueue is Empty!";
else
{
item = (*ptr_front)-> value;
ptr = *ptr_front;
*ptr_front = (*ptr_front)->next;
Queues
OPERATIONS ON QUEUES
if (*ptr_front == NULL)
*ptr_rear = NULL;
free(ptr);
cout << "\nItem Removed from the Queue.";
return (item);
}
}
Queues
OPERATIONS ON QUEUES
• Function to Determine the Item at the Front of the
Queue
int front_item(NODE *front, NODE *rear)
{
if (queue_empty(front, rear) == 1)
cout << "\nQueue is Empty!";
else
return (front->value);
}
Queues
