(ELE 144)

Data Structures and Algorithms

Lecture 3
Queue
 Basic principles of Queue
Agenda

Operations of Queue

Implementation Queue
using Array

Applications of Queue
What is a Queue?
• Queue is an abstract data structure, somewhat similar to Stacks. Unlike
stacks, a queue is open at both its ends. One end is always used to
insert data (enqueue) and the other is used to remove data (dequeue).
(FIFO: First In, First Out).
• Examples of queue:

dequeue
enqueue (remove from
(add at rear) Front(
 The Queue Operations
• A queue is like a line of people waiting for a bank teller. The queue has a front and a rear.

• The queue supports two fundamental methods: -

• enqueue(o): Insert object o at the rear of the queue
• dequeue(): Remove the object from the front of the queue and return it
an error occurs if the queue is empty

Every queue has a front and a

rear. You enqueue items at the
rear and dequeue from the front.
Enqueue (ItemType newItem) Dequeue ()
 Function: Adds newItem to  Function: Removes front item from
the rear of the queue. queue.
 Preconditions: Queue has  Preconditions: Queue has been
been initialized and is not full. initialized and is not empty.
 Postconditions: newItem is at  Postconditions: Front element has
rear of queue. been removed from queue.
Queue Array Implementation
• A queue can be implemented with an array, as shown
here. For example, this queue contains the integers 4 (at
the front), and 6 (at the rear).
Rear
Front enqueue
[0] [1] [2] [3] [4] [5] ...
dequeue
4 8 6

An array of integers
to implement a We don't care what's in
queue of integers this part of the array.
 When an element leaves ➢ When an element enters
the queue, size is the queue, size is incremented,
decremented, and front and rear changes, too.
changes, too.
At the End of the Array
• There is special behaviour at the end of the array. For example,
suppose we want to add a new element to this queue, where the
rear index is [5]:

•The size of the queue depends on the number

and order of enqueue and dequeue.
•It may be situation where memory is
available but enqueue is not possible.

Problem:
when rear reaches the end of the array, we can't enqueue
anything else
 Ex: Suppose that:
The array size is 16
We have performed 16 pushes
We have performed 5 pops
The queue size is now 11
We perform one further push
In this case, the array is not full and yet we cannot
place any more objects into the array
 Idea :Circular Queue
▪ When rear reaches the end of the array ,put the next element
at index 0 .Next after that goes at index 1
▪ front wraps around in the same way
▪ Use all the extra space that's left in the beginning of the array
after we dequeue!
 Circular Queue
Instead of viewing the array on the range 0, …, 15,
consider the indices being cyclic:
…, 15, 0, 1, …, 15, 0, 1, …, 15, 0, 1, …
This is referred to as a circular array

The circular queue is a clever type

of array-based queue Unlike our
previous array-based queue, we
never need to shift items with the
circular queue!
 Queue Implementation

• As in stacks, a queue can also be implemented

using Arrays or Linked-lists.
 The Circular Queue Implementation
#include <iostream>
#define SIZE bool isFull()
{
using namespace std;
if ((front == 0 && rear == SIZE - 1)
class Queue_cir { ||(front == rear + 1))
private: {
int data[SIZE], front, rear; return true;
}
public: return false;
Queue_cir() }
{ bool isEmpty(){
front = -1; // queue empty
if(front == -1) return true;
rear = -1; else return false;
} }
void enQueue(int element)
{ void deQueue()
if(isFull()) {
int element;
{
if(isEmpty()){
cout << "Queue is full"<<endl; cout << "Queue is empty" << endl;
} }
else { else {
if (front == -1) cout <<“Data dequeued”<< data[front];
front = 0; if (front == rear){
rear = (rear + 1) % SIZE; front = -1;
data[rear] = element; rear = -1;
cout <<"data queue"<<data[rear]<<endl; else {
front=(front+1) % SIZE;
}
} }
} }
 int main()
{
void display() Queue_cir Q;
{ Q.EnQueue(5);
/* Function to display status of Circular Queue */ Q.EnQueue(3);
int i; Q.EnQueue(7);
if(isEmpty()) { Q.display();
cout << endl << "Empty Queue" << endl; Q.DeQueue();
Q.display();
}
Q.EnQueue(2);
else Q.display();
{ Q.EnQueue(8);
cout <<"Rear at " << rear <<endl; Q.display();
cout <<"front at " << front <<endl; Q.DeQueue();
{for(int i=front; i!=rear;i=(i+1)%size) Q.display();
cout << arr[i]<<endl; Q.EnQueue(10);
cout<<arr[rear]<<endl; Q.display();
}} Q.EnQueue(20);
Q.display();
Q.EnQueue(30);
}
Stacks
• only last element can be Queues
deleted • only first element can
• ==>insert and delete at be deleted
one end • ==>insert at one end,
• last-in-first-out (LIFO) delete at other
• first-in-first-out (FIFO)
 Applications of queue data structure
• Queues are used to maintain the playlist in media players to add and remove the songs from the
play-list.

• The most common application is in client-server models. Multiple clients may be requesting
services from one or more servers. Some clients may have to wait while the servers are busy.
Those clients are placed in a queue and serviced in the order of arrival, banks, and airport security
use queues

• Queues are widely used as waiting lists for a single shared resource like a printer.