Queue
Department of Computer Science and Software
Engineering
Capital University of Sciences & Technology,
Islamabad Pakistan
CS2143 Data Structures
Queue
An Abstract Data type
A Linear Data Structure
Follows FIFO (First In First Out) principle
Open at both ends unlike stack
Real World Examples
Single lane one-way road
Ticket windows
Bus Stops etc
CS2143 Data Structures
Basic Operations
Enqueue => Adding an element to the queue
Dequeue => Removing an element from the
queue
Isfull => Checks if the queue is full
Isempty => Checks if the queue is empty
Peek => Gets the element at the front of
queue without removing it
Implementation of Queue as
Array
Four member variables
Array to store queue elements
Variables Front, Rear
Variable ItemsCount
Using Front, Rear to access queue
elements
Front: first queue element index
Rear: last queue element index
Front changes after each dequeue operation
Rear changes after each enqueue operation
Stacks VS Queues
Middle elements inaccessible
Stacks VS Queues
Pointer in
Stack
Pointers
in Queue
Where to Best Use What?
Stacks Queues
For storing data It is useful to store
elements, when the data elements
you need recently when you want to
added object to be treat or process
treated / processed element which is
first added first
E.g.: Recent
operations
performed in word
Operations of Stacks VS
Queues
For an empty stack set top to • For an empty queue set rear
-1 and front to -1
isempty() : Return true if • isempty() : Return true if
stack is empty, return false stack is empty, return false
otherwise
otherwise
• isfull(): returns full if the
Is full(): returns full if the queue is full
stack is full • Peek(): Returns the
top() : Return top element of element at front
stack • dequeue() : Remove an
pop() : Remove the top element from the front of
element from the stack the queue
push(x) : Add element x at • enqueue(x) : Add element
x at the rear of the queue
the top of the stack
CS2143 Data Structures
Implementation – Queue
public class Queue
{private:
int array [5];
int front, rear, count;
public:
Queue() …
bool isEmpty() …
void display() …
void dequeue() …
int peek()…
bool isFull() …
void enqueue (int value) …
}
CS2143 Data Structures
Implementation –
Constructor
The constructor of the class Queue sets the front and
the rear of the queue to -1, indicating an empty queue
Also the count variable indicating the total number of
elements in the queue, is set to 0
Queue()
{
rear
front = rear = -1;
count = 0; 2
0 1
}
CS2143 Data Structures
front
Implementation – isEmpty()
This function checks the front of the queue to
determine if the queue is empty
If the value of the front indicator is -1 then the queue is empty
Otherwise there can be multiple data stored in the queue
bool isEmpty()
{
if (front== -1)
return true;
else
return false;
}
CS2143 Data Structures
Implementation – isfull()
This function checks the rear of the queue to
determine if the queue is full
If the value of the rear indicator equals the size of the queue – 1,then the
stack can be called full
bool isFull()
{
if (front ==4)
return true;
else
return false;
}
CS2143 Data Structures
Implementation –peek()
This function helps to see data at the front of
the queue
int peek()
{
return array[front];
}
CS2143 Data Structures
Implementation –
enqueue ()
It adds an element public void enqueue(int value)
at the rear of the {
queue if (isFull())
cout<<“Queue is Full!”;
It takes as else
argument an {
integer value to be if(front == -1)
front = 0;
inserted array[++rear] = value;
It first checks if count++;
}
there is room left
}
in the queue
If no room is left, it throws a
QueueFull exception.
CS2143 Data Structures
Implementation –
dequeue ()
void dequeue ()
The dequeue method
{
removes an item from if (isEmpty())
the front of the queue cout << "Queue is Empty!";
The method first else
checks if the queue is {
empty front++;
If the queue is empty, it throws a
EmptyQueue Exception count--;
Otherwise, it simply decrements
the count of enqueued items by
if (front == rear)
one and returns the item found at front = rear = -1;
the front of the queue
}
CS2143 Data Structures }
Draw Back of Linear Queue
Once the queue is full, even though few
elements from the front are deleted and some
occupied space is relieved, it is not possible
to add anymore new elements, as the rear
has already reached the Queue’s rear most
position
Types of Queues – 2
• Linear data structure in which the
operations are performed based on FIFO
Circ (First In First Out) principle and the last
ular position is connected back to the first
Que position to make a circle.
ue
Example
Components of Circular
Queue
Size
Array
Index Locators
Rear
Front
Constructor
Checker Functions
Is Full
Is Empty
Functions:
Enqueue
Dequeue
Display
Implementation -
Constructor
CircularQueue()
{
rear = front = -1;
}
Implementation – IsEmpty()
bool isEmpty()
{
if(front == -1 )
{
return true;
}
else
{
return false;
}
}
Implementation – IsFull()
bool isFull()
{
if(front == 0 && rear == SIZE - 1)
{ return true; }
return false;
}
Implementation – Enqueue()
void enqueue(int x)
{
if(isFull())
cout << "Queue is full";
else
{
if(front == -1)
front = 0; rear = (rear + 1) % SIZE; // going round and round concept
array[rear] = x; // inserting the element
cout << endl << "Inserted " << x << endl;
}
}
Implementation – Dequeue()
void dequeue()
{
if(isEmpty())
cout << "Queue is empty" << endl;
else
{
if(front == rear) // only one element in queue, reset queue after removal
{
front = -1;
rear = -1;
}
else
front = (front+1) % SIZE;
}
}
Applications of Queues
Used in waiting list
Queues are useful in a time-sharing multi-
user operating systems where many users
share the CPU simultaneously
Mainly used in scheduling and process
sharing
CS2143 Data Structures
