Queue
The Queue - Introduction
Definition: A queue is an ordered collection of items where the addition of
new items happens at one end, called the “rear,” and the removal of existing
items occurs at the other end, commonly called the “front.”
Queues maintain a “First In First Out (FIFO)” ordering property.
Queue
3.3
Uses a explicit linear ordering (follows FIFO)
Insertions and removals are performed individually
There are no restrictions on objects inserted into (Enqueue) the
queue—that object is designated the back of the queue
The object designated as the front of the queue is the object which was
in the queue the longest
The remove operation (Dequeue from the queue) removes the current
front of the queue
Queue
3.3.1
Graphically, we may view these operations as follows:
Enqueue
Dequeue
Abstract Queue
3.3.1
There are two exceptions associated with this abstract data
structure:
Calling pop on an empty queue
Calling front on an empty queue
Implementation of Queue
1. Using Arrays
2. Using Linked Lists
Implementation of Queue using arrays
void main( ) i = delq ( arr, &front, &rear ) ;
{ printf ( "\nItem deleted: %d", i ) ;
int arr[MAX] ;
int front = -1, rear = -1, i ; i = delq ( arr, &front, &rear ) ;
printf ( "\nItem deleted: %d", i ) ;
addq ( arr, 23, &front, &rear ) ;
addq ( arr, 9, &front, &rear ) ; i = delq ( arr, &front, &rear ) ;
addq ( arr, 11, &front, &rear ) ; printf ( "\nItem deleted: %d", i ) ;
addq ( arr, -10, &front, &rear ) ;
addq ( arr, 25, &front, &rear ) ; }
addq ( arr, 16, &front, &rear ) ;
addq ( arr, 17, &front, &rear ) ;
addq ( arr, 22, &front, &rear ) ;
addq ( arr, 19, &front, &rear ) ;
addq ( arr, 30, &front, &rear ) ;
addq ( arr, 32, &front, &rear ) ;
Implementation of Queue using arrays
/* removes an element from the queue
*/
/* adds an element to the queue */ int delq ( int *arr, int *pfront, int *prear )
void addq ( int *arr, int item, int {
*pfront, int *prear ) int data ;
{
if ( *prear == MAX - 1 ) if ( *pfront == -1 )
{ {
printf ( "\nQueue is full." ) ; printf ( "\nQueue is Empty." ) ;
return ; return NULL ;
} }
data = arr[*pfront] ;
( *prear )++ ; arr[*pfront] = 0 ;
arr[*prear] = item ; if ( *pfront == *prear )
*pfront = *prear = -1 ;
if ( *pfront == -1 ) else
*pfront = 0 ; ( *pfront )++ ;
} return data ;
}
Queue using Arrays…
What is the problem in this code?
• Let us fix the array capacity (maxsize) as 5
[0] [1] [2] [3] [4]
• Perform 5 push operations
[0] [1] [2] [3] [4]
5 10 15 20 25 Queue is full
• Perform 2 pop operations
[0] [1] [2] [3] [4]
15 20 25 Queue has 2 free slots??
Queue using Arrays…
What is the problem in this code…?
• Perform 2 pop operations
[0] [1] [2] [3] [4]
Free Free 15 20 25 Queue has 2 free slots
In front of the queue !!
In this case, the array is not full and yet we cannot place any more objects
in to the array. Why??
[0] [1] [2] [3] [4]
15 20 25
Front Rear
Queue using Arrays…
What is the solution?
1. Shift array elements after each deletion – Very expensive (You can try)
2. Cyclic arrays - Instead of viewing the array as linear, on the range “0, 1,
2, 3, 4”, consider the indices by cyclic.
0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,……
Queue using Circular Array…
What is the solution?
Now the next push can be performed into the next available location of
the circular array.
Queue using Circular Array…
Using Circular Array
Problem: front and rear no longer can be used as condition to
distinguish between queue‐full and queue‐empty.
Solution:
• Use a counter
o If count==0 Queue is Empty
o If count==maxsize Queue is full
Disadvantage: Overhead of maintaining counter variable
Deque
3.4.1
Uses a explicit linear ordering
Insertions and removals are performed individually
Allows insertions at both the front and back of the deque
Deque
3.4.1
The operations will be called
front back
push_front push_back
pop_front pop_back
There are four errors associated with this abstract data type:
It is an undefined operation to access or pop from an empty
deque
Assignment:
3.4.1
Write a C Program implements linked list as a queue
Write a C Program implements array as a queue
