A queue is a collection of items whereby its operations work in a FIFO - First In First Out manner. The two primary operations associated with them are enqueue and dequeue.

In real life, we often encounter queues, whether it's waiting in line at a grocery store or in a drive-thru. The principle behind queues is also applicable in computer science and software development.

Java Implementation of a Queue

Let's start with a simple implementation of a queue using Java. In Java, we can use the Queue interface and its implementation class LinkedList to create a queue.

Here's an example of how to create and use a queue in Java:

1import java.util.Queue;
2import java.util.LinkedList;
3
4public class Main {
5  public static void main(String[] args) {
6    // Replace with your Java logic here
7    Queue<String> queue = new LinkedList<>();
8
9    // Enqueue elements
10    queue.add("Apple");
11    queue.add("Banana");
12    queue.add("Orange");
13
14    // Dequeue elements
15    while (!queue.isEmpty()) {
16      String element = queue.poll();
17      System.out.println(element);
18    }
19  }
20}

This code snippet demonstrates how to create a queue using the LinkedList class and perform enqueue and dequeue operations. In this example, the queue stores strings and the elements are added to the queue using the add method. The poll method is used to remove and retrieve elements from the queue in the order they were added.

By understanding the basics of queues and how to implement them in Java, we can now move on to exploring different queue implementations and their advantages and disadvantages.

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Replace with your Java logic here

    Queue<String> queue = new LinkedList<>();

​

    // Enqueue elements

    queue.add("Apple");

    queue.add("Banana");

    queue.add("Orange");

​

    // Dequeue elements

    while (!queue.isEmpty()) {

      String element = queue.poll();

      System.out.println(element);

    }

  }

}

In the previous screen, we saw how to implement a queue using the LinkedList class in Java. Another common way to implement a queue is using arrays.

Array Implementation of Queues

The array implementation of queues involves using an array to store the items in the queue. Two pointers, front and rear, are used to keep track of the first and last elements of the queue, respectively.

Here's an example of how to implement a queue using an array in Java:

1import java.util.Arrays;
2
3public class ArrayQueue {
4  private static final int DEFAULT_CAPACITY = 10;
5  private int[] queue;
6  private int front;
7  private int rear;
8
9  public ArrayQueue() {
10    queue = new int[DEFAULT_CAPACITY];
11    front = -1;
12    rear = -1;
13  }
14
15  // Other methods
16}

In this implementation, we have an array queue to store the elements, and front and rear pointers to keep track of the first and last elements, respectively. The DEFAULT_CAPACITY is used to specify the initial capacity of the array, and it can be adjusted as needed.

To enqueue an element, we increment the rear pointer and add the element to the queue. If the rear pointer exceeds the array size, we resize the array to accommodate more elements.

To dequeue an element, we increment the front pointer and return the element at the front position. If the front pointer exceeds the rear, it means the queue is empty.

The advantage of the array implementation is that it provides constant-time access to the front and rear elements. However, it has a fixed size and can run out of space if more elements are added than the initial capacity.

Now that we have seen the array implementation of queues, let's move on to the next topic: linked list implementation of queues.

xxxxxxxxxx

}

import java.util.Arrays;

​

public class ArrayQueue {

  private static final int DEFAULT_CAPACITY = 10;

  private int[] queue;

  private int front;

  private int rear;

​

  public ArrayQueue() {

    queue = new int[DEFAULT_CAPACITY];

    front = -1;

    rear = -1;

  }

​

  public void enqueue(int item) {

    if (rear == queue.length - 1) {

      // Queue is full, resize the array

      queue = Arrays.copyOf(queue, queue.length * 2);

    }

    queue[++rear] = item;

    if (front == -1) {

      front = 0;

    }

  }

​

  public int dequeue() {

    if (front == -1 || front > rear) {

      // Queue is empty

      throw new NoSuchElementException();

Another common way to implement a queue is using linked lists. In the linked list implementation, each element in the queue is represented as a node in a linked list, and the front and rear pointers are used to keep track of the first and last nodes, respectively.

Here's an example of how to implement a queue using linked lists in Java:

1class LinkedListQueue<T> {
2  private static class Node<T> {
3    private T data;
4    private Node<T> next;
5
6    public Node(T data) {
7      this.data = data;
8      this.next = null;
9    }
10  }
11
12  private Node<T> front;
13  private Node<T> rear;
14
15  public LinkedListQueue() {
16    this.front = null;
17    this.rear = null;
18  }
19
20  public void enqueue(T item) {
21    Node<T> newNode = new Node<>(item);
22
23    if (isEmpty()) {
24      front = newNode;
25    } else {
26      rear.next = newNode;
27    }
28
29    rear = newNode;
30  }
31
32  public T dequeue() {
33    if (isEmpty()) {
34      throw new NoSuchElementException("Queue is empty");
35    }
36
37    T data = front.data;
38    front = front.next;
39
40    if (front == null) {
41      rear = null;
42    }
43
44    return data;
45  }
46
47  public boolean isEmpty() {
48    return front == null;
49  }
50}

xxxxxxxxxx

}

class LinkedListQueue<T> {

  private static class Node<T> {

    private T data;

    private Node<T> next;

​

    public Node(T data) {

      this.data = data;

      this.next = null;

    }

  }

​

  private Node<T> front;

  private Node<T> rear;

​

  public LinkedListQueue() {

    this.front = null;

    this.rear = null;

  }

​

  public void enqueue(T item) {

    Node<T> newNode = new Node<>(item);

​

    if (isEmpty()) {

      front = newNode;

    } else {

      rear.next = newNode;

    }

​

    rear = newNode;

Now that we understand the basics of queues and their implementations, let's dive into the operations that we can perform on a queue.

The two fundamental operations of a queue are: enqueue and dequeue.

1. Enqueue: This operation adds an element to the rear end of the queue. The enqueue operation is also known as insertion.

Here's the Java code for enqueue operation in a basic array implementation of a queue:

1void enqueue(int item) {
2    if (isFull()) {
3        throw new IllegalStateException("Queue is full");
4    }
5    
6    rear = (rear + 1) % maxSize;
7    queue[rear] = item;
8    currentSize++;
9}

2. Dequeue: This operation removes an element from the front end of the queue. The dequeue operation is also known as deletion.

Here's the Java code for dequeue operation in a basic array implementation of a queue:

1int dequeue() {
2    if (isEmpty()) {
3        throw new NoSuchElementException("Queue is empty");
4    }
5    
6    int item = queue[front];
7    front = (front + 1) % maxSize;
8    currentSize--;
9    return item;
10}

It's important to note that both enqueue and dequeue operations have a time complexity of O(1) in a basic array implementation of a queue.

xxxxxxxxxx

}

class QueueOperations {

    private int[] queue;

    private int front;

    private int rear;

    private int maxSize;

    private int currentSize;

    public QueueOperations(int size) {

        maxSize = size;

        queue = new int[maxSize];

        front = 0;

        rear = -1;

        currentSize = 0;

    }

    public void enqueue(int item) {

        if (isFull()) {

            throw new IllegalStateException("Queue is full");

        }

        rear = (rear + 1) % maxSize;

        queue[rear] = item;

        currentSize++;

    }

    public int dequeue() {

        if (isEmpty()) {

            throw new NoSuchElementException("Queue is empty");

        }

Now that we have a good understanding of queues and their implementations, let's explore some real-world applications where queues can be useful.

Real-World Applications of Queues

1. Process Scheduling: Queues are extensively used in operating systems for process scheduling. In an operating system, multiple processes are waiting to be executed. The operating system maintains a queue of processes, and each process gets CPU time based on its priority and the order in which it arrived in the queue.

2. Web Servers: Queues are used in web servers to handle incoming requests. When a web server receives a request, it adds the request to a queue and processes it in a first-come, first-served manner. This ensures that the server can handle multiple requests without overwhelming its resources.

3. Breadth-First Search (BFS): BFS is a graph traversal algorithm that uses a queue to explore all the vertices in a graph. It starts from a given vertex, visits all its neighbors, and then visits their neighbors in a level-by-level manner.

4. Print Spooling: In a printing system, when multiple print jobs are sent to a printer, they are stored in a queue. The printer then processes the jobs in the order they were received, ensuring that all jobs are printed without any interference.

5. Call Center Phone System: In a call center, incoming calls are often put on hold until a customer service representative becomes available. The calls are typically placed in a queue and handled on a first-come, first-served basis.

These are just a few examples of the many real-world applications where queues play a vital role. As you can see, queues are versatile data structures that can be used to manage and process various types of tasks in a systematic and organized manner.

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    Queue<String> queue = new LinkedList<>();

    // Enqueue elements to the queue

    queue.add("Alice");

    queue.add("Bob");

    queue.add("Charlie");

    queue.add("Dave");

    // Dequeue elements from the queue

    while (!queue.isEmpty()) {

      String person = queue.remove();

      System.out.println("Processing " + person + "...");

      // replace with your custom logic here

    }

  }

}

Priority Queues

In the previous lessons, we learned about the basic queue data structure and its implementations. Now, let's move on to priority queues.

A priority queue is a variation of a queue where each element has a priority associated with it. The priority determines the order in which the elements are processed. The element with the highest priority is processed first.

Priority queues have the following characteristics:

• Elements are dequeued in order of their priority.
• When enqueuing elements, they are inserted based on their priority.
• Elements with the same priority are dequeued in the order they were enqueued.

Unlike a basic queue, which is a FIFO (First In First Out) data structure, a priority queue is an ordered data structure. Depending on the implementation, elements can be ordered in either ascending or descending order of their priorities.

Let's take a look at an example of a priority queue in Java:

1class Main {
2  public static void main(String[] args) {
3    // Priority Queue Example
4    PriorityQueue<Integer> pq = new PriorityQueue<>();
5    
6    pq.add(5);
7    pq.add(3);
8    pq.add(8);
9    pq.add(1);
10    pq.add(10);
11    
12    while (!pq.isEmpty()) {
13      System.out.println(pq.poll());
14    }
15  }
16}

Output:

11
23
35
48
510

In this example, we create a priority queue and add a few elements to it. The priority queue automatically orders the elements based on their values. When we dequeue the elements using the poll() method, they are returned in ascending order.

Priority queues are commonly used in various applications. For example:

• Task Scheduling: Priority queues can be used to schedule tasks in an application based on their priority levels.
• Event-driven Systems: Priority queues can be used to handle events based on their priority, ensuring that high-priority events are processed first.
• Graph Algorithms: Priority queues are often used in graph algorithms like Dijkstra's algorithm and Prim's algorithm to select the next vertex or edge to visit based on their priority.

By using a priority queue, you can efficiently process elements based on their priorities and optimize various algorithms and systems.

Now that we have a basic understanding of priority queues, let's explore their implementation and operations in more detail.

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Priority Queue Example

    PriorityQueue<Integer> pq = new PriorityQueue<>();

    pq.add(5);

    pq.add(3);

    pq.add(8);

    pq.add(1);

    pq.add(10);

    while (!pq.isEmpty()) {

      System.out.println(pq.poll());

    }

  }

}

Circular Queues

In the previous lessons, we learned about the basic queue data structure and its implementations, such as array-based and linked-list-based queues. Now, let's dive into the concept of circular queues.

A circular queue is a variant of the basic queue data structure in which the last position is connected back to the first position to form a circle. This allows for efficient memory utilization and addresses the issue of wasted space in a regular queue.

Implementation

Circular queues can be implemented using arrays by considering the following properties:

• Front: the index of the first item in the queue
• Rear: the index of the last item in the queue
• Size: the current number of elements in the queue

To enqueue an element in a circular queue, we need to check whether the queue is full. If the queue is not full, we increment the rear index and add the element at the rear position. In case the rear index reaches the end of the array, we wrap it around to the beginning of the array (0 index).

To dequeue an element from a circular queue, we need to check whether the queue is empty. If the queue is not empty, we remove the element at the front index and increment the front index. If the front index reaches the end of the array, we wrap it around to the beginning of the array (0 index).

Here's an example of implementing and using a circular queue in Java:

{{code}}

Output:

15
23
38
41
510
67
72

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Circular Queue Example

    CircularQueue<Integer> cq = new CircularQueue<>(5);

    cq.enqueue(5);

    cq.enqueue(3);

    cq.enqueue(8);

    cq.enqueue(1);

    cq.enqueue(10);

    System.out.println(cq.dequeue());

    System.out.println(cq.dequeue());

    cq.enqueue(7);

    cq.enqueue(2);

    while (!cq.isEmpty()) {

      System.out.println(cq.dequeue());

    }

  }

}

Double Ended Queues

In the previous lessons, we covered the basic queue data structure along with its implementations and operations. Now, let's explore another variant of the queue called a Double Ended Queue (Deque).

A Double Ended Queue is a type of queue where insertion and deletion operations can be performed at both ends, i.e., the front and the rear. This allows for more flexibility in manipulating and accessing the elements in the queue.

Implementation

Double Ended Queues can be implemented using arrays or linked lists. In Java, the Deque interface provides a way to implement Double Ended Queues. Java provides two classes that implement the Deque interface:

1. ArrayDeque: It is an implementation of Deque using a resizable array.
2. LinkedList: It is an implementation of Deque using a doubly-linked list.

Here's an example of using the Deque interface to implement a Double Ended Queue in Java:

1{{code}}

Output:

1Deque: [E, L, O]
2Removed Element: E
3Updated Deque: [L, O]

xxxxxxxxxx

import java.util.Deque;

import java.util.LinkedList;

​

public class Main {

    public static void main(String[] args) {

        Deque<String> deque = new LinkedList<>();

​

        deque.addFirst("E");

        deque.addLast("L");

        deque.addLast("O");

​

        System.out.println("Deque: " + deque);

​

        String element = deque.removeFirst();

​

        System.out.println("Removed Element: " + element);

​

        System.out.println("Updated Deque: " + deque);

    }

}

Implementing Queue using Stacks

In the previous lessons, we have discussed different implementations of the queue data structure using arrays and linked lists. Now, let's explore another interesting approach - implementing a queue using stacks.

Approach

To implement a queue using stacks, we can use two stacks: one for the enqueue operation and one for the dequeue operation. Let's call them stack1 and stack2, respectively.

Here's a basic outline of the queue implementation using stacks:

1. When an element needs to be enqueued, we simply push it onto stack1.
2. For the dequeue operation, we first check if both stack1 and stack2 are empty. If they are, then the queue is empty and we throw an exception.
3. If stack2 is empty, we transfer all the elements from stack1 to stack2 in reverse order, so that the first element pushed onto stack1 becomes the first element at the top of stack2 (which ensures FIFO order).
4. Finally, we pop and return the top element from stack2 as the dequeued element.

Here is a Java implementation of a queue using stacks:

1{{code}}

Example

Let's enqueue elements 1, 2, and 3 to the queue and then dequeue an element. The internal state of stack1 and stack2 would be as follows:

1stack1: [1, 2, 3]
2stack2: []

After dequeuing an element, the internal state would be:

1stack1: []
2stack2: [3, 2]

The dequeued element would be 1.

By implementing a queue using stacks, we can effectively achieve the FIFO behavior of a queue using the LIFO behavior of stacks. This approach can be useful in scenarios where a stack is readily available or preferred over other data structures. It's important to note that the time complexity of both the enqueue and dequeue operations is O(n), where n is the number of elements in the queue, due to the transfer of elements between the two stacks. However, the space complexity is O(n).

xxxxxxxxxx

}

class QueueUsingStack {

​

    private Stack<Integer> stack1;

    private Stack<Integer> stack2;

​

    public QueueUsingStack() {

        stack1 = new Stack<>();

        stack2 = new Stack<>();

    }

​

    public void enqueue(int num) {

        stack1.push(num);

    }

​

    public int dequeue() {

        if (stack1.isEmpty() && stack2.isEmpty()) {

            throw new NoSuchElementException("Queue is empty");

        }

​

        if (stack2.isEmpty()) {

            while (!stack1.isEmpty()) {

                stack2.push(stack1.pop());

            }

        }

​

        return stack2.pop();

    }

​

    public boolean isEmpty() {

Queue Design Problems

In the previous lessons, we have discussed various implementations of queues and explored different operations associated with queues. Now, let's dive into solving design problems related to queues.

Design Problem 1: Implement a Circular Queue

Problem Statement: Design and implement a circular queue data structure. The circular queue should support the following operations:

1. enQueue: Insert an element into the circular queue. If the queue is full, return false;
2. deQueue: Delete an element from the circular queue. If the queue is empty, return false;
3. isEmpty: Check whether the circular queue is empty or not;
4. isFull: Check whether the circular queue is full or not;
5. Front: Get the front item from the queue;
6. Rear: Get the last item from the queue.

You can try solving this design problem yourself or refer to the solution provided in the code snippet above.

Design Problem 2: Implement a Priority Queue

Problem Statement: Design and implement a priority queue data structure. The priority queue should support the following operations:

1. insert: Insert an element into the priority queue;
2. delete: Delete the highest priority element from the priority queue;
3. isEmpty: Check whether the priority queue is empty or not;

Consider using a heap data structure to implement the priority queue. You can try solving this design problem yourself or refer to relevant resources.

These are just a couple of examples of design problems related to queues. As you continue to explore data structures and algorithms, you'll come across many more interesting design problems involving queues.

Feel free to research and attempt other queue design problems outside of this course to further strengthen your problem-solving skills.

xxxxxxxxxx

}

import java.util.Stack;

​

class QueueUsingStacks {

    private Stack<Integer> stack1;

    private Stack<Integer> stack2;

​

    public QueueUsingStacks() {

        stack1 = new Stack<>();

        stack2 = new Stack<>();

    }

​

    public void enqueue(int item) {

        stack1.push(item);

    }

​

    public int dequeue() {

        if (stack1.isEmpty() && stack2.isEmpty()) {

            throw new RuntimeException("Queue is empty!");

        }

​

        if (stack2.isEmpty()) {

            while (!stack1.isEmpty()) {

                stack2.push(stack1.pop());

            }

        }

​

        return stack2.pop();

    }

​