DEFINITION

• “A queue is an ordered list in which insertions (additions, pushes) and deletions (removals and

pops) take place at different ends.”

• The end at which new elements are added is called the rear, and that from which old elements

are deleted is called the front.

• Given a queue Q = (a0, a1,……… an-1) , a0, is the front element an-1 is the rear element, ai+1 is

behind ai 0< =i < n-1.

If the elements are inserted A, B, C, D and E in this order, then A is the first element deleted

from the queue. Since the first element inserted into a queue is the first element removed,

queues are also known as First-In-First-Out (FIFO) lists.

QUEUE REPRESENTATION USING ARRAY

• Queues may be represented by one-way lists or linear arrays.

• Queues will be maintained by a linear array QUEUE and two pointer variables: FRONTcontaining the
location of the front element of the queue

• REAR-containing the location of the rear element of the queue.

• The condition FRONT = NULL will indicate that the queue is empty.

• Figure indicates the way elements will be deleted from the queue and the way new elements

will be added to the queue.

• Whenever an element is deleted from the queue, the value of FRONT is increased by 1; this

can be implemented by the assignment FRONT := FRONT + 1

• When an element is added to the queue, the value of REAR is increased by 1; this can be

implemented by the assignment REAR := REAR + 1

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

MODULE 2

vtucode.in
DATA STRUCTURES-BCS304

Implementation of the queue operations as follows.

1. Queue Create

Queue CreateQ(maxQueueSize) ::=

#define MAX_QUEUE_SIZE 100 /* maximum queue size */

typedef struct

int key;

/* other fields */

} element;

element queue[MAX_QUEUE_SIZE];

int rear = -1;

int front = -1;

2. Boolean IsEmptyQ(queue) ::= front ==rear

3. Boolean IsFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1

In the queue, two variables are used which are front and rear. The queue increments rear in

addq( ) and front in delete( ). The function calls would be addq (item); and item =delete( );

4. addq(item)

void addq(int *rear, element item)

// add an item to the queue

if (rear == MAX_QUEUE_SIZE-1)

{ queue_Full();

return;

queue [++rear] = item;

Program: Add to a queue

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

5. deleteq( )

element deleteq(int *front, int *rear)

{ /* remove element at the front of the queue */

if (front == rear)

return queue_Empty( ); /* return an error key

return queue[++front];

Program: Delete from a queue

6. queueFull( )

The queueFull function which prints an error message and terminates execution

void queueFull()

fprintf(stderr, "Queue is full, cannot add element");

exit(EXIT_FAILURE);

Example: Job scheduling

• Queues are frequently used in creation of a job queue by an operating system. If the

operating system does not use priorities, then the jobs are processed in the order

they enter the system.

• Figure illustrates how an operating system process jobs using a sequential

representation for its queue.

vtucode.in

DATA STRUCTURES-BCS304

Drawback of Queue

When item enters and deleted from the queue, the queue gradually shifts to the right as

shown in figure.

In this above situation, when we try to insert another item, which shows that the queue is

full . This means that the rear index equals to MAX_QUEUE_SIZE -1. But even if the

space is available at the front end, rear insertion cannot be done.

Overcome of Drawback using different methods

Method 1:

• When an item is deleted from the queue, move the entire queue to the left so that the

first element is again at queue[0] and front is at -1. It should also recalculate rear so

that it is correctly positioned.

• Shifting an array is very time-consuming when there are many elements in queue &

queueFull has worst case complexity of O(MAX_QUEUE_SIZE)

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

Method 2:

Circular Queue

• It is “The queue which wrap around the end of the array.” The array positions are

arranged in a circle.

• In this convention the variable front is changed. front variable points one position

counterclockwise from the location of the front element in the queue. The
convention for rear is unchanged.

CIRCULAR QUEUES

• It is “The queue which wrap around the end of the array.” The array positions are

arranged in a circle as shown in figure.

• In this convention the variable front is changed. front variable points one position

counterclockwise from the location of the front element in the queue. The

convention for rear is unchanged.

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

Implementation of Circular Queue Operations

• When the array is viewed as a circle, each array position has a next and a previous

position. The position next to MAX-QUEUE-SIZE -1 is 0, and the position that

precedes 0 is MAX-QUEUE-SIZE -1.

• When the queue rear is at MAX_QUEUE_SIZE-1, the next element is inserted at

position 0.

• In circular queue, the variables front and rear are moved from their current

position to the next position in clockwise direction. This may be done using code

if (rear = = MAX_QUEUE_SIZE-1)

rear = 0;

else rear++;

Addition & Deletion

• To add an element, increment rear one position clockwise and insert at the new

position. Here the MAX_QUEUE_SIZE is 8 and if all 8 elements are added into

queue and that can be represented in below figure (a).

deleted from queue and if we perform 6 deletions from the queue of Figure (b) in

this fashion, then queue becomes empty and that front =rear.

• If the element I is added into the queue as in figure (c), then rear needs to

increment by 1 and the value of rear is 8. Since queue is circular, the next

position should be 0 instead of 8.

This can be done by using the modulus operator, which computes remainders.

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

void addq(element item)

{ /* add an item to the queue */

rear = (rear +1) % MAX_QUEUE_SIZE;

if (front == rear)

queueFull(rear); /* print error and exit */

queue [rear] = item;

Program: Add to a circular queue

element deleteq()

{ /* remove front element from the queue */

element item;

if (front == rear)

return queueEmpty( ); /* return an error key */

front = (front+1)% MAX_QUEUE_SIZE;

return queue[front];

}
Program: Delete from a circular queue

MODULE 2

vtucode.in

DATA STRUCTURES-BCS304

CIRCULAR QUEUES USING DYNAMIC ARRAYS

• A dynamically allocated a

• rray is used to hold the queue elements. Let capacity be the number of positions in

the array queue.

• To add an element to a full queue, first increase the size of this array using a

function realloc.

Consider the full queue of figure (a). This figure shows a queue with seven elements in

an array whose capacity is 8. A circular queue is flatten out the array as in Figure (b).