Wednesday, 6 December 2017

Queues Data Structure:

A queue is another special kind of list, where items are inserted at one end called the rear and deleted at the other end called the front. Another name for a queue is a “FIFO” or “First-in-first-out” list. The operations for a queue are analogues to those for a stack, the difference is that the insertions go at the end of the list, rather than the beginning. We shall use the following operations on queues:
a. enqueue: which inserts an element at the end of the queue.
b. dequeue: which deletes an element at the start of the queue.

Applications of Queue:
a. It is used to schedule the jobs to be processed by the CPU.
b. 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.
c. Breadth first search uses a queue data structure to find an element from a graph. 

Circular Queue Data Structure:
A more efficient queue representation is obtained by regarding the array Q[MAX] as circular. Any number of items could be placed on the queue. This implementation of a queue is called a circular queue because it uses its storage array as if it were a circle instead of a linear list.
There are two problems associated with linear queue. They are:
a. Time consuming: linear time to be spent in shifting the elements to the 
beginning of the queue.
b. Signaling queue full: even if the queue is having vacant position. 

Deque Data Structure:
In the preceding section we saw that a queue in which we insert items at one end and from which we remove items at the other end. In this section we examine an extension of the queue, which provides a means to insert and remove items at both ends of the queue. This data structure is a deque. The word deque is an acronym derived from double-ended queue. 

Priority Queue Data Structure:
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:
a. An element of higher priority is processed before any element of lower priority.
b. two elements with same priority are processed according to the order in which they were added to the queue.
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. An efficient implementation for the Priority Queue is to use heap, which in turn can be used for sorting purpose called heap sort.
An output restricted deque is a deque, which allows deletions at one end but allows insertions at both ends of the list.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput