The queue is a linear data structure that follows the FIFO rule (first in first out). We can implement Queue for not only Integers but also Strings, Float, or Characters. There are 5 primary operations in Queue:
- enqueue() adds element x to the front of the queue
- dequeue() removes the last element of the queue
- front() returns the front element
- rear() returns the rear element
- empty() returns whether the queue is empty or not
Note: Time complexity is of order 1 for all operations
Implementation:
Example
Java
// Java Program to Implement Queue using Array and GenericsÂ
// Importing input output classesimport java.io.*;// Importing all utility classesimport java.util.*;Â
// Class 1// Helper Class(user defined - generic queue class)class queue<T> {    // front and rear variables are initially initiated to    // -1 pointing to no element that control queue    int front = -1, rear = -1;Â
    // Creating an object of ArrayList class of T type    ArrayList<T> A = new ArrayList<>();Â
    // Method 1    // Returns value of element at front    T front()    {        // If it is not pointing to any element in queue        if (front == -1)Â
            return null;Â
        // else return the front element        return A.get(front);    }    // Method 2    // Returns value of element at rear    T rear()    {        // If it is not pointing to any element in queue        if (rear == -1)            return null;        return A.get(rear);    }    // Method 3    // Inserts element at the front of queue    void enqueue(T X)    {        // If queue is empty        if (this.empty()) {            front = 0;            rear = 0;            A.add(X);        }Â
        // If queue is not empty        else {            front++;            if (A.size() > front) {Â
                // Mov front pointer to next                A.set(front, X);            }            elseÂ
                // Add element to the queue                A.add(X);        }    }    // Method 4    // Deletes elements from the rear from queue    void dequeue()    {        // if queue doesn't have any elements        if (this.empty())Â
            // Display message when queue is already empty            System.out.println("Queue is already empty");Â
        // If queue has only one element        else if (front == rear) {Â
            // Both are pointing to same element            front = rear = -1;        }Â
        // If queue has more than one element        else {Â
            // Increment the rear            rear++;        }    }Â
    // Method 5    // Checks whether the queue is empty    boolean empty()    {        // Both are initialized to same value        // as assigned at declaration means no queue made        if (front == -1 && rear == -1)            return true;        return false;    }    // Method 6    // Print the queueÂ
    // @Override    public String toString()    {        if (this.empty())            return "";Â
        String Ans = "";Â
        for (int i = rear; i < front; i++) {            Ans += String.valueOf(A.get(i)) + "->";        }Â
        Ans += String.valueOf(A.get(front));Â
        return Ans;    }}Â
// Class 2// Main classclass GFG {Â
    // Main driver method    public static void main(String args[])    {        // Case 1 : Integer QueueÂ
        // Creating object of queue Class (user defined)        // Declaring object of integer type        queue<Integer> q1 = new queue<>();Â
        // Pushing elements to the integer object created        // Custom input integer entries        q1.enqueue(5);        q1.enqueue(10);        q1.enqueue(20);Â
        // Print the queue after inserting integer elements        System.out.println(            "q1 after enqueue of 3 elements:\n" + q1);        q1.dequeue();        System.out.println("q1 after dequeue :\n" + q1);Â
        // Case 2 : String QueueÂ
        // Creating object of queue Class (user defined)        // Declaring object of string type        queue<String> q2 = new queue<>();Â
        // Pushing elements to the String object created        // Custom input string entries        q2.enqueue("hello");        q2.enqueue("world");        q2.enqueue("GFG");Â
        // Print the queue after inserting string elements        System.out.println(            "\nq2 after enqueue of 3 elements:\n" + q2);Â
        // Printing front and rear of the above queue        System.out.println("q2 front = " + q2.front()                           + ", q2 rear = " + q2.rear());Â
        // Case 3 : Float QueueÂ
        // Creating object of queue Class (user defined)        // Declaring object of float type        queue<Float> q3 = new queue<>();Â
        // Display message only        System.out.println(            "\nCreated new Float type queue q3...");Â
        // Display whether queue is empty or not        // using the empty() method        System.out.println(            "Checking if queue is empty or not :\n"            + q3.empty());    }} |
Output
q1 after enqueue of 3 elements: 5->10->20 q1 after dequeue : 10->20 q2 after enqueue of 3 elements: hello->world->GFG q2 front = GFG, q2 rear = hello Created new Float type queue q3... Checking if queue is empty or not : true
Time Complexity: O(n) for traversing and rest O(1) for rest other operations
Auxiliary Space: O(1)
