Stacks & QueuesProblem 2 of 38
Implement Queue from Scratch
Problem Statement
Implement a queue data structure from scratch that supports the following operations:
enqueue(x)/push(x): Add element x to the rear of the queuedequeue()/pop(): Remove and return the front elementfront()/peek(): Return the front element without removing itisEmpty(): Check if the queue is emptysize(): Return the number of elements in the queue
Example:
enqueue(1) -> Queue: [1]
enqueue(2) -> Queue: [1, 2]
enqueue(3) -> Queue: [1, 2, 3]
front() -> Returns: 1
dequeue() -> Returns: 1, Queue: [2, 3]
size() -> Returns: 2
isEmpty() -> Returns: false
Approach 1: Using Array (Circular Queue)
Intuition
Use a circular array to efficiently utilize space. Maintain front and rear pointers. When either pointer reaches the end of the array, it wraps around to the beginning, forming a circular structure.
Algorithm
- Initialize array with fixed capacity, set front = 0, rear = -1, count = 0
- For enqueue: increment rear circularly
(rear + 1) % capacity, store element - For dequeue: return
arr[front], increment front circularly - Use count to track number of elements and detect full/empty conditions
java
public class Queue {
private int[] arr;
private int frontIndex;
private int rearIndex;
private int count;
private int capacity;
public Queue(int size) {
capacity = size;
arr = new int[capacity];
frontIndex = 0;
rearIndex = -1;
count = 0;
}
public Queue() {
this(1000);
}
public void enqueue(int x) {
if (isFull()) {
throw new RuntimeException("Queue Overflow");
}
rearIndex = (rearIndex + 1) % capacity;
arr[rearIndex] = x;
count++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue Underflow");
}
int val = arr[frontIndex];
frontIndex = (frontIndex + 1) % capacity;
count--;
return val;
}
public int front() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return arr[frontIndex];
}
public int rear() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return arr[rearIndex];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == capacity;
}
public int size() {
return count;
}
public static void main(String[] args) {
Queue q = new Queue(100);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
System.out.println("Front: " + q.front()); // 10
System.out.println("Dequeue: " + q.dequeue()); // 10
System.out.println("Front: " + q.front()); // 20
System.out.println("Size: " + q.size()); // 2
System.out.println("Empty: " + q.isEmpty()); // false
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(n) where n is the capacity of the queue
Approach 2: Using Linked List (Dynamic Size)
Intuition
Use a singly linked list with both head (front) and tail (rear) pointers. Enqueue adds at tail, dequeue removes from head. This allows dynamic sizing without fixed capacity.
Algorithm
- Maintain head (front) and tail (rear) pointers
- For enqueue: create new node, add at tail
- For dequeue: remove node from head
- Handle edge cases when queue becomes empty
java
public class QueueLinkedList {
private class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head; // front
private Node tail; // rear
private int count;
public QueueLinkedList() {
head = null;
tail = null;
count = 0;
}
public void enqueue(int x) {
Node newNode = new Node(x);
if (isEmpty()) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
count++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue Underflow");
}
int val = head.data;
head = head.next;
if (head == null) {
tail = null;
}
count--;
return val;
}
public int front() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return head.data;
}
public int rear() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return tail.data;
}
public boolean isEmpty() {
return head == null;
}
public int size() {
return count;
}
public static void main(String[] args) {
QueueLinkedList q = new QueueLinkedList();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
System.out.println("Front: " + q.front()); // 10
System.out.println("Rear: " + q.rear()); // 30
System.out.println("Dequeue: " + q.dequeue()); // 10
System.out.println("Size: " + q.size()); // 2
System.out.println("Empty: " + q.isEmpty()); // false
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(n) where n is the number of elements in the queue
Key Takeaways
- Circular array implementation efficiently reuses space and avoids shifting elements
- Linked List implementation provides dynamic sizing but uses extra memory for pointers
- All basic queue operations (enqueue, dequeue, front) should be O(1)
- FIFO (First In First Out) is the fundamental property of a queue
- For circular queue, use modulo operator
%to wrap around indices - Maintain separate count variable to easily check empty/full conditions