Data Structures and Algorithms

Lecture 06
Outlines
• Queue
• Defining Queue Class
• Enqueue and Dequeue operations
• Problem with Simple Queue
Queue
• A queue is a data structure that is based upon first-
come first-serve order, or first-in first-out (FIFO)
order.
• A Queue or FIFO (First in, first out) is an abstract
data type that serves as a collection of elements,
with two principal operations: enqueue, which adds
an element to the collection, and dequeue, which
removes the first element that was added.
• The elements that are inserted first will be removed
first, and similarly, the elements that are inserted
last will be removed last.
Example
Example
Queue Operations
• Insert(item): (also called enqueue)
• It adds a new item to the end of the queue
• Remove( ): (also called delete or dequeue)
• It deletes the head item of the queue, and returns to the caller. If the
queue is already empty, this operation returns NULL
• getHead( ):
• Returns the value in the head element of the queue
• getTail( ):
• Returns the value in the tail/end element of the queue
• isEmpty( )
• Returns true if the queue has no items
• size( )
• Returns the number of items in the queue
More About Queue
• A Queue consist of
• Front
• Represents start of the queue. Element are always
dequeued from front.
• Rare
• Represents end of the queue. Elements are always
enqueued from rare.
Example of Queue
A queue Class based on Array
class Queue{
private:
int front, rare, length,capacity;
double* arr;
public:
Queue(int cap)
{
front=0; //represents the head of queue
rare=0; //represents the tail/end of queue
length=0; //represents total elements in queue
capacity=cap; //represents total capacity of queue
arr=new double[capacity];
}
 How head and tail Change
• head increases by 1 after each dequeue( )
• tail increases by 1 after each enqueue( )

Now:
49 48 47 4 3 2 1 0

After enqueue:
49 48 47 4 3 2 1 0

After dequeue:
49 48 47 4 3 2 1 0
 How head and tail Change
• head increases by 1 after each dequeue( )
• tail increases by 1 after each enqueue( )

After dequeue:
49 48 47 4 3 2 1 0

After enqueue:
49 48 47 4 3 2 1 0
Example: enqueue
void enqueue (double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
else
{
cout<<"queue is full"<<endl;
}
}
Example: enqueue
void enqueue (double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
Front and Rare

49 48 47 4 3 2 1 0

capacity=50 length=0
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
Front and Rare

49 48 47 4 3 2 1 0

capacity=50 length=0
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
Front and Rare

49 48 47 4 3 2 1 0

capacity=50 length=1
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
rare Front

49 48 47 4 3 2 1 0

capacity=50 length=1
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
rare Front

49 48 47 4 3 2 1 0

capacity=50 length=1
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
rare Front

49 48 47 4 3 2 1 0

capacity=50 length=2
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
rare Front

49 48 47 4 3 2 1 0

capacity=50 length=2
Example: enqueue
void enqueue(double val)
{
if ((length<capacity)&&(rare<capacity))
{
arr[rare]=val;
length++;
rare=rare+1;
cout<<"value added "<<val<<endl;
}
}
rare Front

49 48 47 4 3 2 1 0

capacity=50 length=3
Example: dequeue
• Suppose 5 enqueue have been made. Now, we like
to dequeue 2 elements

rare Front

49 48 47 5 4 3 2 1 0

capacity=50 length=5
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=5

index 0
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=5

index 0
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=4

index 0
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=4

index 1
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=4

index 1
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=front+1;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=3

index 1
Overflow Issue
• Suppose 50 enqueue have been made when program
starts, so now the queue array is full

49 48 47 4 3 2 1 0

• Assume 4 calls to dequeue( ) are made

49 48 47 4 3 2 1 0

• Assume a call to enqueue( ) is made now. The tail

part seems to have no space, but the front has 4
unused spaces; if never used, they are wasted.
Solution
• Use modulus to increment front and rare.
void enqueue(double val)
{
if (length<capacity)
{
arr[rare]=val;
length++;
rare=(rare+1)%capacity;
cout<<"value added "<<val<<endl; rare Front
}
}

49 48 47 4 3 2 1 0

capacity=50 length=3
Example: dequeue
double dequeue()
{
double value;
if (length>0)
{
value=arr[front];
front=(front+1)%capacity;
length--;
}
return value;
} rare Front

49 48 47 4 3 2 1 0

capacity=50 value= value at length=3

index 1