Implementing a Queue using Array
A queue can be implemented efficiently using a fixed size array. Operations like enqueue and dequeue have O(1) time complexity.
Java example:
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
| public class MyQueue {
private int[] arr;
private int front;
private int rear;
private int size;
public MyQueue(int capacity) {
arr = new int[capacity];
}
public void enqueue(int item) {
if (isFull()) {
// handle overflow
}
arr[rear] = item;
rear = (rear + 1) % arr.length;
size++;
}
public int dequeue() {
if (isEmpty()) {
// handle underflow
}
int item = arr[front];
front = (front + 1) % arr.length;
size--;
return item;
}
// other methods like isFull(), isEmpty() etc.
}
|
C++ example:
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
| class MyQueue {
private:
int arr[MAX_SIZE];
int front;
int rear;
int size;
public:
MyQueue() {
front = 0;
rear = -1;
size = 0;
}
void enqueue(int item) {
if (isFull())
// handle overflow
rear = (rear + 1) % MAX_SIZE;
arr[rear] = item;
size++;
}
int dequeue() {
if (isEmpty())
// handle underflow
int item = arr[front];
front = (front + 1) % MAX_SIZE;
size--;
return item;
}
// other methods
};
|
Python example:
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
| class MyQueue:
def __init__(self, capacity):
self.arr = [None] * capacity
self.capacity = capacity
self.front = 0
self.rear = -1
self.size = 0
def enqueue(self, item):
if self.isFull():
# handle overflow
self.rear = (self.rear + 1) % self.capacity
self.arr[self.rear] = item
self.size += 1
def dequeue(self):
if self.isEmpty():
# handle underflow
item = self.arr[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
# other methods
|
Modeling a queue with array provides simple and efficient implementation.
A Queue is a First-In-First-Out (FIFO) data structure, meaning the first element added will be the first to be removed. A queue implemented using an array requires an array to hold the elements and two integers to mark the front and rear of the queue. The primary operations are enqueue
, which adds an element to the rear, and dequeue
, which removes the front element. Optionally, a peek
operation can retrieve the front element without removing it.
Example Code
Java
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
| public class Queue {
private int[] arr;
private int front;
private int rear;
public Queue(int size) {
arr = new int[size];
front = -1;
rear = -1;
}
public void enqueue(int value) {
if (rear == arr.length - 1) {
System.out.println("Queue is full");
return;
}
if (front == -1) front = 0;
arr[++rear] = value;
}
public int dequeue() {
if (front == -1) {
System.out.println("Queue is empty");
return -1;
}
int val = arr[front];
if (front == rear) {
front = rear = -1;
} else {
front++;
}
return val;
}
public int peek() {
if (front == -1) {
System.out.println("Queue is empty");
return -1;
}
return arr[front];
}
}
|
C++
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
46
| #include <iostream>
using namespace std;
class Queue {
private:
int* arr;
int front;
int rear;
int size;
public:
Queue(int size) : size(size), front(-1), rear(-1) {
arr = new int[size];
}
void enqueue(int value) {
if (rear == size - 1) {
cout << "Queue is full" << endl;
return;
}
if (front == -1) front = 0;
arr[++rear] = value;
}
int dequeue() {
if (front == -1) {
cout << "Queue is empty" << endl;
return -1;
}
int val = arr[front];
if (front == rear) {
front = rear = -1;
} else {
front++;
}
return val;
}
int peek() {
if (front == -1) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[front];
}
};
|
Python
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
| class Queue:
def __init__(self, size):
self.arr = [None] * size
self.front = -1
self.rear = -1
self.size = size
def enqueue(self, value):
if self.rear == self.size - 1:
print("Queue is full")
return
if self.front == -1:
self.front = 0
self.rear += 1
self.arr[self.rear] = value
def dequeue(self):
if self.front == -1:
print("Queue is empty")
return None
val = self.arr[self.front]
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front += 1
return val
def peek(self):
if self.front == -1:
print("Queue is empty")
return None
return self.arr[self.front]
|
These examples demonstrate how to implement a queue using an array in Java, C++, and Python. The enqueue
, dequeue
, and peek
operations work with front
and rear
indices to maintain the queue’s state.