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)
