Queue Implementation
Array Queue
An array-based queue tracks two indexes, front and rear, marking the current start and end of the valid elements, and enqueue/dequeue just move those indexes forward instead of shifting the whole array.
Example: Array Queue
#include <iostream>
using namespace std;
int main() {
int q[5], front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
cout << "Dequeued: " << q[front++] << endl;
cout << "Front now: " << q[front] << ", Rear: " << q[rear];
return 0;
}public class Main {
public static void main(String[] args) {
int[] q = new int[5];
int front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
System.out.println("Dequeued: " + q[front++]);
System.out.println("Front now: " + q[front] + ", Rear: " + q[rear]);
}
}q = [None] * 5
front, rear = 0, -1
for v in (1, 2, 3):
rear += 1
q[rear] = v
print("Dequeued:", q[front])
front += 1
print("Front now:", q[front], ", Rear:", q[rear])#include <stdio.h>
int main() {
int q[5], front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
printf("Dequeued: %d\n", q[front++]);
printf("Front now: %d, Rear: %d", q[front], q[rear]);
return 0;
}Login to try C/C++/Java code in the editor
Linked List Queue
A linked-list-based queue keeps head and tail node references: enqueue adds a new node at the tail, and dequeue removes the node at the head, both in O(1) time regardless of how many elements are in the queue.
Example: Linked List Queue
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, nullptr};
Node* tail = head;
tail->next = new Node{2, nullptr}; tail = tail->next;
tail->next = new Node{3, nullptr}; tail = tail->next;
cout << "Dequeued: " << head->data;
head = head->next;
cout << ", New head: " << head->data;
return 0;
}public class Main {
static class Node { int data; Node next; Node(int d) { data = d; } }
public static void main(String[] args) {
Node head = new Node(1);
Node tail = head;
tail.next = new Node(2); tail = tail.next;
tail.next = new Node(3); tail = tail.next;
System.out.print("Dequeued: " + head.data);
head = head.next;
System.out.println(", New head: " + head.data);
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = tail = Node(1)
for v in (2, 3):
tail.next = Node(v)
tail = tail.next
print("Dequeued:", head.data)
head = head.next
print("New head:", head.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *head = malloc(sizeof(struct Node));
head->data = 1; head->next = NULL;
struct Node *tail = head;
tail->next = malloc(sizeof(struct Node)); tail = tail->next; tail->data = 2; tail->next = NULL;
printf("Dequeued: %d\n", head->data);
head = head->next;
printf("New head: %d", head->data);
return 0;
}Login to try C/C++/Java code in the editor
Queue Overflow
An array-backed queue overflows when the rear index reaches the array's capacity and there's no room left for another element, even if earlier slots were freed up by prior dequeues (unless it wraps around, like a circular queue).
Example: Queue Overflow
#include <iostream>
using namespace std;
int main() {
int q[3], rear = -1;
int capacity = 3;
for (int i = 0; i < 4; i++) {
if (rear == capacity - 1) { cout << "Overflow! Cannot enqueue " << i + 1; break; }
q[++rear] = i + 1;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] q = new int[3];
int rear = -1, capacity = 3;
for (int i = 0; i < 4; i++) {
if (rear == capacity - 1) { System.out.println("Overflow! Cannot enqueue " + (i + 1)); break; }
q[++rear] = i + 1;
}
}
}q = [None] * 3
rear = -1
capacity = 3
for i in range(4):
if rear == capacity - 1:
print("Overflow! Cannot enqueue", i + 1)
break
rear += 1
q[rear] = i + 1#include <stdio.h>
int main() {
int q[3], rear = -1, capacity = 3;
for (int i = 0; i < 4; i++) {
if (rear == capacity - 1) { printf("Overflow! Cannot enqueue %d", i + 1); break; }
q[++rear] = i + 1;
}
return 0;
}Login to try C/C++/Java code in the editor
Queue Underflow
Underflow happens when a dequeue is attempted on an empty queue, meaning front and rear indicate there's nothing left to remove, and an implementation should check for this explicitly rather than returning garbage.
Example: Queue Underflow
#include <iostream>
using namespace std;
int main() {
int front = 0, rear = -1;
if (front > rear) cout << "Underflow! Queue is empty.";
else cout << "Dequeue OK";
return 0;
}public class Main {
public static void main(String[] args) {
int front = 0, rear = -1;
if (front > rear) System.out.println("Underflow! Queue is empty.");
else System.out.println("Dequeue OK");
}
}front, rear = 0, -1
if front > rear:
print("Underflow! Queue is empty.")
else:
print("Dequeue OK")#include <stdio.h>
int main() {
int front = 0, rear = -1;
if (front > rear) printf("Underflow! Queue is empty.");
else printf("Dequeue OK");
return 0;
}Login to try C/C++/Java code in the editor
Queue Using Two Pointers
Tracking front and rear as two separate positions, rather than trying to reuse a single index for both, is what keeps enqueue and dequeue each a clean, constant-time operation without needing to shift any existing elements.
Example: Queue Using Two Pointers
#include <iostream>
using namespace std;
int main() {
int q[5], front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2;
int dequeued = q[front++];
q[++rear] = 3;
cout << "Dequeued: " << dequeued << ", front=" << front << ", rear=" << rear;
return 0;
}public class Main {
public static void main(String[] args) {
int[] q = new int[5];
int front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2;
int dequeued = q[front++];
q[++rear] = 3;
System.out.println("Dequeued: " + dequeued + ", front=" + front + ", rear=" + rear);
}
}q = [None] * 5
front, rear = 0, -1
rear += 1; q[rear] = 1
rear += 1; q[rear] = 2
dequeued = q[front]; front += 1
rear += 1; q[rear] = 3
print("Dequeued:", dequeued, ", front=", front, ", rear=", rear)#include <stdio.h>
int main() {
int q[5], front = 0, rear = -1;
q[++rear] = 1; q[++rear] = 2;
int dequeued = q[front++];
q[++rear] = 3;
printf("Dequeued: %d, front=%d, rear=%d", dequeued, front, rear);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: