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 operations

Queue data structure fundamentally provide the following operations.

• Enqueue
• Dequeue

Enqueue Operation

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.

Dequeue Operation

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.

1. Simple Queue
2. Priority Queue
3. Circular Queue
4. Double Ended Queue

Queue implementation

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.

1. CPU scheduling
2. 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.