Queue is also a special type of linear data structure resulting after restriction of insertion and deletion operations on linear data structure. So, it can be implemented using either one-dimensional array or linked list. When the insertion operation is restricted to the other end in a linear data structure, then the resulting data structure is called as QUEUE. Insertion or addition of items is done at the end called REAR end and deletion of items is done from the other end called as FRONT end.
Assume a service center, with one serving window. The person comes for the service first is served first. If another person comes for the service, while the first person is being served, he has to wait. He will stand behind the first person. If any other persons come for the service, they will also stand one by one behind each other. The waiting persons frame a QUEUE. The persons are added into the QUEUE from end called REAR end. One person who enters the QUEUE first is served first. The deletion is done from the other end FRONT end. As an item is added to QUEUE at the REAR end and it is deletion from the other end, FRONT end, the item added first comes out first. So the data structure QUEUE is also called as FIFO, First In First Out structure. QUEUE has many applications in computer Field.
In a multiprocessing environment, the processes waiting for the CPU service are placed in a QUEUE called Ready Queue. In multiprocessing environment the CPU executes more than one process.
Representation of Queue:
The representation of QUEUE depends on the type of QUEUE. The QUEUE can be implemented either using a one-dimensional array or using Linked List. As there are different type of QUEUE depending on storage and the way the ADD and DELETE operations are done on the QUEUE.
Type of QUEUE:
1 Linear QUEUE: The elements are arranged in a QUEUE in linear order.
2 Circular QUEUE: The elements are arranged in a QUEUE by means of circular array.
3 DEQUE-Double Ended QUEUE: The ADD and DELETE operations are done from both the ends.
4 Priority QUEUE: The elements are stored in QUEUE with a characteristic called priority and DELETE operation depends on priority, high priority elements are deleted first (served first).