Problem

Implementing a queue using a linked list.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input:
Operations: ["enqueue(1)", "enqueue(2)", "front()", "dequeue()", "isEmpty()"]
Output: [null, null, 1, 1, false]
Explanation:
1. Enqueue 1: The queue becomes [1].
2. Enqueue 2: The queue becomes [1, 2].
3. Front: The front element is 1.
4. Dequeue: Remove the front element 1. The queue becomes [2].
5. isEmpty: The queue is not empty, hence returns false.

Solution

Method 1 - Using Linked list

A linked list is an ideal data structure for implementing a queue because it allows efficient addition and removal of elements at both ends. We will use a singly linked list to create the queue, where each node holds a value and a reference to the next node. We maintain pointers to both the front (head) and the rear (tail) of the queue to ensure all operations are efficient.

To make removing the last item from the queue easy, the queue should use a doubly linked list.

Here is the approach:

  1. Node Class: Create a Node class that stores data and a reference to the next node.
  2. Queue Class: Implement the queue using the Node class with pointers to the head and tail nodes.
  3. enqueue(x): Add a new node at the tail or rear point.
  4. dequeue(): Remove the node from the head or front.
  5. isEmpty(): Check if the head or front is null.
  6. front(): Return the value of the head or front node.

The Enqueue method simply adds a new cell to the top of the list, and the Dequeue method removes the bottom cell from the list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    private ListNode head, tail;

    public Solution() {
        head = null;
        tail = null;
    }

    public void enqueue(int x) {
        ListNode newNode = new ListNode(x);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int value = head.val;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int front() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return head.val;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class ListNodeQueue:
    def __init__(self):
        self.rear = None
        self.front = None
        self.count = 0

    # Insert at the rear
    def enqueue(self, item: int) -> bool:
        node = ListNode(item)
        if self.front is None:
            self.front = node
            self.rear = node
        else:
            self.rear.next = node
            self.rear = node

        self.count += 1
        return True

    # Delete at the beginning
    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")

        temp = self.front
        self.front = self.front.next
        
        # If the list becomes empty
        if self.front is None:
            self.rear = None
        
        self.count -= 1
        return temp.val

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.front.val

    def is_empty(self) -> bool:
        return self.count == 0  # We can also do: rear == None and front == None

    def size(self) -> int:
        return self.count