Queue Data Structure
Queue is a linear data structure that always only FIFO order for storage and retrieval of data items. FIFO order means the items/data that will be inserted first also will be fetched first. Sometimes this order is also known as FCFS (First Come First Serve). FCFS order commonly used in CPU job scheduling.
Queue in daily life
There are multiple examples of queue in our daily life. Some commonly observed examples of queue are as given.
- Queue of peoples in front of banks
- Queue of students in assembly
- Queue of peoples for interview
- Queue of flying birds
- Queue of factory production items
Queue data structure fundamentally provide the following operations.
The process of inserting new data items in queue is called enqueue operation. New item is inserted from the rare of queue. To track where next item will be inserted in queue is handled by special pointer known as rare pointers. After every enqueue operation the rare pointer is moved to the next position.
The process of retrieving item from the queue is known as dequeue operation. Dequeue is always performed from the front of queue. The next item to be fetched is pointed by special pointer is known as front. Initially front pointer holds -1 value. After each dequeue operation the position of front is again reappropriate according to type of queue.
Types of Queue
There are four types of queue in data structure.
- Simple Queue
- Priority Queue
- Circular Queue
- Double Ended Queue
Queue data structure can be implemented by using following two techniques.
- Queue using array
- Queue using linked list
Queue using array
While implementing queue data structure there is initially an array is declared. Using array we can insert limited data items in queue. Additionally two variables also declared that track the insertion and deletion operations. These two pointers are known as front and rare pointers. Queue implementation using array is preferable where the data set is small and known in advance. This provides fast enqueue and dequeue operations.
Queue using linked list
Queue can also be implemented using linked list data structure. Linked list for implementation is preferable where the volume of data is not known in advance. This is more suitable for large data set. Queue using linked list also provide best memory utilization. There will be more memory utilized if we implement queue using linked list.
Uses of Queue
Some important uses of queue in computers are as follows.
- CPU scheduling
- Resource Allocation
Queue presentation and structure
Queue in memory is presented in the following way using linked list and array.
Structure in memory depends upon its implementation.