Implement Queue using Array Editorial

Practice Problem Link: Implement Queue using Array

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement a queue using an array as the underlying container.

The Queue class should support the following methods:

• int size()
• boolean isEmpty()
• int front()
• int back()
• void push(int element)
• void pop()

Approach

We will implement each of the functions by keeping track of the parameters: current size of the queue, start pointer and end pointer. We enqueue an article from the front and dequeue an article from the rear. We can simply increment front and rear pointers accordingly, but there might be edge cases to be handled at the endpoints of the queue. So to avoid these errors, we increment the front and rear pointers in a circular fashion. Refer to the implementation for a better understanding of the concept.

Analysis

• Time Complexity: O(1) for all the functions
• Space Complexity: O(1) for all the functions

Implementation

C++

// Implement the Queue class
class Queue {
public:
	int frontTrack, rear, currentSize;
    int capacity;
    vector<int> queue;
	Queue (int capacity) {
		this->capacity = capacity;
		frontTrack = this->currentSize = 0;
		rear = capacity - 1;
		queue.resize(this->capacity);
	}

	bool isEmpty() {
		return currentSize == 0;
	}
	
	int size() {
		return currentSize;
	}
	
	int front() {
		if(isEmpty()) {
			return -1;
		}
		return this->queue[this->frontTrack];
	}
	
	int back() {
		if (isEmpty()) {
            return -1;
		}
        return this->queue[this->rear];
	}
	
	void push(int element) {
		if (currentSize == capacity) {
            return;
		}
        this->rear = (this->rear + 1) % this->capacity;
        this->queue[this->rear] = element;
        this->currentSize = (this->currentSize) + 1;
	}
	
	void pop() {
		this->frontTrack = (this->frontTrack + 1) % this->capacity;
        this->currentSize = this->currentSize - 1;
	}
};

Java

class Queue {
	int front, rear, currentSize;
    int capacity;
    int arr[];
	Queue (int capacity) {
		this.capacity = capacity;
        front = this.currentSize = 0;
        rear = capacity - 1;
        arr = new int[this.capacity];
	}

	boolean isEmpty() {
		return (currentSize == 0);
	}
	
	int size() {
		return currentSize;
	}
	
	int front() {
		if (isEmpty())
            return -1;
 
        return this.arr[this.front];
	}
	
	int back() {
		if (isEmpty())
            return -1;
 
        return this.arr[this.rear];
	}
	
	void push(int element) {
		if (currentSize == capacity) {
            return;
		}
        this.rear = (this.rear + 1)
                    % this.capacity;
        this.arr[this.rear] = element;
        this.currentSize = this.currentSize + 1;
       
	}
	
	void pop() {
        this.front = (this.front + 1)
                     % this.capacity;
        this.currentSize = this.currentSize - 1;

	}
}