This article explains the fundamental differences between three important abstract data types (ADTs) in computer science: Queue, Deque, and Priority Queue. It covers their unique insertion, deletion, and prioritization methods, along with real-world applications in systems like task scheduling and data processing.
In computer science, Queue, Deque, and Priority Queue are Abstract Data Types (ADTs) used to organize and process data. The three structures have functionalities in common but differ in how they manage the order of insertion, deletion, and prioritization of elements. These ADTs are widely used in computer science for applications like operating systems, task scheduling systems, and data entry applications.
Queue (FIFO — First In, First Out)
Queue stands for ‘waiting in line’ as people wait line in at an airport check-in gate (Minh, 2019). The queue is a linear data structure that follows the First In, First Out (FIFO) principle — first come, first served -, where the first element inserted (in) is the first one to be removed (out). This approach is useful for applications where tasks or data need to be processed in the same order they arrive.
A use case is in tasks shouldering applications, such as processing print jobs, the print driver processes each print job in the order they were submitted, the first job submitted is printed first, and so on.
Usually, a Queue ADT provides three main operations, see the table below:
Table 1
Queue ADT Operations
In computer science, Queue, Deque, and Priority Queue are Abstract Data Types (ADTs) used to organize and process data. The three structures have functionalities in common but differ in how they manage the order of insertion, deletion, and prioritization of elements. These ADTs are widely used in computer science for applications like operating systems, task scheduling systems, and data entry applications.
Queue (FIFO — First In, First Out)
Queue stands for ‘waiting in line’ as people wait line in at an airport check-in gate (Minh, 2019). The queue is a linear data structure that follows the First In, First Out (FIFO) principle — first come, first served -, where the first element inserted (in) is the first one to be removed (out). This approach is useful for applications where tasks or data need to be processed in the same order they arrive.
A use case is in tasks shouldering applications, such as processing print jobs, the print driver processes each print job in the order they were submitted, the first job submitted is printed first, and so on.
Usually, a Queue ADT provides three main operations, see the table below:
Table 1
Queue ADT Operations
Note: From “Java queue collection tutorial and examples. Code Java: Coding Your Pasion” by Minh (2019, p.4)
- Insert: adds an element at the end of the queue (tail).
- Remove: removes the element at the beginning of the queue (head).
- Examine: does not remove an element but returns the element at the head of the queue, if no element is at the head of the queue it returns ‘null’.
Below is a simple implementation of a Queue ADT in Java using a linked list
public class MyQueue {
// Inner class Node that holds the data and reference to the next node
private class Node {
T data;
Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
private Node front;
private Node rear;
private int size;
// Constructor
public MyQueue() {
this.front = null;
this.rear = null;
this.size = 0;
}
// add an element to the queue (enqueue operation)
public void enqueue(T data) {
Node newNode = new Node<>(data);
if (rear == null) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
System.out.println(data + " added to the queue.");
}
// remove an element from the queue (dequeue operation)
public T dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. No elements to remove.");
return null;
}
T removedData = front.data;
front = front.next;
if (front == null) {
rear = null;
}
size--;
System.out.println(removedData + " removed from the queue.");
return removedData;
}
// get the front element of the queue
public T peek() {
if (isEmpty()) {
System.out.println("Queue is empty. No elements to show.");
return null;
}
return front.data;
}
// check if the queue is empty
public boolean isEmpty() {
return size == 0;
}
// get the size of the queue
public int getSize() {
return size;
}
// print the elements of the queue
public void printQueue() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
Node current = front;
System.out.print("Queue: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
MyQueue queue = new MyQueue<>();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.printQueue();
System.out.println("Front element: " + queue.peek());
queue.dequeue();
queue.printQueue();
System.out.println("Is queue empty? " + queue.isEmpty());
System.out.println("Size of the queue: " + queue.getSize());
}
}
Outputs
10 added to the queue.
20 added to the queue.
30 added to the queue.
Queue: 10 20 30
Front element: 10
10 removed from the queue.
Queue: 20 30
Is queue empty? false
Size of the queue: 2
Deque (Double-Ended Queue)
A deque ADT or Double-Ended Queue combines the functionalities of both a queue and a stack. It allows elements to be added or removed from both ends, head and tail combining both a stack (Last In, First Out — LIFO) or a queue (First In, First Out — FIFO). This approach is useful for applications where tasks or data need to be processed either from the front or the back.
A use case is in data entry applications, such as in text editors, where the undo/redo functionality is used to add or remove data from both ends of a deque stores text entries.
Usually, a Deque ADT provides the following main operations:
Table 2
Deque ADT Operations
Note: From “Java queue collection tutorial and examples. Code Java: Coding Your Pasion” by Minh (2019, p.5)
The operations are similar to the queue’s Insert, Remove, and Examine operations, with the difference that they apply to both the head and tail of the deque. In a queue, the Remove and Examine operations apply only to the head, while the Insert operation applies only to the tail of the queue.
Priority Queue
A Priority Queue ADT organizes elements by priority rather than by the elements’ order of entry. In other words, it does not follow either the LIFO or FIFO principles but instead processes elements with the highest priority first or maximum, regardless of when they were added. It also allows arbitrary element insertion. This approach is useful for applications where certain tasks must be handled before others.
A use case is in prioritizing task applications, such as the operating system scheduler applications, where critical system events are prioritized for execution over all other tasks, regardless of their order of arrival.
Queue ADT provides the following main operations:
- insert(priority, element): Insert new element with given priority.
- peekMax(): Return (but don’t remove) the element with the largest priority.
- removeMax(): Return and remove the element with the largest priority.
(Cabbe, n.d.)
To summarize, the primary difference between a Queue, Deque, and Priority Queue is how elements are inserted, deleted, and prioritized:
Queue (FIFO — First In, First Out):
- A Queue allows insertion at the end (tail) and removal from the front (head).
- Use when the order of processing matters and follows a first-come-first-served principle.
Deque (Double-Ended Queue):
- A Deque is a combination of FIFO (queue) and LIFO (stack) allowing elements to be inserted and removed from both ends (head and tail).
- Use when elements need to be added or removed from either end of the structure.
Priority Queue:
- In a Priority Queue, elements are based on priority, not on the order of entry. The highest priority element is always removed first.
- Use when tasks or elements need to be prioritized over others.
Note that the algorithms’ complexity also varies, see the table below.
Table 3
Time and Space Complexities
Note: From “Queue (Data Structure)” by Devopedia (n.d.). Modify.
Queue, Deque, and Priority Queue are essential and widely used ADTs. Each plays a crucial role in managing data efficiently in numerous real-world applications, from task scheduling to data processing and system management. Understanding when and how to use each of these ADTs is essential for creating efficient and functional software solutions.
References:
Cabbe, F. (n.d.). The priority queue. ADT. IC312: Data structures. United States Naval Academy. https://www.usna.edu/Users/cs/crabbe/IC312/current/units/07/unit.html/
Devopedia (n.d.). Queue (data structure). Devopedia. https://devopedia.org/queue-data-structure
Minh, H., N. (2019, June 14). Java queue collection tutorial and examples. Code Java: Coding Your Pasion. CodeJava. https://www.codejava.net/java-core/collections/java-queue-collection-tutorial-and-examples#google_vignette
Originally published at Alex.omegapy - Medium on October 3, 2024.
Top comments (0)