Queue
A queue is a linear list in which elements can be added at one end and elements can be
removed only at other end. So the information in this list is processed in same order as it was
received .Hence queue is called a FIFO structure.(First In First Out).
Ex: people waiting in a line at a bus stop.
The first person in queue is the first person to take bus. Whenever new person comes he joins
at end of the queue.
Type of queues
1. Linear Queue
2. Circular queue.
3. Priority queue
4.Deque
- Linear Queue
- It is a linear data structure.
- It is considered as ordered collection of items.
- It supports FIFO (First In First Out) property.
It has three components:
A Container of items that contains elements of queue.
A pointer front that points the first item of the queue.
A pointer rear that points the last item of the queue.
Insertion is performed from REAR end.
Deletion is performed from FRONT end.
Insertion operation is also known as ENQUEUE in queue.
Deletion operation is also known as DEQUEUE in queue.
Implementation of Queue
Queue can be implementing by two ways:
Array implementation.(Static and Dynamicarrays)
Linked List implementation.
Array Representation of Queue
In Array implementation FRONT pointer initialized with 0 and REAR initialized
with -1.
Circular Queue
In a normal Queue Data Structure, elements can be inserted until queue becomes full. But
once if queuIe becomes full, no more elements can be inserted until all the elements are
deletedfromthequeue
Priority Queue:
A priority queue is a collection of elements such that each element has been assigned a
priority and such that the order in which elements are deleted and processed comes from the
following rules:
1. An element of higher priority is processed before any element of lowerpriority.
2. two elements with same priority are processed according to the order in which they were
added to thequeue.
A prototype of a priority queue is time sharing system: programs of high priority are
processed first, and programs with the same priority form a standard queue.
Implementation of a Priority Queue
A priority queue can be implemented by creating a sorted or ordered list. A sorted list can be
used to store the elements so that when an element is to be removed, the queue need not be
searched for an element with the highest priority, since the element with the highest priority
is already in the first position. Insertions are handled by inserting the elements inorder.
Deque
Deque is a variation of queue data structure, pronounced “deck”, which stands for double
ended queue. In a deque values can be inserted at either the front or the back, A
peas in a straw is a good example..
:\n");
front and rear). That means, we can insert at both
performed at only one end
). doubleended
collection of
Queues and deques are used in a number of ways in computer applications. A printer, for
example, can only print one job at a time. During the time it is printing there may be many
different requests for other output to be printed. To handle this printer will maintain a queue of
pending print tasks. Since you want the results to be produced in the order that they are received,
a queue is the appropriate data structure.
For a deque the defining property is that elements can only be added or removed from the
end points. It is not possible to add or remove values from the middle of the collection.
Operations on deque
Insertfront
Deletefront
INsertrear
Deleterear
Deque Implementation
Usingarrays
Linked list –Doubly linkedlist
Applications of Queue:
1. It is used to schedule the jobs to be processed by theCPU.
2. When multiple users send print jobs to a printer, each printing job is kept in the printing
queue. Then the printer prints those jobs according to first in first out (FIFO)basis.
Breadth first search uses a queue data structure to find an element from a graph.
