Koding Books

Professional, free coding tutorials

Queues

Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It is an ordered list of elements where the insertion of new elements happens at one end, called the rear, and the removal of existing elements occurs at the other end, called the front.

Queues are commonly used in computer science for various applications such as process scheduling, task management, and network packet handling. They are also used in real-life scenarios, such as waiting in line at a ticket counter or a fast-food restaurant.

In this article, we will explore the basic operations of a queue, its implementation, and some common use cases.

Operations

The basic operations of a queue are:

  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes the element from the front of the queue.
  • Peek/Front: Returns the element at the front of the queue without removing it.
  • IsEmpty: Returns true if the queue is empty, false otherwise.
  • IsFull: Returns true if the queue is full, false otherwise (in some implementations).

These operations allow us to manipulate the elements in the queue according to the FIFO principle.

Advantages

The advantages of using a queue data structure over other data structures are:

  • FIFO Principle: Queues follow the First In, First Out (FIFO) principle, meaning that the element inserted first is the first to be removed. This makes queues ideal for scenarios where the order of elements is important, such as process scheduling or network packet handling.
  • Efficient Insertion and Removal: Queues have efficient insertion and removal operations. Adding an element to the rear of the queue takes O(1) time, and removing an element from the front of the queue also takes O(1) time. This makes queues a good choice for scenarios where elements must be added and removed frequently.
  • Easy to Implement: Queues are easy to implement and understand. They can be implemented using a simple list or array, and their basic operations are straightforward.
  • Versatile: Queues can be used in various applications, such as process scheduling, task management, network packet handling, etc. They are versatile data structures that can be adapted to many different scenarios.

Queues are a simple and efficient data structure that can be used in various applications. Their FIFO principle and efficient insertion and removal operations make them a good choice for scenarios where the order of elements is important, and elements need to be added and removed frequently.

Use Case

Queues are commonly used in computer science for various applications such as:

  • Process Scheduling: In operating systems, processes are queued up to be executed by the CPU. The process that arrives first is executed first, and so on.
  • Task Management: In multi-tasking systems, tasks are queued up to be executed by the processor. The task that arrives first is executed first, and so on.
  • Network Packet Handling: In computer networks, packets are queued up to be transmitted over the network. The packet that arrives first is transmitted first, and so on.
  • Breadth-First Search: In graph theory, breadth-first search (BFS) uses a queue to traverse a graph level by level.
  • Printer Spooling: In computer systems, print jobs are queued up to be printed by the printer. The job that arrives first is printed first, and so on.
  • Call Center Management: In call centres, customer calls are queued up to be answered by the next available agent. The call that arrives first is answered first, and so on.

These are just a few examples of the many use cases of queues in computer science.

Implementation

Python

# tests
def test_enqueue():
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    assert len(q) == 3

def test_dequeue():
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    assert q.dequeue() == 1
    assert q.dequeue() == 2
    assert q.dequeue() == 3
    assert q.dequeue() is None

def test_peek():
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    assert q.peek() == 1
    q.dequeue()
    assert q.peek() == 2

def test_is_empty():
    q = Queue()
    assert q.is_empty() is True
    q.enqueue(1)
    assert q.is_empty() is False
    q.dequeue()
    assert q.is_empty() is True

# implementation

import numpy as np

class Queue:
    def __init__(self):
        self.items = np.array([])

    def enqueue(self, item):
        self.items = np.append(self.items, item)

    def dequeue(self):
        if not self.is_empty():
            item = self.items[0]
            self.items = np.delete(self.items, 0)
            return item

    def peek(self):
        if not self.is_empty():
            return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def __len__(self):
        return len(self.items)

C++

#include <gtest/gtest.h>
#include "queue.h"

TEST(QueueTest, EnqueueTest) {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    EXPECT_EQ(q.peek(), 1);
}

TEST(QueueTest, DequeueTest) {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    EXPECT_EQ(q.dequeue(), 1);
    EXPECT_EQ(q.dequeue(), 2);
    EXPECT_EQ(q.dequeue(), 3);
    EXPECT_EQ(q.dequeue(), -1);
}

TEST(QueueTest, PeekTest) {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    EXPECT_EQ(q.peek(), 1);
    q.dequeue();
    EXPECT_EQ(q.peek(), 2);
}

TEST(QueueTest, IsEmptyTest) {
    Queue q;
    EXPECT_TRUE(q.is_empty());
    q.enqueue(1);
    EXPECT_FALSE(q.is_empty());
    q.dequeue();
    EXPECT_TRUE(q.is_empty());
}

int main(int argc, char **argv) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

# implementation

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class Queue {
private:
    Node* front;
    Node* rear;
public:
    Queue() {
        front = NULL;
        rear = NULL;
    }

    void enqueue(int item) {
        Node* newNode = new Node();
        newNode->data = item;
        newNode->next = NULL;
        if (rear == NULL) {
            front = newNode;
            rear = newNode;
        }
        else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    int dequeue() {
        if (front == NULL) {
            return -1;
        }
        else {
            int item = front->data;
            Node* temp = front;
            front = front->next;
            if (front == NULL) {
                rear = NULL;
            }
            delete temp;
            return item;
        }
    }

    int peek() {
        if (front == NULL) {
            return -1;
        }
        else {
            return front->data;
        }
    }

    bool is_empty() {
        return front == NULL;
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    cout << q.dequeue() << endl; // Output: 1
    cout << q.peek() << endl; // Output: 2
    cout << q.is_empty() << endl; // Output: 0 (false)
    return 0;
}

The last byte…

Queues are a fundamental data structure in computer science that follows the First In, First Out (FIFO) principle. They are an ordered list of elements where the insertion of new elements happens at one end, called the rear, and the removal of existing elements occurs at the other end, called the front. Queues are commonly used in computer science for various applications such as process scheduling, task management, and network packet handling.

In this article, we explored the basic operations of a queue, its implementation in Python and C++, and some common use cases. We discussed how queues have efficient insertion and removal operations and how they are easy to implement and understand. We also looked at some advantages of using a queue data structure over other data structures, such as their versatility and adherence to the FIFO principle.

We provided examples of queue implementations in Python and C++ and showed how to write unit tests for the Queue class using the pytest and Google Test frameworks. We also discussed the efficiency of different queue implementations and how to choose the best implementation for your specific use case.

Queues are a simple and efficient data structure that can be used in various applications. Whether you’re working on process scheduling, task management, network packet handling, or any other scenario where the order of elements is important, queues are a powerful tool in your programming arsenal.

Ali Kayani

https://www.linkedin.com/in/ali-kayani-silvercoder007/

Post navigation

Leave a Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

On Balance Volume stock indicator

Dual Thrust Trading Algorithm

CMAKE – A practical introduction

White hat hacking using Python