Front points to the index of the queue from where we can delete an element. Rear points to that index of the queue from where we insert elements.<\/p>\n
We can represent the queue as follows:<\/p>\n
There are various types of queue data structures such as: Let us see each of them in detail now:<\/p>\n A linear queue is a simple queue in which insertion occurs at one end and deletion occurs at the other end. The basic operations that we can perform on a queue are:<\/p>\n a. enqueue():<\/strong> To insert an element into the queue.<\/p>\n b. dequeue():<\/strong> To delete an element from a queue.<\/p>\n c. peek():<\/strong> To print\/display the element at the front without deleting it.<\/p>\n d. isfull():<\/strong> To check if the queue is full or not.<\/p>\n e. isempty()<\/strong>: To check if the queue is empty or not.<\/p>\n Out of the given operations, the first two operations are the most important. The rest three are used to improve the efficiency of the first two operations while implementation.<\/p>\n The queue has two ends pointed by Front and Rear. The enqueue() operation is always performed at the Rear end.<\/p>\n While performing enqueue() operation, we always check whether the queue is full or not. In case the queue is full, we return an overflow error. Otherwise, we insert the element at the rear end and make the Rear point to the next position in the queue.<\/p>\n For example, suppose we have a queue with elements A, B, C, D and we wish to insert E into the queue. We can insert this new element into the queue as follows:<\/p>\n The pseudo-code for the enqueue() operation is shown below:<\/strong><\/p>\n The time complexity of enqueue() operation is of the order O(1).<\/strong><\/p>\n Thus, in enqueue operation, we need to remember the following key points:<\/p>\n While performing enqueue() operation algorithmically, we check three different cases. These cases are:<\/p>\n When the queue is full, the rear will point to the last index i.e. Size of queue – 1 position. In that case, we will return an overflow error and exit the program.<\/p>\n When the queue is empty, initially both the front and rear will point to an invalid index say -1. In this case, when we insert an element, both will start pointing to index 0.<\/p>\n Since the queue has only one element, in this case, both the front and rear for a queue will be the same.<\/p>\n If the queue is neither empty nor full, we just increase the value of the rear pointer by one and insert the new element.<\/p>\n This operation is used to delete an element from the queue. dequeue() operation is always performed at the \u2018Front\u2019 of the queue.<\/p>\n While performing dequeue() operation, we always make sure that the queue is not already empty. If the queue is already empty, there is nothing to delete. In that case, we return an underflow error. If the queue is not empty, we delete the front node and move the front pointer to the next node.<\/p>\n The following diagram depicts the deletion operation:<\/p>\n The pseudo-code for dequeue() operation is:<\/strong><\/p>\n The time complexity of the dequeue() operation is O(1) when we implement the queue using arrays.<\/p>\n In case of dequeue() operation:<\/p>\n Whenever the rear points to the SIZE (i.e. the maximum size of the queue), the isfull() operation returns true. The code for the isfull() operation is as shown below:<\/p>\n It will return true only if the queue is empty. Just like isfull() operation, it is a boolean operation and so it returns either true or false.<\/p>\n If the value of the Front is MIN or pointing to an invalid index, then the queue is empty. Thus, this operation will return true.<\/p>\n The code for isEmpty() operation is:<\/strong><\/p>\n This operation returns the value of the data element at the front of the queue without deleting it. Its code will be:<\/p>\n Queues are mainly used for ordering items into a particular order of performance or when there are multiple users for a single resource.<\/p>\n The major applications of the queue data structure are:<\/p>\n We can make use of queues to transfer data asynchronously. Asynchronous transfer means when the rate of transmission of data is not the same between two processes. For example, queues are used in pipes, file input\/output, sockets for asynchronous data transfer.<\/p>\n Whenever we need to make the process wait for a single shared resource, we maintain them inside a queue. For example, printer, CPU, etc are the shared resources.<\/p>\n Queues are useful as a buffer to store the data primarily whenever required. For example, the queue is used as a buffer in the case of MP3 players. CD players, etc.<\/p>\n Whenever a process gets interrupted, it is sent back and made to wait in the queue. Thus, queue helps in interrupt handling.<\/p>\n Queues help maintain any kinds of lists. We can maintain a playlist of songs or other media with the help of queues.<\/p>\n A circular queue overcomes the drawback of a linear queue. In the circular queue, all the nodes are in a circle interconnected to each other. The last element of the queue is connected to the first element. It also follows the FIFO approach. It is also known as the Ring buffer.<\/strong><\/p>\n Suppose we have the letters of the word \u201cTECHVIDVAN\u201d. It will be represented in the circular queue as follows:<\/p>\n Following are the operations that we can perform on circular queues: If the queue is full, return overflow. If the queue is empty, the rear and front both will point to -1 initially. Insert the new element at 0, and point both front and rear to the 0th index.<\/p>\n Otherwise, insert the lament and increment rear by one.<\/p>\n The pseudo-code will be as follows:<\/p>\n Implementation of Enqueue in C:<\/strong><\/p>\n It helps to delete elements from the rear end.<\/p>\n If the queue is already empty, return underflow. Otherwise, delete the element and decrement the value of the rear by one.<\/p>\n While removing the last element, set both front and rear =-1.<\/p>\n The pseudo-code of the dequeue function is:<\/p>\n C implementation of dequeue operation:<\/strong><\/p>\n This operation returns the size of the circular queue. Its implementation in C is shown below:<\/p>\n We can make use of both arrays as well as linked lists to implement a circular queue. But, the linked list implementation is more efficient. The worst-case time complexity of linked list implementation is O(n).<\/p>\n It returns the value of the element at the front without deleting it.<\/p>\n Circular queue comes into use in the following cases:<\/p>\n Circular queues help in better memory management in comparison to linear queues. A circular queue utilizes unused memory very well. This can be shown as follows:<\/p>\n <\/p>\n In this case, even though we have space for 3 elements in the queue, but it will not be able to add the elements. This is because the rear is pointing at the end.<\/p>\n We can overcome this problem using a circular queue as shown:<\/p>\n Since it is circular, we can add elements up to the full capacity of the queue.<\/p>\n All the processes waiting for their turn can be placed in a circular queue.<\/p>\n In computerized traffic systems, circular queues help to switch between the different traffic lights circularly.<\/p>\n In a priority queue, each element has some priority attached to it. This priority decides the order of execution of nodes inside the queue.<\/p>\n A priority queue is designed in such a way that insertion occurs according to the arrival of elements. The deletion occurs on the basis of the priority of execution.<\/p>\n 1. Ascending order priority queue:<\/strong> In ascending priority queue, we give higher priority to a smaller number as shown:<\/p>\n 2. Descending order priority queue:<\/strong> It gives high priority to a higher value number.<\/p>\n We can implement a priority queue using four different data structures: The heap data structure is based on a complete binary tree. It satisfies heap properties. There are two types of heap data structure:<\/p>\n 1. Max heap:<\/strong> In a max-heap, for every node, the value of the parent node is greater than both of its child nodes as shown:<\/p>\n 2. Min heap:<\/strong> In a min-heap, the value of every parent node is less than the value of both of its children.<\/p>\n We first insert the element in the available memory slot such that it does not violate the properties of a complete binary tree. If the element is not at the right place i.e. it violates the max-heap property, we compare it to its parent node.<\/p>\n If the value of the parent node is less than the child node, we swap them. These comparisons and swaps continue until all the nodes are in their right place.<\/p>\n![\"Queue](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/TV-Queue-normal-images-01.jpg\")
<\/a><\/p>\nTypes of Queue<\/h3>\n
\n1. Linear queue
\n2. Circular queue
\n3. Deque
\n4. Priority queue<\/p>\n1. Linear queue<\/h4>\n
\nIn a linear queue, we are sometimes not able to utilize memory effectively. This is because insertion can be performed only at the rear end.<\/p>\nBasic operations on Linear Queue:<\/h4>\n
a. enqueue() Operation in Queue<\/h5>\n
<\/a><\/p>\nvoid enQueue(int key) \/\/key is the element to be inserted\n{\n if(Rear == SIZE-1){ \/\/SIZE denotes the maximum size of the queue\n print(\"Overflow\"); \/\/Prints overflow if the queue is already full.\n return;\n }\n if(Front == -1){ \/\/If the queue is empty\n Front = 0; \/\/whenever the queue is empty, front always point to -1 initially\n Rear = 0; \/\/'Queue being empty' is a rare case when both front and rear point to the same index\n Queue[Rear] = key;\n }\n else{\n Rear = Rear + 1; \/\/Making rear point to the next index of the queue\n Queue[Rear] = key;\n }\n}\n<\/pre>\n\n
b. dequeue() Operation<\/h5>\n
<\/a><\/p>\nint deQueue()\n{\n int temp; \/\/We declare 'temp' variable to store the value of element to be deleted\n if(Front == -1) \/\/If the queue is empty\n {\n printf(\"Underflow\");\n break;\n }\n if(Front == Rear) \/\/If the queue has only one element\n {\n temp = Queue[Front];\n Front = -1;\n Rear = -1;\n return temp;\n }\n else\n {\n temp = Queue[Front];\n Front = Front + 1;\n return temp;\n }\n}\n<\/pre>\n\n
c. isfull() Operation in Queue<\/h5>\n
\nisfull() operation is a boolean operation i.e. it either returns true or false.<\/p>\nbool isfull() {\n if(Rear == SIZE-1)\n return true;\n else\n return false;\n}\n\n<\/pre>\nd. isEmpty() Operation<\/h5>\n
bool isEmpty() {\n if(000Front < 0 || Front > Rear) \n return true;\n else\n return false;\n}\n<\/pre>\ne. peek() Operation in queue<\/h5>\n
int peek() {\n return Queue[Front];\n}\n<\/pre>\nApplications of Linear Queue<\/h3>\n
1. Asynchronous data transfer<\/h4>\n
2. Multiple users for a single resource<\/h4>\n
3. Used as buffers<\/h4>\n
4. Interrupt handling<\/h4>\n
5. Maintain playlists<\/h4>\n
Circular Queue<\/h3>\n
Representation of Circular queue:<\/h4>\n
<\/a><\/p>\nOperations on Circular queue:<\/h4>\n
\n1. Front( ):<\/strong> It returns the element at which the front pointer is pointing.
\n2. Rear( ):<\/strong> It returns the last element of the circular queue.
\n3. Enqueue( ):<\/strong> It helps to insert a new element at the rear end of the queue.
\n4. Dequeue( ):<\/strong> It deletes the last element of the circular list from the front end.<\/p>\nArray implementation of Circular queue:<\/h3>\n
1. Enqueue( ):<\/h4>\n
Enqueue_operationint key(){\n if (rear+1)%max = front\n {\n print(\"overflow\");\n break;\n }\n if (front == -1 && rear == -1)\n {\n front = rear = 0;\n CircularQueue[Rear] = key;\n }\n else\n {\n Rear = Rear+1;\n set CircularQueue[Rear] = key;\n } \n}\n<\/pre>\nvoid Enqueue(int key) \n{ \n if(Front==-1 && Rear==-1) \n { \n Front = Rear = 0; \n Counter = 1;\n CircularQueue[Rear] = key; \n } \n else if((rear+1) % max == Front) \n { \n printf(\"OverFlow\"); \n break;\n } \n else \n { \n Rear = (Rear+1) % max; \n CircularQueue[Rear] = key; \n Counter++; \n } \n} \n<\/pre>\n2. Dequeue( ):<\/h4>\n
Dequeue_operation{\n if (Front == -1)\n {\n display(\"underflow\");\n break;\n }\n if (Front == Rear)\n {\n Front = Rear = -1;\n }\n else{\n if(Front = SIZE-1)\n Front = 0\n else\n Front = Front + 1\n }\n}\n<\/pre>\nint dequeue() \n{ \n int Counter=0;\n if(Front == -1 && Rear== -1) \n printf(\"Underflow\"); \n \n else if(Front == Rear) \n { \n front=-1; \n rear=-1; \n Counter=0; \n }\n else \n front=(front+1)%max; \n return queue[front];\n Counter--;\n}\n<\/pre>\n3. size( ):<\/h4>\n
int size(int Count) \n return Count;\n<\/pre>\n
Linked List implementation of Circular queue:<\/h3>\n
1. Enqueue( ):<\/h4>\n
void Enqueue(struct Node* NewNode , int key) \n{ \n NewNode->data = key; \n Newnode->Next = 0; \n if(Rear==-1) \n { \n Front = Rear = NewNode; \n Rear->Next = Front; \n } \n else \n { \n Rear->Next = NewNode; \n Rear = NewNode; \n Rear->Next = Front; \n } \n}\n<\/pre>\n2. Dequeue( ):<\/h4>\n
void Dequeue() \n{ \n if(Front==-1 && Rear == -1) \n { \n printf(\"Underflow\"); \n break;\n } \n else if(Front == Rear) \n Front = Rear = -1; \n else \n { \n Front = Front->Next; \n Rear->Next = Front; \n } \n} \n<\/pre>\n3. peek( ):<\/h4>\n
int peek() \n{ \n if(Front==-1 && Rear==-1) \n printf(\"Underflow- EMpty queue\"); \n else \n return Front->data; \n} \n<\/pre>\nApplications of Circular queue:<\/h3>\n
1. Memory management<\/h4>\n
<\/a><\/p>\n<\/a><\/p>\n2. CPU scheduling<\/h4>\n
3. Traffic system<\/h4>\n
Priority queue:<\/h3>\n
Types of Priority Queue:<\/h4>\n
<\/a><\/p>\n<\/a><\/p>\nImplementation of Priority Queue:<\/h4>\n
\n1. Array
\n2. Linked list
\n3. Binary search tree
\n4. Heap data structure<\/p>\nHeap data structure:<\/h4>\n
<\/a><\/p>\n<\/a><\/p>\nOperations on Priority Queue:<\/h4>\n
a. Enqueue operation using Max-heap:<\/h5>\n