Queues Link List Based Implementation
Queues Link list based implementation
In this tutorial, you will learn
1. Linked List Based Implementation of queues.
2. Learn the basic concept of priority queues.
What is the linked list based implementation of queues?
- class Queue
- linked_list l;
- bool isEmpty()
- return (l.isEmpty());
- void enQueue (int value)
- int deQueue()
- cout<<"\nQueue is Empty\t";
- return 0;
- int x=l.start()->info;
- return x;
Given above is the linked list based implementation of queues. Queues are implemented by linked list mostly when the information of maximum number of data numbers is not given. As linked list is dynamic, data can be added and removed with out worrying about the space allocated for that.
First, an object of linked list is made where data is to be stored. The first function is to check whether the queue is empty. This can be simply checked by checking whether the linked list is empty or not. Empty linked list implies that the queue is empty. For the function being used to check emptiness of queue, it is necessary that function to check emptiness of linked list must be public so that it may be accessed inside the class of queue.
The next function is to insert data. As the insertion and removal of data in case of queues (from both ends) does not require shifting of rest of data so we do not need additional counters. In case of linked list based implementation, this can be achieved simply by changing values of pointers. To add data, we simply use the function which inserts the data at end. Now, we should remember that for insertion, data is inserted in end and according to FIFO “First In First Out” concept, data should be remove from other end i.e. data should be removed from start. In enQueue function, we do not need any other operations because all the operations are covered in function for inserting data in linked list. Again, the function to insert data at end must be declared public while making the linked list class so that it may be accessed in the class of queues.
The last function is deQueue. This function is used to remove data from linked list. First of all, it is checked whether the queue is empty or not. If the queue is empty, you cannot delete data and attempting to delete a node from an empty linked list can make your code faulty and can give rise to runtime errors. Hence, the status of emptiness of queues must be checked. If the queue is not empty, we save the number we want to delete and then delete the node and lastly return the value. From your previous interaction with coding, you must know that if we return the value at some point, rest of function is not run. Also, the function to delete data from beginning must be public.
The complete code of queue along with linked list( actually more than required from linked list) is given. Do go through this to know how to use queues.
What is a priority queue?
A priority queue is a data structure like a normal queue but it has one additional feature which is that data is also given priority. The data of higher priority is served first. The question arises when 2 or more items have same priority. Actually, there is no specific rule for this. There are different approaches for that. Mostly, it is treated as a queue which means that the element coming first will be served first. But coders design their approach.
The idea of priority queues makes perfect sense. E.g. if someone is designing a management system for a hospital, he must take into account the emergencies. If there is a patient who must be treated immediately, he must be given higher priority. Similarly, in an office receiving many complaints, the complaints must be arranged with priority. E.g. in a cereal industry, there are two complaints. The extruder (used for cooking and cutting) needs to be repaired and the lights in an office need to be replaced, the extruder complaint must be dealt with earlier because the industry actually earns through this. Thus, priority queues find their uses in many different areas of coding. And if used properly, they can be used as a strong tool to make code more efficient.
NOTE: In next tutorial, priority queues will be ended and I would try to wrap up the course of Data Structures in some more lectures. Do go through codes of queues to understand their usage and implementation properly.