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]
➢ Queue follows First-in-First-out methodology i.e. the
data item stored first will be accessed first
QUEUE
OUT IN
Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7]
Front = NULL
Rear = NULL
Memory representation of a queue using arrays
➢ Let QUEUE be a linear queue. Two pointer variables
called FRONT and REAR
➢ The pointer variable FRONT contains the location of the
element to be removed
➢ The pointer variable REAR contains location of the last
element inserted.
➢ The condition FRONT = NULL indicates that the queue is
EMPTY
➢ The condition REAR = N -1 i.e. REAR = MAX-1 indicates
that the queue is FULL.
Operations performed on queues
➢ Queue() - Creates a new queue that is empty. It needs no
parameters
➢ Enqueue(item) - Inserts an element to the rear end of the
queue, accepts an argument and returns no value
➢ Dequeue() - Removes an element from the front end of
the queue, returns the removed element
➢ Isempty() - Used to check if the queue is empty or not,
returns a Boolean value
➢ Size() - Returns the number of elements in the queue,
needs no parameters but returns an integer
Types of queues
➢ Simple Queue
➢ Circular Queue
➢ Priority Queue
➢ Dequeue (Double Ended queue)
Simple Queue
In Simple queue insertion occurs at the rear end of the
list and deletion occurs at the front end of the list.
QUEUE
FRONT REAR
Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7]
DELETION INSERTION
Circular Queue
➢ Circular queue is also a linear data structure which
follows the principle of First-In-First-Out.
➢ But instead of ending the queue at the last position,
it again starts from the first position after the last.
➢ Hence making the queue behave like a circular data
structure
Or
A circular queue is a queue in which all nodes are
treated as circular such that the last node follows the
first node.
Circular Queue:
Insertion happens at Rear end
Deletion happens at Front end
OR
FRONT REAR
Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7]
Dequeue (Double Ended queue)
It is a queue in which insertion and deletion takes place
at both the ends, that is front and rear of the queue
Front Rear
Insertion Insertion
Deletion Q[0] Q[1] Q[2] Q[3] Q[4] Deletion
Q[5] Q[6] Q[7]
Priority Queue
➢ A priority queue is a queue that contains items that
have some preset priority.
➢ An element can be inserted or removed from any
position depending on some priority
10 0 20 4 30 2 59 1 70 3
A[0] A[1] A[2] A[3] A[4]
Priority Queue is an Extension of queue with
following properties
➢ Every item has a priority associated with it
➢ An element with high priority is dequeued before an
element with low priority
➢ If two elements have the same priority, they are
served according to their order in the queue
➢ In the above priority queue, element with maximum
ASCII value will have the highest priority
10 0 20 4 30 2 59 1 70 3
A[0] A[1] A[2] A[3] A[4]
Applications of queues
➢ Simulation
➢ Various features of operating system.
[Operating systems often maintain a queue of
processes that are ready to execute or that are
waiting for a particular event to occur.]
➢ Multi-programming platform systems
➢ Different type of scheduling algorithm
➢ Round robin technique or Algorithm
➢ Printer server routines
➢ Various applications software is also based on
queue data structure
