You know that feeling, when you get to a good restaurant and surprisingly, there aren't many people.
I bet you would be happy, not needing to wait in line to get some delicious meals.
In programming, we have something similar.
It's called the queue.
Table of Contents
- What is a queue?
- Where is it used?
- What are the types of queues?
- How is it implemented?
- How efficient is it?
- What's next?
- Where can I learn more?
What is a queue?
Let's forget about programming for a second, and let us define the word queue:
A line or sequence of people or vehicles awaiting their turn to be attended to or to proceed.
At its core, a queue is simply a sequence of items waiting to be processed.
Examples include:
- Customers in a pizzeria, waiting for their pizza.
- Line in a movie theater, waiting for the security guys to verify their ticket.
- Vehicles in a gas station, waiting till the person in front of them finishes filling his gas tank.
You get it, there are lots of these examples out there, but coming back to software.
A queue is a linear data structure that follows a particular order in which the operations are performed.
Queues follow the First-In-First-Out methodology, meaning that the first item to be inserted into the queue will be the first item popped out from it. First come, first served.
Isn't this similar to the stack data structure?
Yes, they are similar but the only major difference between the stack and the queue is how they handle their data. The stack uses the Last-In-First-Out methodology while the queue uses the First-In-First-Out methodology.
Where is it used?
The queue is used mostly when you have:
- Items that don't have to be processed immediately.
- Items that have to be processed in the First-In-First-Out order.
- A single resource wanting to be used by many processes.
Let us go over some applications of the queue.
-
Message Queues — A message queue is a general concept in computer science used for communication between processes. A sender sends a message and if the receiver cannot receive it, due to it being busy with some other process or offline. The message gets sent to a queue, where it waits until the receiver is ready to receive the message. The message is removed from the queue and sent to the receiver.
For example, when you send an email, it waits in a queue called the SMTP queue, until the receiver logs into their inbox. Same concept is applied when you send a message to someone who is not online on a social network. Your message waits in some kind of a queue on a server, and when the recipient comes online, it is sent to them.
Process Scheduling — All the processes running on your computer now, first wait in a queue called ready queue, waiting to be executed by your processor. There are various scheduling algorithms that decide which process should be executed next based on certain criteria like priority.
-
Data Buffers — A buffer implements a queue and is typically used in communication when there is a difference between the rate at which data is received and the rate at which it can be processed.
For example in video streaming applications, the video is streamed in bursts and stored in a buffer so that even if the network becomes slow for a while, the playback is not interrupted. Say for example the video is playing at 24fps, then the streaming app may store 240 frames in its buffer so that it can continue playing for the next 10 seconds even if the network is interrupted. The buffer is also used for sequencing frames, ie, if frames come out of order, they are sorted in the buffer before being played. Buffers are also used in disk drives, input/output devices, and communication over networks.
Algorithms — A queue is also used in several algorithms such as the Breadth-First Search algorithm, and round-robin algorithm.
What are the types of queues?
Yes, you heard right, there are multiple types of queues:
- Simple Queue
- Circular Queue
- Priority Queue
- Dequeue (Double Ended Queue)
Simple Queue
Your average queue where insertion takes place in the front and deletion takes place in the rear.
Circular Queue
Also known as the Ring Buffer, it's basically a simple queue but the rear is connected to the front.
Priority Queue
A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.
Dequeue (Double Ended Queue)
It's basically a queue that insertion and deletion can happen in both the front and the rear.
How is it implemented?
Queues can be implemented in different ways, which includes:
- An array with front at index 0.
- An array with floating front and rear (wrap-around array).
- A singly linked list with front.
- A singly linked list with front and rear.
- A doubly linked list.
As you can probably tell, queues can be implemented in many ways, but they all should include the common methods that all queues have:
- Enqueue: Add an element to the end of the queue
- Dequeue: Remove an element from the front of the queue
- IsEmpty: Check if the queue is empty
- IsFull: Check if the queue is full
- Peek: Get the value of the front of the queue without removing it
Let us go over some common implementations of the queue.
PS. We are gonna implement a simple queue.
Java
class Queue
{
private int[] arr; // array to store queue elements
private int front; // front points to the front element in the queue
private int rear; // rear points to the last element in the queue
private int capacity; // maximum capacity of the queue
private int count; // current size of the queue
// Constructor to initialize a queue
Queue(int size)
{
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
// Utility function to dequeue the front element
public void dequeue()
{
// check for queue underflow
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(1);
}
System.out.println("Removing " + arr[front]);
front = (front + 1) % capacity;
count--;
}
// Utility function to add an item to the queue
public void enqueue(int item)
{
// check for queue overflow
if (isFull())
{
System.out.println("Overflow\nProgram Terminated");
System.exit(1);
}
System.out.println("Inserting " + item);
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
// Utility function to return the front element of the queue
public int peek()
{
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(1);
}
return arr[front];
}
// Utility function to return the size of the queue
public int size() {
return count;
}
// Utility function to check if the queue is empty or not
public Boolean isEmpty() {
return (size() == 0);
}
// Utility function to check if the queue is full or not
public Boolean isFull() {
return (size() == capacity);
}
}
Python
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
Javascript
class Queue {
constructor(){
this.data = [];
this.rear = 0;
this.size = 10;
}
enqueue(element) {
if(this.rear < this.size ) {
this.data[this.rear] = element;
this.rear = this.rear + 1;
}
}
size() {
return this.rear;
}
isEmpty() {
return this.rear === 0;
}
peek() {
if(this.isEmpty() === false) {
return this.data[0];
}
}
dequeue() {
if(this.isEmpty() === false) {
this.rear = this.rear-1;
return this.data.shift();
}
}
}
How efficient is it?
Glad you asked my friend, let's go over the time and space complexity of the queue.
- Access - to access an item in a queue, in the worst case we should traverse the whole queue, making it a linear time or O(n) complexity.
- Search - similar to access, we also have to traverse through each item in the queue, making it too linear time or O(n) complexity.
- Insertion (Enqueue) - because insert happens in one place, this makes it constant time or O(1) complexity.
- Deletion (Dequeue) - similar to insertion, it is also constant time or O(1) complexity.
What's next?
Next, we will talk about the union-find data structure.
But for now, I hope you understood what is a queue, and now you have a new weapon in your data structure arsenal.
Where can I learn more?
- https://www.cpp.edu/~ftang/courses/CS240/lectures/queue.htm
- https://adarsh-menon.medium.com/queue-data-structure-practical-applications-operations-43efec72a58d
- https://introcs.cs.princeton.edu/java/43stack/
- https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
- https://www.faceprep.in/data-structures/types-of-queue-data-structure/
- https://www.programiz.com/dsa/queue
- https://www.techiedelight.com/queue-implementation-in-java/
- https://www.bigocheatsheet.com/
- https://cs.stackexchange.com/questions/85851/time-complexity-of-dequeue-function-queues
- https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/
- https://www.programiz.com/dsa/priority-queue
- https://www.programiz.com/dsa/deque
Top comments (0)