Benha University
Electrical Engineering Department Benha Faculty of Engineering
Today’s discussion…
Queue
Basic principles
Operation 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).
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)
Function: Adds newItem to the rear of the queue.
Preconditions: Queue has been initialized and is not full.
Postconditions: newItem is at rear of queue.
Dequeue (ItemType& item)
Function: Removes front item from queue.
Preconditions: Queue has been initialized and is not empty.
Postconditions: Front element has been removed from queue and
item is a copy of removed element.
Queue overflow
The condition resulting from trying to add an element onto a full queue.
if(!q.IsFull())
q.Enqueue(item);
Queue underflow
The condition resulting from trying to remove an element from an
empty queue.
if(!q.IsEmpty())
q.Dequeue(item);
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 in to 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, Linked-lists, Pointers and
Structures.
The Circular Queue Implementation
#include <iostream>
#define SIZE bool isFull()
{
using namespace std;
if ((front == 0 && rear == SIZE - 1)
class Queue { ||(front == rear + 1))
private: {
int data[SIZE], front, rear; return true;
}
public: return false;
Queue() }
{ 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;
}
} }
} }
void display()
{
/* Function to display status of Circular Queue */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
if (frront > rear)
{for(int i=frront; i!=rear;i=(i+1)%SIZE)
cout << data[i]<<endl;
cout << endl << "Rear at " << rear <<endl;
}
Else
{for (int i=frront; i<=rear; i=(i+1)%SIZE)
cout << data[i]<<endl;
cout << endl << "Rear at " << rear <<endl;
}
}}
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.
For example, in downloading from web server, those requests not
currently being downloaded are marked as “Queued”
