Queue

Introduction

• Like Linked list and Stack, Queue is also an Abstract data structure.
• Queue is normally created or used when things don’t have to be processed immediately.
• A queue is considered as an Ordered list.

Definition

• A queue is another special kind of linear & non-contiguous data structure, where new data items or data elements are inserted(enqueue) at one specific end called REAR end, and delete an existing item from the other end(dequeue) called the FRONT end.

Features/Characteristics/Property

• A queue works on the principle of FIFO(first-in first-out)/FCFS(first come first serve)/LILO (Last in last out) i.e. the data item stored first will be accessed/deleted/removed/come out first from a queue normally and its vice-versa.
• A queue is open at both ends one for the insertion process and the other for the deletion process.
• In the queue, data does not remain in the data structure for a long time as in stacks.

Operations in Queue

• The basic operations in the queue are –

Representation/Implementation of Queue

• As in Stack, Queue is also implemented in two ways –

(a) As an Array(Static data structure)

(b) As a Linked List(Dynamic data structure)

Types of Queue

There are the following types of queues specifically formed to perform various operations –

(a) Simple/Normal Queue (b) Circular Queue (c) Deque [Double Ended Queue] (d)  Priority Queue (e) Hybrid Queue

(a) Simple/Normal/Fundamental Queue

• A simple queue is the most basic queue.
• Here, the enqueue operation takes place at the rear end, while the dequeue operation takes place at the front end.
• This queue is commonly used in process scheduling, disk scheduling, memory management, IO buffer, pipelining, call center phone systems, movies/railway ticket booking, and interrupt handling.

(b) Circular Queue

• A Simple queue in which the last node/front end is connected to the first node/rear end.
• A circular queue consumes less memory than a linear queue because in the queue while doing insertion after deletion operation it allocates an extra space the first remaining vacant but in the circular queue, the first is used as it comes immediately after the last.
• It is sometimes called a Ring Buffer.
• In a circular queue, memory is mostly utilized i.e. when we delete any element from a circular queue that position is used later because it is circular in structure.

(c) Deque [Double Ended Queue]

• Deque is an extension/modified form of the queue (to do some specific job), which provides insertion and deletion of items at both ends of the queue as per need. This data structure is called deque.
• A deque provides four operations – 
  • enqueue-front : insertion of element at the front.
  • dequeue-front : deletion of element at the front.
  • enqueue-rear : insertion of element at the rear.
  • dequeue-rear : deletion of element at the rear.
• There are two variations/categories of deque. They are –
  (i) Input Restricted Deque (IRD)
  • An Input restricted deque is a deque, which allows insertions at one end but allows deletions at both ends of the list.

(ii) Output Restricted Deque (ORD)

• • An output-restricted deque is a deque, which allows deletions at one end but allows insertions at both ends of the list.

(d)  Priority Queue

• A priority queue is a collection of elements such that each element has been assigned a priority value such that the order in which elements are deleted and processed.
• In a priority queue, an element with high priority is served/processed first or before an element with low priority.
• A priority queue follows certain rules during its processing. These are – 
   –   An element of higher priority value is processed first before any element of lower priority.
  –  Two elements with the same priority are processed according to the order in which they were added to the queue i.e. FCFS algorithm is followed.
• A prototype of a priority queue is a time-sharing system.
• An efficient implementation for the Priority Queue is to use a heap, which in turn can be used for sorting purposes.
• There are two kinds of priority queues normally created:- (a) Min priority queue. (b)Max priority queue.

(e) Hybrid Queue

• Hybrid queue is a unique type of queue created/used in special or rare cases of process scheduling.
• This queue is the combination of more than one type of queue. This combination depends on the requirements of the processing.

Advantages

• Queues can handle multiple data types during its operation.
• They are both flexible and fast.
• Queues can be of potentially infinite length compared with the use of fixed-length arrays.

Disadvantages

• Adding or deleting elements from the middle of the queue is complex one/impossible.
• With queues, data does not remain in the data structure for as long as with stacks.

Use/Applications

• There are a lot of applications of queues used in our daily life people services such as the people waiting in a line at a bank/cinema hall ticket counter/railway or bus ticket booking counter etc.
• In CPU/Process scheduling, Disk scheduling processes inside the computer. 
• In multi-user, multiprogramming, and time-sharing environments where a system(computer) handles several jobs at a time, to handle these jobs the concept of a queue is used.
• Round-robin scheduling/processing technique is implemented using a queue.
• In BFS(Breadth First Search) searching process of a graph.
• In Spooling & Buffering process.
• In Routing(at Router) and Switching(at Switch) process. 
• In Printers, during the printing process of jobs.