Overview of Queue

A stack is a data structure which stores elements one after others. 

A unique feature of this data structure is that we can use an array or linked list for its implementation. We are concerned about its functionality instead of it is implemented in code. Thus, the queue is an abstract data type. 

Consider a group of students waiting outside the professor's cabin in line for project submission. 



The queue increases when more people arrive. 

The queue decreases when professor calls the student and he/she goes inside the cabin. Note that other students do not shift to fill vacant space.


Thus people are served from First Come First Serve basis. This approach is known as First In First Out procedure. The process of addition of elements is called enqueue, and the process of deletion of elements is called dequeue.


We can deduce an analogy that people are equivalent to data elements. 

We use two variables for performing operations. 

  1. Rear/Back- Denotes the end for enqueueing.
  2. Front- Denotes the end for dequeuing.

There are two states which can be determined by the value of "front" pointer.

  1. Overflow- It means that the queue is full.
  2. Underflow- It means that the queue is empty.
                                   I

                                                                                                                                                 Image credits: Wikimedia Commons


Advantages of this data structure are:

  1. Easy insertion and deletion of elements.

Disadvantages of this data structure are:

  1. Elements cannot be randomly accessed.
  2. Upon deletion, the cleared memory space is not available for reuse. However, the circular queue overcomes this limitation.

Note: Advantages and disadvantages of data structure used for the implementation of the queue are reflected.


Applications of this data structure are:

  1. Used for the breadth-first-search algorithm.
  2. Can be used for interprocess communication.
  3. Interrupt handling by CPU.

Comments

Post a Comment

Popular posts from this blog

Overview of Tree Data Structure

Image
The tree is an abstract data structure which stores hierarchical data. For example, organisations have a hierarchical structure for employees. It is similar to the image given below. Several sergeants have to report to their respective captain. Now captains report to colonel. This colonel takes order from the general and assigns them to sergeants. Each of these consists of several levels. The general is on level 0, Colonel A and Colonel V are on level 1, Captain A, B and C are on level 2 and so on. Another terminology is height of the tree.  The height of a tree is longest path from the root node to any leaf node of the tree. Height of leaf node n=Level of leaf n+1.  Suppose we want to find the height of Private A. Height of private A= Level of Private A+1                                       =4+1                                       =5 In terms of computer programming, the general would be the root node of the tree. Colonel A and Colonel B are children of general. These two colonels
Read more

Overview of Three Dimensional Array

Image
A multidimensional array is an array consisting of more than 2 dimensions.  We can perceive three dimensions at most. To visual 3-dimensional array, let's take an example of a cube. Therefore, the array is cube[3][3][3]. For better understanding, represent a 3-D array as a combination of 2-D arrays.  Note: The two-dimensional array must have the same size. To conclude, a three dimensional array has arr[sub-array number][row][column]. Application of 3-D array: To represent real-world location co-ordinates. For storing spatial data such as MRI data. 3-D modelling.
Read more

Overview of Priority Queue

Image
  Consider a group of patients waiting outside the doctor's cabin for consultation. The functioning of the clinic is First In First Out basis like a queue . Suddenly, a new patient arrives with a condition which requires immediate treatment.  Then, the doctor would treat this patient first and then continue treating other patients like the previous order. In a priority queue, each data element has priority. So that crucial data does not get stuck. High priority elements are dequeue before low priority elements. If multiple elements have the same priority number, then the deletion is on a first come first serve basis. When  array implements a priority queue, an additional  2-D array is required to store the priority. When a  linked list implements a priority queue, the node stores the priority number. Applications of priority queue: Bandwidth management. Dijkstra Algorithm. Huffman Coding. Best First Search Algorithm. CPU Scheduling
Read more