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.

Discussion

  • What are the common operations on a queue data structure?
    Operations on a queue. Source: Lindemuth 2019.
    Operations on a queue. Source: Lindemuth 2019.

    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).

    Queue implementations maintain front and rear variables or pointers that are essential to most operations.

  • How can queues be implemented?
    Implementation of queue. Source: Desai 2019.
    Implementation of queue. Source: Desai 2019.

    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?
    Linear queue versus circular queue. Source: Devopedia 2022.
    Linear queue versus circular queue. Source: Devopedia 2022.

    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?
    Input-restricted (top) vs output-restricted (bottom) deques. Source: Adapted from Rajinikanth 2022.
    Input-restricted (top) vs output-restricted (bottom) deques. Source: Adapted from Rajinikanth 2022.

    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?
    Types of priority queues implemented using binary heaps. Source: Thareja 2014, fig. 12.1.
    Types of priority queues implemented using binary heaps. Source: Thareja 2014, fig. 12.1.

    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?
    Time and space complexity of queues. Source: Devopedia 2022.
    Time and space complexity of queues. Source: Devopedia 2022.

    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 deques, enqueuing and dequeuing from either end have worst-case time complexity of O(1). Where supported, enqueuing and dequeuing from the middle is at O(n). Peeking at either end is at O(1).

    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.

    Messaging systems use queues. Producers write to message queues. One or more consumers read from those queues. Apache Kafka, Amazon Simple Queue Service (SQS), and RabbitMQ are some examples.

  • What are some variants of queue?
    Summary of BlockingQueue methods in Java. Source: Oracle 2021b.
    Summary of BlockingQueue methods in Java. Source: Oracle 2021b.

    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.

    Another type of blocking queue is the transfer queue in which producers may wait for consumers to dequeue an element. This is useful in message passing applications.

    Sometimes we don't want to overwhelm consumers with too many messages. Delay queue is another blocking queue that delays dequeuing operations. Only after the delay time expires, dequeuing can happen.

Milestones

1960

FCFS and Round Robin scheduling algorithms use queues for process scheduling in operating systems.

1964

Williams introduces binary heap that forms the basis of priority queues. It supports insertion of an element and extraction of the element with minimum value.

1978

Vuillemin presents a type of priority queue that he calls binomial queue. It supports primitive operations such as union, update and search.

1995

C++ Standard Template Library (STL) is released with support for three sequence containers: vector, list and deque. STL's stack, queue and priority_queue provide restricted interfaces to these containers. In particular, list and deque can be used for queues; vector and 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.

2004

J2SE 5.0 (aka internal version 1.5) is released. New collection interfaces Queue and 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 Deque and BlockingDeque along with concrete implementations ArrayDeque and LinkedBlockingDeque. In 2011, J2SE 7.0 adds the interface TransferQueue along with the implementation LinkedTransferQueue.

Sample Code

  • // Source: https://algs4.cs.princeton.edu/13stacks/Queue.java
// Accessed 2022-03-24
// Implementing an unbounded queue implemented as a linked list
 
// To compile, add to build.gradle within dependencies { ... }
// implementation group: 'edu.princeton.cs', name: 'algs4', version: '1.0.2'
 
// Example program args: a b c - d -  - - -
// : - will invoke dequeue operation
 
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
 
public class Queue<Item> implements Iterable<Item> {
    private Node<Item> first;    // beginning of queue
    private Node<Item> last;     // end of queue
    private int n;               // number of elements on queue
 
    // helper linked list class
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }
 
    /**
     * Initializes an empty queue.
     */
    public Queue() {
        first = null;
        last  = null;
        n = 0;
    }
 
    /**
     * Returns true if this queue is empty.
     *
     * @return {@code true} if this queue is empty; {@code false} otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }
 
    /**
     * Returns the number of items in this queue.
     *
     * @return the number of items in this queue
     */
    public int size() {
        return n;
    }
 
    /**
     * Returns the item least recently added to this queue.
     *
     * @return the item least recently added to this queue
     * @throws NoSuchElementException if this queue is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }
 
    /**
     * Adds the item to this queue.
     *
     * @param  item the item to add
     */
    public void enqueue(Item item) {
        Node<Item> oldlast = last;
        last = new Node<Item>();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else           oldlast.next = last;
        n++;
    }
 
    /**
     * Removes and returns the item on this queue that was least recently added.
     *
     * @return the item on this queue that was least recently added
     * @throws NoSuchElementException if this queue is empty
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = first.item;
        first = first.next;
        n--;
        if (isEmpty()) last = null;   // to avoid loitering
        return item;
    }
 
    /**
     * Returns a string representation of this queue.
     *
     * @return the sequence of items in FIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this) {
            s.append(item);
            s.append(' ');
        }
        return s.toString();
    } 
 
    /**
     * Returns an iterator that iterates over the items in this queue in FIFO order.
     *
     * @return an iterator that iterates over the items in this queue in FIFO order
     */
    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);  
    }
 
    // an iterator, doesn't implement remove() since it's optional
    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;
 
        public LinkedIterator(Node<Item> first) {
            current = first;
        }
 
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }
 
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }
 
 
    /**
     * Unit tests the {@code Queue} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        Queue<String> queue = new Queue<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-"))
                queue.enqueue(item);
            else if (!queue.isEmpty())
                StdOut.print(queue.dequeue() + " ");
            StdOut.println("(" + queue.size() + " left on queue)");
        }
    }
}
 

References

  1. AWS. 2022. "Message Queues." Amazon Web Services. Accessed 2022-03-25.
  2. AWS. 2022b. "Amazon SQS delay queues." Developer Guide, Amazon Simple Queue Service, Amazon Web Services. Accessed 2022-03-25.
  3. Agarwal, Megh. 2021. "Applications of data structure." Nerd For Tech, on Medium, February 27. Updated 2021-02-27. Accessed 2022-03-09.
  4. Apache Kafka. 2022. "Apache Kafka Documentation." Kafka 3.1, Apache Software Foundation. Accessed 2022-03-25.
  5. Baeldung. 2021. "Priority Queue." Baeldung, June 18. Updated 2021-08-02. Accessed 2022-03-08.
  6. 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.
  7. Bullinaria, John. 2019. "Data Structures and Algorithms." Lecture notes, University of Birmingham, March 27. Accessed 2022-02-23.
  8. Desai, Akshit. 2019. "Implementing Queue using Linked list." OpenGenus IQ, March 31. Accessed 2022-02-23.
  9. 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.
  10. IBM. 2022. "Introduction to message queuing." Documentation, IBM MQ, v9.0, IBM, February 17. Accessed 2022-03-25.
  11. IIT Kharagpur. 2006. "Stacks and queues." CS13002 - Programming and Data Structures, IIT Kharagpur. Accessed 2022-02-23.
  12. Jenkov, Jakob. 2020. "Blocking Queues." Tutorial, January 15. Accessed 2022-03-25.
  13. Karumanchi, Narasimha. 2017. "Data Structures and Algorithms Made Easy." 5th edition, CareerMonk Publications. Accessed 2022-03-05.
  14. Kaswan, Amar. 2020. "Types of Queues." Baeldung CS, June 22. updated 2020-10-09. Accessed 2022-02-23.
  15. Lindemuth, Spencer. 2019. " Data Structure: Stack and Queue." DEV, November 02. Updated 2020-01-02. Accessed 2022-03-09.
  16. Minh, Nam Ha. 2022. "Java SE versions history." CodeJava. Accessed 2022-03-25.
  17. Mohapatra, Subasish. 2020. "Data Structures Using C." CET, Bhubaneswar. Accessed 2022-02-23.
  18. 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.
  19. Oracle. 2004. "Collections Framework Enhancements." Documentation, Java SE 5, Oracle. Accessed 2022-03-09.
  20. Oracle. 2006. "Collections Framework Enhancements." Documentation, Java SE 6, Oracle. Accessed 2022-03-09.
  21. Oracle. 2011. "Collections Framework Enhancements in Java SE 7." Documentation, Java SE 7, Oracle. Accessed 2022-03-25.
  22. Oracle. 2021b. "Interface BlockingQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
  23. Oracle. 2021d. "Class DelayQueue<E extends Delayed>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
  24. Oracle. 2021l. "Class LinkedBlockingDeque<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
  25. Oracle. 2021s. "Class SynchronousQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
  26. Oracle. 2021t. "Interface TransferQueue<E>." Oracle, September 13. Updated 2022-03-02. Accessed 2022-03-13.
  27. Padmaja. 2017. "Lecture Notes on Data Structures." Institute of Aeronautical Engineering (IARE), Hyderabad. Accessed 2022-02-23.
  28. Pandav, Rohan. 2021. "Applications of data structure." Geek Culture, on Medium, April 14. Updated 2021-04-14. Accessed 2022-03-05.
  29. RabbitMQ. 2022. "Routing." Tutorial, RabbitMQ. Accessed 2022-03-25.
  30. Rajinikanth. 2022. "Double Ended Queue Datastructure." BtechSmartClass. Accessed 2022-03-08.
  31. Sedgewick, Robert, and Kevin Wayne. 2020. "Queue." Princeton University, June 13. Accessed 2022-03-09.
  32. Sharma, Pankaj. 2018. "Double Ended Queue (Deque)." OpenGenus, June 18. Accessed 2022-03-08.
  33. Stepanov, Alexander, and Meng Lee. 1995. "The Standard Template Library." Hewlett-Packard Company, October 31. Accessed 2022-03-09.
  34. Thareja, Reema. 2014. "Data Structures Using C." Second edition, Oxford University Press. Accessed 2022-03-05.
  35. Vernon, Mary. 2005. "Priority Queues." CS 367: Introduction to Data Structures, University of Wisconsin, Spring 2005. Updated 2005-02-24. Accessed 2022-02-23.
  36. 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.
  37. Wikipedia. 2021. "Multilevel Queue." Wikipedia. Updated 2021-07-02. Accessed 2022-02-26.
  38. Zanden, Brad Vander. 2010. "Queues." Lecture notes, CS140 - Data Structures, University of Tennessee, Fall 2010. Accessed 2022-02-23.

Further Reading

  1. Porter, Riley. 2017. "Pseudocode, ADTs, Priority Queues, Heaps." CSE 373: Data Structures & Algorithms, Winter 2017, University of Washington. Accessed 2022-02-24.
  2. Wikipedia. 2021. "Data Structures/Stacks and Queues" Wikipedia. Updated 2020-09-20. Accessed 2022-02-24.
  3. Tang, Daisy. 2013. "Queues." CS240 -- Lecture Notes, Cal Poly Pomona University. Updated 2013-07-01. Accessed 2022-02-24.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
User avatar harshpreet0508
32
22
4245
Avatar of user arvindpdmn arvindpdmn
5
10
2887
DevCoins due to articles, chats, their likes and article hits are included.
1770
Words
2
Authors
37
Edits
32
Chats
1
Likes
24K
Hits

Cite As

Devopedia. 2022. "Queue (Data Structure)." Version 37, March 25. Accessed 2024-06-25. https://devopedia.org/queue-data-structure
Contributed by
2 authors

Last updated on
2022-03-25 16:11:02
data algorithms data type performance

See Also