Introduction to Queue Data Structure with Practical Examples

• Queue Data Structure
• Operations in Queue
  • 1. Enqueue Operation
  • 2. Dequeue Operation
  • 3. Peek (or Front) Operation
  • 4. Size Operation
  • 5. Search Operation
• Implementation of Queue Using Array and Struct in C
• Implementation of Queue Using Array and Class in C++
• Queue in C++ STL
  • Functions in STL Queue
  • Example with the STL Queue Functions
• Types of Queues
  • 1. Simple Queue
  • 2. Circular Queue
  • 3. Priority Queue
  • 4. Double-ended Queue (Deque)
• Applications of Queue
• Run C Programming Online Compiler
• Tags

A queue data structure works like a toll booth on a single lane, one-way road. It’s like a line of cars waiting to pay. The first car that arrived is the first one to be served and leave. As new cars come, they join the back of the line and wait their turn to be served at the toll booth. It’s a first come, first served system.

¶Queue Data Structure

A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle. The element that enters the queue first is the first to be removed and the element enters last is the last to be removed.

Queues are flexible and have uses in different areas of computer science. They play a crucial role in tasks like managing tasks in a computer program, handling requests in networks, and organizing data efficiently. Queues help ensure that processes are carried out in an orderly and organized manner.

¶Operations in Queue

A queue provides a set of useful operations for manipulating its data. These operations include:

¶1. Enqueue Operation

Enqueueing is the process of adding an element to the back of the queue. It’s like a new car joining the line at the end. This operation ensures that the element becomes the last in line to be served, following the FIFO (First-In-First-Out) principle.
Complexity: O(1) - Constant time complexity, as adding an element to the back can be done in constant time.

¶2. Dequeue Operation

Dequeueing is the removal of the front element from the queue. Similar to a car at the front of the line completing their service and leaving, this operation ensures that the oldest element is served and removed, maintaining the order of arrival.
Complexity: O(1) - Constant time complexity, as removing the front element is a quick operation.

¶3. Peek (or Front) Operation

The peek operation allows you to view the front element of the queue without removing it. It’s like checking which car is at the front of the line without them leaving. This operation is useful for inspecting the next element to be served.
Complexity: O(1) - Constant time complexity, as viewing the front element does not involve any modification of the queue.

¶4. Size Operation

The Size operation returns the current number of elements in the queue. It helps in understanding the overall size of the queue and is useful for monitoring and managing the capacity of the queue dynamically.
Complexity: O(1) - Constant time complexity, as the size of the queue is usually maintained as an attribute and can be retrieved quickly.

¶5. Search Operation

Searching for a specific element in a queue involves dequeuing elements one by one until the desired element is found or the queue becomes empty.
Complexity: O(n) - Linear time complexity, where ‘n’ is the number of elements in the queue. In the worst case, you may need to traverse the entire queue to find the desired

¶Implementation of Queue Using Array and Struct in C

#include <stdio.h>

#define MAX_SIZE 100

struct Queue {
    int arr[MAX_SIZE];
    int front, rear;
};

// Function to initialize the queue
void initQueue(struct Queue* q) {
    q->front = q->rear = -1;
}

// Enqueue Operation
void enqueue(struct Queue* q, int item) {
    if (q->rear == MAX_SIZE - 1) {
        printf("Queue Overflow: Cannot enqueue more elements.\n");
        return;
    }

    if (q->front == -1) {
        q->front = q->rear = 0;
    } else {
        q->rear++;
    }

    q->arr[q->rear] = item;
    printf("%d enqueued to the queue.\n", item);
}

// Dequeue Operation
void dequeue(struct Queue* q) {
    if (q->front == -1) {
        printf("Queue Underflow: Cannot dequeue from an empty queue.\n");
        return;
    }

    int dequeuedItem = q->arr[q->front];

    if (q->front == q->rear) {
        q->front = q->rear = -1; // Reset the queue when the last element is dequeued
    } else {
        q->front++;
    }

    printf("%d dequeued from the queue.\n", dequeuedItem);
}

// Peek (or Front) Operation
void peek(struct Queue* q) {
    if (q->front == -1) {
        printf("Queue is empty.\n");
    } else {
        printf("Front element: %d\n", q->arr[q->front]);
    }
}

// Size Operation
int size(struct Queue* q) {
    if (q->front == -1) {
        return 0;
    }
    return q->rear - q->front + 1;
}

// Search Operation
int search(struct Queue* q, int item) {
    for (int i = q->front; i <= q->rear; i++) {
        if (q->arr[i] == item) {
            printf("%d found in the queue.\n", item);
            return 1;
        }
    }
    printf("%d not found in the queue.\n", item);
    return 0;
}

// Check if the queue is empty
int isEmpty(struct Queue* q) {
    return q->front == -1;
}

int main() {
    struct Queue myQueue;
    initQueue(&myQueue);

    enqueue(&myQueue, 10);
    enqueue(&myQueue, 20);
    enqueue(&myQueue, 30);

    peek(&myQueue);

    dequeue(&myQueue);
    peek(&myQueue);

    printf("Queue Size: %d\n", size(&myQueue));

    search(&myQueue, 20);
    search(&myQueue, 40);

    return 0;
}

¶Implementation of Queue Using Array and Class in C++

#include <iostream>

class Queue {
private:
    static const int MAX_SIZE = 100; // Maximum size of the queue
    int arr[MAX_SIZE];
    int front, rear;

public:
    // Constructor to initialize the queue
    Queue() : front(-1), rear(-1) {}

    // Enqueue Operation
    void enqueue(int item) {
        if (rear == MAX_SIZE - 1) {
            std::cout << "Queue Overflow: Cannot enqueue more elements." << std::endl;
            return;
        }

        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear++;
        }

        arr[rear] = item;
        std::cout << item << " enqueued to the queue." << std::endl;
    }

    // Dequeue Operation
    void dequeue() {
        if (isEmpty()) {
            std::cout << "Queue Underflow: Cannot dequeue from an empty queue." << std::endl;
            return;
        }

        int dequeuedItem = arr[front];

        if (front == rear) {
            front = rear = -1; // Reset the queue when the last element is dequeued
        } else {
            front++;
        }

        std::cout << dequeuedItem << " dequeued from the queue." << std::endl;
    }

    // Peek (or Front) Operation
    void peek() {
        if (isEmpty()) {
            std::cout << "Queue is empty." << std::endl;
        } else {
            std::cout << "Front element: " << arr[front] << std::endl;
        }
    }

    // Size Operation
    int size() {
        if (isEmpty()) {
            return 0;
        }
        return rear - front + 1;
    }

    // Search Operation
    bool search(int item) {
        for (int i = front; i <= rear; i++) {
            if (arr[i] == item) {
                std::cout << item << " found in the queue." << std::endl;
                return true;
            }
        }
        std::cout << item << " not found in the queue." << std::endl;
        return false;
    }

    // Check if the queue is empty
    bool isEmpty() {
        return front == -1;
    }
};

int main() {
    Queue myQueue;

    myQueue.enqueue(10);
    myQueue.enqueue(20);
    myQueue.enqueue(30);

    myQueue.peek();

    myQueue.dequeue();
    myQueue.peek();

    std::cout << "Queue Size: " << myQueue.size() << std::endl;

    myQueue.search(20);
    myQueue.search(40);

    return 0;
}

¶Queue in C++ STL

C++ Standard Template Library (STL) offers a versatile and powerful implementation of the queue data structure, providing with a convenient tool for managing collections in a FIFO manner. They also provides a number of useful function to perform queue operations. To use the C++ STL queue, include the <queue> header and declare a queue object.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue; // Declaration of an integer queue
    // Rest of the code...
    return 0;
}

¶Functions in STL Queue

• empty() Determines whether the queue is empty.
• size() Returns the number of elements in the queue.
• front() Accesses the front element of the queue without removing it.
• back() Accesses the back element of the queue without removing it.
• push() Adds an element to the back of the queue.
• pop() Removes the front element from the queue.

¶Example with the STL Queue Functions

#include <iostream>
#include <queue>

int main() {
    // Declare a queue of integers
    std::queue<int> myQueue;

    // Check if the queue is empty
    if (myQueue.empty()) {
        std::cout << "Queue is empty." << std::endl;
    } else {
        std::cout << "Queue is not empty." << std::endl;
    }

    // Add elements to the queue
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // Display the size of the queue
    std::cout << "Size of the queue: " << myQueue.size() << std::endl;

    // Access and display the front and back elements
    std::cout << "Front element: " << myQueue.front() << std::endl;
    std::cout << "Back element: " << myQueue.back() << std::endl;

    // Remove the front element
    myQueue.pop();

    // Display the size of the modified queue
    std::cout << "Size after popping: " << myQueue.size() << std::endl;

    // Check if the queue is empty after popping
    if (myQueue.empty()) {
        std::cout << "Queue is empty after popping." << std::endl;
    } else {
        std::cout << "Queue is not empty after popping." << std::endl;
    }

    return 0;
}

¶Types of Queues

Queues can be classified into various categories based on how they are implemented and what they are used for. They are primarily classified into the following categories:

¶1. Simple Queue

A basic queue that follows the First-In-First-Out (FIFO) principle. Elements are enqueued at the rear and dequeued from the front, maintaining the order of arrival. It is a straightforward implementation used in various scenarios where the order of processing matters.

¶2. Circular Queue

In a circular queue, the last element is connected to the first, forming a circular structure. This design optimizes space usage by allowing efficient reutilization of empty slots. It finds applications in situations where a fixed-size buffer is desirable, such as in embedded systems.

¶3. Priority Queue

A priority queue assigns priorities to elements, and the element with the highest priority is served first. It is useful in scenarios where tasks or events have varying levels of urgency. Priority queues are employed in scheduling algorithms, simulation systems, and real-time applications.

¶4. Double-ended Queue (Deque)

A deque supports insertion and deletion at both ends, offering greater flexibility compared to a simple queue. Elements can be added or removed from the front or back, making it suitable for a wide range of applications, including algorithms requiring bidirectional processing.

¶Applications of Queue

Queues, with their orderly and efficient First-In-First-Out (FIFO) structure, find diverse applications across various domains. Here are some key applications of queues:

• CPU Scheduling
• Disk Scheduling
• Print Queue Management
• Breadth-First Search (BFS) in Graphs
• Simulation Systems

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

[Run C programming online](https://devsenv.com/page/run-c-programming)

¶Tags

Standard Template Library, C Programming, C Programming Language, C Coding Language, Define Array, C Software Language, C Programming in C, C Programming C, C Program in C, C Programming C Programming, Data Structure, Structure in Data Structure, Data Structure and, A Data Structure, Data Str, Algorithm and Data Structure, Database Structure and Algorithm, Algorithms and Data Structures, Linked List, Priority Queuing, Queue in Python, Linked List Python, Struct in C, Structure in C Programming, C Code Structure, Data Structures, Data Structures and Algorithms, Data Structure, Structure in Data Structure, Structured Data, Python Data Structures, Structured vs Unstructured Data, Structured Data Testing Tool