Implementation of Queue Data Structure

Complexity Analysis of Operations on Queue Data Structure:

Queue can be implemented using following data structures:

We have discussed the implementation of Queue below:

C++

// Implementation of queue(enqueue, dequeue).
#include <bits/stdc++.h>
using namespace std;

class Queue {
public:
    int front, rear, size;
    unsigned cap;
    int* arr;
};

Queue* createQueue(unsigned cap)
{
    Queue* queue = new Queue();
    queue->cap = cap;
    queue->front = queue->size = 0;

    queue->rear = cap - 1;
    queue->arr = new int[(queue->cap * sizeof(int))];
    return queue;
}

int isFull(Queue* queue)
{
    return (queue->size == queue->cap);
}

int isempty(Queue* queue) { return (queue->size == 0); }
// Function to add an item to the queue.
// It changes rear and size.
void enqueue(Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->cap;
    queue->arr[queue->rear] = item;
    queue->size = queue->size + 1;
    cout << item << " enqueued to queue\n";
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    int item = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->cap;
    queue->size = queue->size - 1;
    return item;
}
int front(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    return queue->arr[queue->front];
}
int rear(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    return queue->arr[queue->rear];
}

// Driver code
int main()
{
    Queue* queue = createQueue(1000);
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    cout << dequeue(queue);
    cout << " dequeued from queue\n";
    cout << "Front item is " << front(queue) << endl;
    cout << "Rear item is " << rear(queue);
    return 0;
}

// C program for array implementation of queue
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a queue
struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

// function to create a queue
// of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
    struct Queue* queue
        = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;

    // This is important, see the enqueue
    queue->rear = capacity - 1;
    queue->array
        = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

// Queue is full when size becomes
// equal to the capacity
int isFull(struct Queue* queue)
{
    return (queue->size == queue->capacity);
}

// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{
    return (queue->size == 0);
}

// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}

// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function to get front of queue
int front(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}

// Function to get rear of queue
int rear(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}

// Driver program to test above functions./
int main()
{
    struct Queue* queue = createQueue(1000);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printf("%d dequeued from queue\n", dequeue(queue));
    printf("Front item is %d\n", front(queue));
    printf("Rear item is %d\n", rear(queue));

    return 0;
}
// This code is contributed by Susobhan Akhuli

Java

// Java program for array
// implementation of queue

// A class to represent a queue
class Queue {
    int front, rear, size;
    int capacity;
    int array[];

    public Queue(int capacity)
    {
        this.capacity = capacity;
        front = this.size = 0;
        rear = capacity - 1;
        array = new int[this.capacity];
    }

    // Queue is full when size becomes
    // equal to the capacity
    boolean isFull(Queue queue)
    {
        return (queue.size == queue.capacity);
    }

    // Queue is empty when size is 0
    boolean isEmpty(Queue queue)
    {
        return (queue.size == 0);
    }

    // Method to add an item to the queue.
    // It changes rear and size
    void enqueue(int item)
    {
        if (isFull(this))
            return;
        this.rear = (this.rear + 1) % this.capacity;
        this.array[this.rear] = item;
        this.size = this.size + 1;
        System.out.println(item + " enqueued to queue");
    }

    // Method to remove an item from queue.
    // It changes front and size
    int dequeue()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        int item = this.array[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size = this.size - 1;
        return item;
    }

    // Method to get front of queue
    int front()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        return this.array[this.front];
    }

    // Method to get rear of queue
    int rear()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        return this.array[this.rear];
    }
}

// Driver class
public class Test {
    public static void main(String[] args)
    {
        Queue queue = new Queue(1000);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println(queue.dequeue()
                           + " dequeued from queue");

        System.out.println("Front item is "
                           + queue.front());

        System.out.println("Rear item is " + queue.rear());
    }
}

// This code is contributed by Susobhan Akhuli

Python

# Python3 program for array implementation of queue

# Class Queue to represent a queue


class Queue:

    # __init__ function
    def __init__(self, capacity):
        self.front = self.size = 0
        self.rear = capacity - 1
        self.Q = [None]*capacity
        self.capacity = capacity

    # Queue is full when size becomes
    # equal to the capacity
    def isFull(self):
        return self.size == self.capacity

    # Queue is empty when size is 0
    def isEmpty(self):
        return self.size == 0

    # Function to add an item to the queue.
    # It changes rear and size
    def EnQueue(self, item):
        if self.isFull():
            print("Full")
            return
        self.rear = (self.rear + 1) % (self.capacity)
        self.Q[self.rear] = item
        self.size = self.size + 1
        print("% s enqueued to queue" % str(item))

    # Function to remove an item from queue.
    # It changes front and size
    def DeQueue(self):
        if self.isEmpty():
            print("Empty")
            return

        print("% s dequeued from queue" % str(self.Q[self.front]))
        self.front = (self.front + 1) % (self.capacity)
        self.size = self.size - 1

    # Function to get front of queue
    def que_front(self):
        if self.isEmpty():
            print("Queue is empty")

        print("Front item is", self.Q[self.front])

    # Function to get rear of queue
    def que_rear(self):
        if self.isEmpty():
            print("Queue is empty")
        print("Rear item is",  self.Q[self.rear])


# Driver Code
if __name__ == '__main__':

    queue = Queue(30)
    queue.EnQueue(10)
    queue.EnQueue(20)
    queue.EnQueue(30)
    queue.EnQueue(40)
    queue.DeQueue()
    queue.que_front()
    queue.que_rear()
# This code is contributed by Susobhan Akhuli

// C# program for array implementation of queue
using System;

namespace w3wiki {
// A class to represent a linearqueue
class Queue {
    private int[] ele;
    private int front;
    private int rear;
    private int max;

    public Queue(int size)
    {
        ele = new int[size];
        front = 0;
        rear = -1;
        max = size;
    }

    // Function to add an item to the queue.
    // It changes rear and size
    public void enqueue(int item)
    {
        if (rear == max - 1) {
            Console.WriteLine("Queue Overflow");
            return;
        }
        else {
            ele[++rear] = item;
        }
    }

    // Function to remove an item from queue.
    // It changes front and size
    public int dequeue()
    {
        if (front == rear + 1) {
            Console.WriteLine("Queue is Empty");
            return -1;
        }
        else {
            Console.WriteLine(ele[front]
                              + " dequeued from queue");
            int p = ele[front++];
            Console.WriteLine("Front item is {0}",
                              ele[front]);
            Console.WriteLine("Rear item is {0} ",
                              ele[rear]);
            return p;
        }
    }

    // Function to print queue.
    public void printQueue()
    {
        if (front == rear + 1) {
            Console.WriteLine("Queue is Empty");
            return;
        }
        else {
            for (int i = front; i <= rear; i++) {
                Console.WriteLine(ele[i]
                                  + " enqueued to queue");
            }
        }
    }
}

// Driver code
class Program {
    static void Main()
    {
        Queue Q = new Queue(5);

        Q.enqueue(10);
        Q.enqueue(20);
        Q.enqueue(30);
        Q.enqueue(40);
        Q.printQueue();
        Q.dequeue();
    }
}
}
// This code is contributed by Susobhan Akhuli

Javascript

<script>
// Queue class
class Queue
{
    // Array is used to implement a Queue
    constructor()
    {
        this.items = [];
    }
    isEmpty()
    {
        // return true if the queue is empty.
        return this.items.length == 0;
    }
    enqueue(element)
    {    
        // adding element to the queue
        this.items.push(element);
        document.write(element + " enqueued to queue<br>");
    }
    dequeue()
    {
        // removing element from the queue
        // returns underflow when called 
        // on empty queue
        if(this.isEmpty())
            return "Underflow<br>";
        return this.items.shift();
    }
    front()
    {
        // returns the Front element of 
        // the queue without removing it.
        if(this.isEmpty())
            return "No elements in Queue<br>";
        return this.items[0];
    }
    rear()
    {
        // returns the Rear element of 
        // the queue without removing it.
        if(this.isEmpty())
            return "No elements in Queue<br>";
        return this.items[this.items.length-1];
    }
}

// creating object for queue class
var queue = new Queue();

// Adding elements to the queue
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);

// queue contains [10, 20, 30, 40]
// removes 10
document.write(queue.dequeue() + " dequeued from queue<br>");

// queue contains [20, 30, 40]
// Front is now 20
document.write("Front item is " + queue.front() + "<br>");

// printing the rear element
// Rear is 40
document.write("Rear item is " + queue.rear() + "<br>");

// This code is contributed by Susobhan Akhuli
</script>

Output

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40

Introduction to Queue Data Structure

Queue Data Structure is a linear data structure that follows FIFO (First In First Out) Principle, so the first element inserted is the first to be popped out. In this article, we will cover all the basics of Queue, Operations on Queue, its implementation, advantages, disadvantages which will help you solve all the problems based on Queue.

Table of Content

What is Queue Data Structure?
Representation of Queue Data Structure:
Types of Queue Data Structure
Basic Operations in Queue Data Structure
1. Enqueue Operation in Queue Data Structure
2. Dequeue Operation in Queue Data Structure
3. Front Operation in Queue Data Structure
4. Rear Operation in Queue Data Structure
5. isEmpty Operation in Queue Data Structure
6. isFull Operation in Queue Structure
Implementation of Queue Data Structure
Complexity Analysis of Operations on Queue Data Structure
Applications of Queue Data Structure
Advantages of Queue Data Structure
Disadvantages of Queue Data Structure
FAQs (Frequently asked questions) on Queue Data Structure

Implementation of Queue Data Structure

Introduction to Queue Data Structure

Similar Reads

Contact Us