Introduction and Array Implementation of Queue

Try it on GfG Practice

Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. 
The difference between stack and queue is in removing an element. In a stack we remove the item that is most recently added while in a queue, we remove the item that is least recently added.

Queue Data structure

Basic Operations on Queue: 

• enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
• dequeue(): This operation removes and returns an element that is at the front end of the queue.
• front(): This operation returns the element at the front end without removing it.
• rear(): This operation returns the element at the rear end without removing it.
• isEmpty(): This operation indicates whether the queue is empty or not.
• isFull(): This operation indicates whether the queue is full or not.
• size(): This operation returns the size of the queue i.e. the total number of elements it contains.  

Array implementation Of Queue:

For implementing the queue, we only need to keep track of two variables: front and size. The front points to the first element in the queue, and size keeps track of the number of elements. When we enqueue an item, we insert it at the position front + size and then increment the size. For dequeuing, we check if the queue is empty and remove the item at the front. After removal, we shift all remaining elements to the left by one position. We then decrease the size to reflect the removal.

Steps for enqueue:

• Check the queue is full or not
• If full, print “Queue is full” and exit.
• If the queue is not full
  1. Add the new element at the index front + size (this is the rear of the queue).
  2. Increment the size of the queue by 1 (i.e., size++).

Steps for dequeue:

• Check queue is empty or not
• If empty, print “Queue is empty” and exit
• If the queue is not empty:
  1. Print and return the front element (which is queue[front]).
  2. Shift all elements in the queue to the left by one position (i.e., move each element queue[i] to queue[i - 1] for i from 1 to size - 1).
  3. Decrement the size by 1 (i.e., size--).

// CPP program for array implementation of queue
#include <iostream>
using namespace std;

class Queue {
private:
  
    // Array to hold elements
    int* queue;   
  
    // Index of the front element
    int front;    
  
    // Current size of the queue
    int size;    
  
    // Maximum capacity of the queue
    int capacity; 

public:
    // Constructor to initialize the queue
    Queue(int c) {
        queue = new int[c];
        front = 0;
        size = 0;
        capacity = c;
    }

    // Destructor to free the allocated memory
    ~Queue() {
        delete[] queue;
    }

    // Function to insert an element at the rear of the queue
    void enqueue(int data) {
        if (size == capacity) {
            cout << "Queue is full" << endl;
            return;
        }
        // Add the element to the rear
        queue[front + size] = data;
        size++;
    }

    // Function to delete an element from the front of the queue
    void dequeue() {
        if (size == 0) {
            cout << "Queue is empty" << endl;
            return;
        }

        // Shift all elements to the left by one position
        for (int i = 1; i < size; i++) {
            queue[i - 1] = queue[i];
        }
        size--;
    }

    // Function to display the elements of the queue
    void display() {
        if (size == 0) {
            cout << "Queue is empty" << endl;
            return;
        }

        for (int i = 0; i < size; i++) {
            cout << queue[i] << " <- ";
        }
        cout << endl;
    }

    // Function to get the front element of the queue
    void getFront() {
        if (size == 0) {
            cout << "Queue is empty" << endl;
        } else {
            cout << "Front Element is: " << queue[front] << endl;
        }
    }
};

int main() {
    // Create a queue with capacity 4
    Queue q(4);
  
    // Display the empty queue
    q.display();

    // Insert elements
    q.enqueue(20); 
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50);

    q.display(); 

    q.enqueue(60); 

    q.display(); 
  
    // Delete elements
    q.dequeue(); 
    q.dequeue();
    cout << "After two node deletions:" << endl;

    q.display();
  
    // Get the front element
    q.getFront(); 

    return 0;
}

// Java program for array implementation of queue
import java.util.Arrays;

class Queue {
    // Array to hold elements
    private int[] queue; 
  
    // Index of the front element
    private int front;   
  
    // Current number of elements in the queue
    private int size;   
  
    // Maximum capacity of the queue
    private int capacity;

    // Constructor to initialize the queue
    public Queue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.size = 0;
    }

    // Method to add an element to the queue
    public void enqueue(int data) {
        if (size == capacity) {
            System.out.println("Queue is full");
            return;
        }

        // Add element at the next available position
        queue[front + size] = data;
        size++;
    }

    // Method to remove an element from the front
    public void dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty");
            return;
        }

        // Shift all elements to the left by one position
        for (int i = 1; i < size; i++) {
            queue[i - 1] = queue[i];
        }

        // Reduce the size
        size--;
    }

    // Method to display the queue elements
    public void display() {
        if (size == 0) {
            System.out.println("Queue is empty");
            return;
        }

        // Print all elements
        for (int i = 0; i < size; i++) {
            System.out.print(queue[i] + " <- ");
        }
        System.out.println();
    }

    // Method to print the front element of the queue
    public void getFront() {
        if (size == 0) {
            System.out.println("Queue is empty");
        } else {
            System.out.println("Front Element is: " + queue[front]);
        }
    }
}

class GfG {
    public static void main(String[] args) {
        // Create a queue with capacity 4
        Queue q = new Queue(4); 
      
        // Display the empty queue
        q.display(); 
      
        // Insert elements
        q.enqueue(20); 
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);

        q.display();

        q.enqueue(60);

        q.display();
      
        // Delete elements
        q.dequeue(); 
        q.dequeue();
        System.out.println("After two node deletions:");

        q.display();
      
        // Get the front element
        q.getFront();
    }
}

# Python3 program for array implementation of queue
class Queue:
    def __init__(self, capacity):
      
        # Array to hold elements
        self.queue = [None] * capacity
        
        # Index of the front element
        self.front = 0
        
        # Current size of the queue
        self.size = 0
        
        # Maximum capacity of the queue
        self.capacity = capacity

    def enqueue(self, data):
        # Check if the queue is full
        if self.size == self.capacity:
            print("Queue is full")
            return

        # Add the element at the next available position
        self.queue[self.front + self.size] = data
        self.size += 1

    def dequeue(self):
        # Check if the queue is empty
        if self.size == 0:
            print("Queue is empty")
            return

        # Shift all elements to the left by one position
        for i in range(1, self.size):
            self.queue[i - 1] = self.queue[i]

        # Reduce the size of the queue
        self.size -= 1

    def display(self):
        # Check if the queue is empty
        if self.size == 0:
            print("Queue is empty")
            return

        # Print all elements in the queue
        for i in range(self.size):
            print(self.queue[i], end=" <- ")
        print()

    def getFront(self):
        # Check if the queue is empty
        if self.size == 0:
            print("Queue is empty")
        else:
            print(f"Front Element is: {self.queue[self.front]}")
            
if __name__ == '__main__':
  # Create a queue with capacity 4
  q = Queue(4)  
  
  # Display the empty queue
  q.display()  
  
  # Insert elements
  q.enqueue(20)  
  q.enqueue(30)
  q.enqueue(40)
  q.enqueue(50)

  q.display() 

  q.enqueue(60) 

  q.display()  

  # Delete elements
  q.dequeue() 
  q.dequeue()
  print("After two node deletions:")

  q.display()
  
  # Get the front element
  q.getFront()  

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

class Queue {
    // Array to hold elements
    private int[] queue;

    // Index of the front element
    private int front;

    // Current size of the queue
    private int size;

    // Maximum capacity of the queue
    private int capacity;

    // Constructor to initialize the queue
    public Queue(int c) {
        queue = new int[c];
        front = 0;
        size = 0;
        capacity = c;
    }

    // Function to insert an element at the rear of the
    // queue
    public void Enqueue(int data) {
        if (size == capacity) {
            Console.WriteLine("Queue is full");
            return;
        }
        // Add the element to the rear
        queue[front + size] = data;
        size++;
    }

    // Function to delete an element from the front of the
    // queue
    public void Dequeue() {
        if (size == 0) {
            Console.WriteLine("Queue is empty");
            return;
        }

        // Shift all elements to the left by one position
        for (int i = 1; i < size; i++) {
            queue[i - 1] = queue[i];
        }
        size--;
    }

    // Function to display the elements of the queue
    public void Display() {
        if (size == 0) {
            Console.WriteLine("Queue is empty");
            return;
        }

        for (int i = 0; i < size; i++) {
            Console.Write(queue[i] + " <- ");
        }
        Console.WriteLine();
    }

    // Function to get the front element of the queue
    public void getFront() {
        if (size == 0) {
            Console.WriteLine("Queue is empty");
        }
        else {
            Console.WriteLine("Front Element is: "
                              + queue[front]);
        }
    }
}
class GfG {
    static void Main() {
        // Create a queue with capacity 4
        Queue q = new Queue(4);

        // Display the empty queue
        q.Display();

        // Insert elements
        q.Enqueue(20);
        q.Enqueue(30);
        q.Enqueue(40);
        q.Enqueue(50);

        q.Display();

        q.Enqueue(60);
        q.Display();

        // Delete elements
        q.Dequeue();
        q.Dequeue();
        Console.WriteLine("After two node deletions:");

        q.Display();

        // Get the front element
        q.getFront();
    }
}

// Javascript program for array implementation of queue
class Queue {
    constructor(c) {
        // Array to hold elements
        this.queue = new Array(c);  
        
        // Index of the front element
        this.front = 0;  
        
        // Current size of the queue
        this.size = 0;              
        
        // Maximum capacity of the queue
        this.capacity = c;        
    }

    // Function to insert an element at the rear of the queue
    enqueue(data) {
        if (this.size === this.capacity) {
            console.log("Queue is full");
            return;
        }
        // Add the element to the rear
        this.queue[this.front + this.size] = data;  
        this.size++;
    }

    // Function to delete an element from the front of the queue
    dequeue() {
        if (this.size === 0) {
            console.log("Queue is empty");
            return;
        }

        // Shift all elements to the left by one position
        for (let i = 1; i < this.size; i++) {
            this.queue[i - 1] = this.queue[i];
        }
        this.size--;
    }

    // Function to display the elements of the queue
    display() {
        if (this.size === 0) {
            console.log("Queue is empty");
            return;
        }

        for (let i = 0; i < this.size; i++) {
            process.stdout.write(this.queue[i] + " <- ");
        }
        console.log();
    }

    // Function to get the front element of the queue
    getFront() {
        if (this.size === 0) {
            console.log("Queue is empty");
        } else {
            console.log("Front Element is: " + this.queue[this.front]);
        }
    }
}

// Driver Code
// Create a queue with capacity 4
const q = new Queue(4);  

// Display the empty queue
q.display(); 

// Insert elements
q.enqueue(20);  
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);

q.display();  

q.enqueue(60);  

q.display();  

// Delete elements
q.dequeue();  
q.dequeue();
console.log("After two node deletions:");

q.display(); 

// Get the front element
q.getFront();  

Queue is empty
20 <- 30 <- 40 <- 50 <- 
Queue is full
20 <- 30 <- 40 <- 50 <- 
After two node deletions:
40 <- 50 <- 
Front Element is: 40

Complexity Analysis:  

• Time Complexity

• Auxiliary Space: 
  O(n) where n is the size of the array for storing elements.

Advantages of Array Implementation:  

• Easy to implement.
• A large amount of data can be managed efficiently with ease.
• Operations such as insertion and deletion can be performed with ease as it follows the first in first out rule.

Disadvantages of Array Implementation:  

• Static Data Structure, fixed size.
• If the queue has a large number of enqueue and dequeue operations, at some point (in case of linear increment of front and rear indexes) we may not be able to insert elements in the queue even if the queue is empty (this problem is avoided by using circular queue).
• Maximum size of a queue must be defined prior.

kartik

Follow

Improve