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.