Queue (Data Structure)
Queue is an Abstract Data Type (ADT) based on the First-In-First-Out principle where an element inserted first is accessed/deleted/processed first. A queue has two ends called front and rear. Insertion of an element happens at the rear end. Deletion of an element happens at the front end.
A queue can be linear or circular, bounded or unbounded. Implementations can be from arrays or linked lists. Deque and priority queue are special queue types not based on the FIFO principle and serve their own purpose.
People standing in a queue (line) to buy a train ticket at a counter is an example of a real-life queue. The first person in the line is served first and exits the queue. A new person who wants to buy a ticket joins the end of the queue.
What are the common operations on a queue data structure?
Inserting an element to a queue is called enqueue operation. Element is added at the queue's rear end. For an unbounded queue, there's no limit to the queue length. Memory is dynamically allocated when required. An overflow condition occurs when one attempts to enqueue into a full bounded queue or when system memory is exhausted.
Deleting an element from a queue is called dequeue operation. Often implementations will support peek operation to inspect the element at the front of the queue. Whereas dequeue removes the element, peek doesn't. An underflow condition occurs when one attempts to dequeue from an empty queue.
Implementations may include interfaces to check if queue is full or empty. Implementations may allow us to inspect queue capacity (maximum limit) and queue size (number of elements currently in the queue).
How can queues be implemented?
Queue is an abstract data type. ADT defines the data and the operations that can be performed on that data while hiding the implementation complexities. So, a queue is implemented using concrete data types such as an array or a linked list.
For an array implementation of queues, we maintain two variables front and rear. After successful insertions, front points to the first element of the array and rear points to the last. In the case of static arrays, once rear reaches the maximum size, overflow occurs. We can solve this problem using dynamic arrays that are resized according to requirement.
For an linked list implementation of queues, each node of the linked list contains data and a pointer to the next node. Nodes need not be stored sequentially in memory. Initially when the queue is empty, front and rear point to NULL. After successful insertions, front points to the first node and rear points to the last node. There's no overflow unless the system memory gets exhausted.
Could you explain the circular queue?
Consider a case in which elements 1-8 are enqueued. The front points to 1 and rear points to 8. Let's dequeue 1 and 2. In the case of a linear queue, the first two memory locations become unavailable. One way to solve this is to shift the remaining elements forward so that last two memory locations become available for enqueuing. But shifting elements this way impacts runtime performance. Without shifting, the first two memory locations becomes unavailable. This is impractical when queues are based on static arrays.
A better option is to use a circular queue. In a circular queue, the first element location follows the last location in a circular structure. It was introduced to efficiently utilize the space that was wasted by a linear queue (without shifting). It can be implemented using a circular array, singly linked list, and doubly linked list.
Both linear and circular queues support the same operations but implementations differ.
What's a deque?
With FIFO queues, there's no quick way to dequeue from the back of the queue. Deque is a double-ended queue that solves this problem. It doesn't follow the FIFO principle. It's a very flexible data structure that allows enqueue and dequeue operations from both front and rear ends.
Operations supported by deque include front enqueue, front dequeue, rear enqueue, and rear dequeue. However, deques could be restricted to implement other data structures. For instance, if only rear enqueue and front dequeue are allowed, we get a queue. If only front enqueue and front dequeue are allowed, we get a stack. In general, there are two types of deques:
- Input-restricted deque that allows insertion at one end and deletion from both the ends.
- Output-restricted deque that allows insertion at both the ends and deletion from one end.
A deque is implemented using a circular array or a doubly-linked list. Deque finds application in the work-stealing algorithm for multiprocess scheduling. Each processor has a deque of tasks. Self-tasks are front dequeued but when a processor becomes free it rear dequeues from another processor's deque.
What's a priority queue?
A normal queue works on the FIFO principle, but there are some cases in which the elements need to be processed based on priority. For example, when multiple processes or programs are ready to execute, the highest priority one will be scheduled first.
A priority queue enqueues elements along with an associated priority value. When dequeuing, the element with the highest priority is processed first. In a max-priority queue, largest value implies highest priority. In a min-priority queue, smallest value implies highest priority.
Priority queues can be implemented with an array, linked list or tree but retrieval of the highest priority element is expensive. Instead, the heap data structure is used to implement a priority queue. Max-heap is a binary tree with a special property that the value of each node is greater than or equal to its children. This is used to implement the max-priority queue. Likewise, min-heap implements the min-priority queue.
A node is enqueued or dequeued keeping in mind that the heap does not violate any of its property.
What's the time and space complexity of operations on queues?
Since all elements need to be stored, the worst-case space complexity for a queue is O(n).
Enqueuing has O(1) average time complexity since only an element is inserted and the rear pointer is updated. With dynamic arrays, occasionally the operation will take longer if resizing is required. Peeking has O(1) worst-case time complexity. Dequeuing has O(1) worst-case time complexity. Dequeuing from a static array where elements are shifted to the front has O(n) worst-case time complexity.
With circular queues, enqueuing and dequeuing have worst-case time complexity of O(1). Queue capacity is fixed and no resizing happens.
With priority queues implemented as binary heaps, enqueuing and dequeuing have worst-case time complexity of O(log n) since elements have to be moved around to conform to binary heap properties. Peeking is at O(1).
What are some real-world applications of queues?
Linear queues are used to handle hardware and real-time system interrupts. First-Come-First-Serve and Round Robin process scheduling algorithms use linear queues extensively. The uniprocessor computer uses a linear queue to store the different applications to be processed in a queue.
Circular queues are used to loop over the list of processes in execution by an operating system until they exit the system. They are treated as buffers for maintaining a playlist in music players and listening to songs on loop.
In computer networking, routers and switches use priority queues to process packets. Operating system use priority queues for disk scheduling, memory management, semaphores, I/O buffers, and file access requests. Requests to shared resources like printers are managed using linear queues and priority queues if priorities are defined. Well-known algorithms such as Prim's, Dijkstra, and heap sort use priority queues.
What are some variants of queue?
Some applications don't consider overflow and underflow conditions as errors. Instead, they wish to wait for an available space when enqueuing into a full queue or wait for new data when dequeuing from an empty queue. This is exactly what the blocking queue provides. Implementations may support no waits, indefinite waits or waits with timeouts. It's used to synchronize producers and consumers that interact via the queue asynchronously.
A special case of a blocking queue is the synchronous queue. Enqueuing and dequeuing are synchronized. An element can be inserted only if a consumer is waiting to dequeue it. Thus, a synchronous queue has no storage capacity.
C++ Standard Template Library (STL) is released with support for three sequence containers:
priority_queue provide restricted interfaces to these containers. In particular,
deque can be used for queues;
deque for priority queues. For example,
queue<deque<int> > is a queue of integers using
deque container. The library provides heap-related functions that are used in the implementation of priority queues.
J2SE 5.0 (aka internal version 1.5) is released. New collection interfaces
BlockingQueue are introduced. Many concrete queue implementations are included. Priority queues are implemented using heaps. Blocking queues, delay queues and synchronous queues are introduced. . In 2006, J2SE 6.0 adds new collection interfaces
BlockingDeque along with concrete implementations
LinkedBlockingDeque. In 2011, J2SE 7.0 adds the interface
TransferQueue along with the implementation
- AWS. 2022. "Message Queues." Amazon Web Services. Accessed 2022-03-25.
- AWS. 2022b. "Amazon SQS delay queues." Developer Guide, Amazon Simple Queue Service, Amazon Web Services. Accessed 2022-03-25.
- Agarwal, Megh. 2021. "Applications of data structure." Nerd For Tech, on Medium, February 27. Updated 2021-02-27. Accessed 2022-03-09.
- Apache Kafka. 2022. "Apache Kafka Documentation." Kafka 3.1, Apache Software Foundation. Accessed 2022-03-25.
- Baeldung. 2021. "Priority Queue." Baeldung, June 18. Updated 2021-08-02. Accessed 2022-03-08.
- Brodal, G.S. 2013. "A Survey on Priority Queues." In: Brodnik A., López-Ortiz A., Raman V., Viola A. (eds), Space-Efficient Data Structures, Streams, and Algorithms, Lecture Notes in Computer Science, vol. 8066. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-642-40273-9_11. Accessed 2022-03-09.
- Bullinaria, John. 2019. "Data Structures and Algorithms." Lecture notes, University of Birmingham, March 27. Accessed 2022-02-23.
- Desai, Akshit. 2019. "Implementing Queue using Linked list." OpenGenus IQ, March 31. Accessed 2022-02-23.
- Gregg, Chris, and Julie Zelenski. 2020. "Lecture 4/15: Stacks and Queues." CS 106B: Programming Abstractions, Stanford University. Updated 2020-04-19. Accessed 2022-03-13.
- IBM. 2022. "Introduction to message queuing." Documentation, IBM MQ, v9.0, IBM, February 17. Accessed 2022-03-25.
- IIT Kharagpur. 2006. "Stacks and queues." CS13002 - Programming and Data Structures, IIT Kharagpur. Accessed 2022-02-23.
- Jenkov, Jakob. 2020. "Blocking Queues." Tutorial, January 15. Accessed 2022-03-25.
- Karumanchi, Narasimha. 2017. "Data Structures and Algorithms Made Easy." 5th edition, CareerMonk Publications. Accessed 2022-03-05.
- Kaswan, Amar. 2020. "Types of Queues." Baeldung CS, June 22. updated 2020-10-09. Accessed 2022-02-23.
- Lindemuth, Spencer. 2019. " Data Structure: Stack and Queue." DEV, November 02. Updated 2020-01-02. Accessed 2022-03-09.
- Minh, Nam Ha. 2022. "Java SE versions history." CodeJava. Accessed 2022-03-25.
- Mohapatra, Subasish. 2020. "Data Structures Using C." CET, Bhubaneswar. Accessed 2022-02-23.
- Northeastern University. 2018. "Lecture 29: Priority Queues and Heapsort." CS2510 - Fundamentals II: Introduction to Class-based Program Design, Northeastern University, Spring 2018. Accessed 2022-02-23.
- Oracle. 2004. "Collections Framework Enhancements." Documentation, Java SE 5, Oracle. Accessed 2022-03-09.
- Oracle. 2006. "Collections Framework Enhancements." Documentation, Java SE 6, Oracle. Accessed 2022-03-09.
- Oracle. 2011. "Collections Framework Enhancements in Java SE 7." Documentation, Java SE 7, Oracle. Accessed 2022-03-25.
- Oracle. 2021b. "Interface BlockingQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
- Oracle. 2021d. "Class DelayQueue<E extends Delayed>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
- Oracle. 2021l. "Class LinkedBlockingDeque<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
- Oracle. 2021s. "Class SynchronousQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
- Oracle. 2021t. "Interface TransferQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
- Padmaja. 2017. "Lecture Notes on Data Structures." Institute of Aeronautical Engineering (IARE), Hyderabad. Accessed 2022-02-23.
- Pandav, Rohan. 2021. "Applications of data structure." Geek Culture, on Medium, April 14. Updated 2021-04-14. Accessed 2022-03-05.
- RabbitMQ. 2022. "Routing." Tutorial, RabbitMQ. Accessed 2022-03-25.
- Rajinikanth. 2022. "Double Ended Queue Datastructure." BtechSmartClass. Accessed 2022-03-08.
- Sedgewick, Robert, and Kevin Wayne. 2020. "Queue." Princeton University, June 13. Accessed 2022-03-09.
- Sharma, Pankaj. 2018. "Double Ended Queue (Deque)." OpenGenus, June 18. Accessed 2022-03-08.
- Stepanov, Alexander, and Meng Lee. 1995. "The Standard Template Library." Hewlett-Packard Company, October 31. Accessed 2022-03-09.
- Thareja, Reema. 2014. "Data Structures Using C." Second edition, Oxford University Press. Accessed 2022-03-05.
- Vernon, Mary. 2005. "Priority Queues." CS 367: Introduction to Data Structures, University of Wisconsin, Spring 2005. Updated 2005-02-24. Accessed 2022-02-23.
- Vuillemin, Jean. 1978. "A data structure for manipulating priority queues." Communications of the ACM, vol. 21, no. 4, pp. 309–315, April. Accessed 2022-02-26.
- Wikipedia. 2021. "Multilevel Queue." Wikipedia. Updated 2021-07-02. Accessed 2022-02-26.
- Zanden, Brad Vander. 2010. "Queues." Lecture notes, CS140 - Data Structures, University of Tennessee, Fall 2010. Accessed 2022-02-23.
- Porter, Riley. 2017. "Pseudocode, ADTs, Priority Queues, Heaps." CSE 373: Data Structures & Algorithms, Winter 2017, University of Washington. Accessed 2022-02-24.
- Wikipedia. 2021. "Data Structures/Stacks and Queues" Wikipedia. Updated 2020-09-20. Accessed 2022-02-24.
- Tang, Daisy. 2013. "Queues." CS240 -- Lecture Notes, Cal Poly Pomona University. Updated 2013-07-01. Accessed 2022-02-24.