Implement Queue using Linked List Editorial

Practice Problem Link: Implement Queue using Linked List

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

Problem Statement

Implement a queue using a Linked List 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 keep two linked-list pointers that point to the front and the rear of the queue. We also keep track of the size and capacity of the queue. We move the front and the rear pointers accordingly based on the push and pop operations to perform these operations in constant time. Also, adjust the size of the queue as required during these operations. Refer to the implementation for more details.

Analysis

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

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

// Implement the Queue class
class Queue {
public:
	ListNode* queueFront;
	ListNode* rear;
	int queueSize = 0;
	int total = 0;
	Queue (int capacity) {
		queueFront = rear = NULL;
		queueSize = 0;
		total = capacity;
	}

	bool isEmpty() {
		return rear == NULL;
	}
	
	int size() {
		return queueSize;
	}
	
	int front() {
		if(queueFront == NULL) {
			return -1;
		}
		return queueFront->data;
	}
	
	int back() {
		if(rear == NULL) {
			return -1;
		}
		return rear->data;
	}
	
	void push(int element) {
		ListNode* temp = new ListNode(element);
		if (rear == NULL) {
            queueFront = rear = temp;
			queueSize++;
            return;
        }
		rear->next = temp;
        rear = temp;
		queueSize++;
	}
	
	void pop() {
		if (this->queueFront == NULL) {
            return;
		}
        ListNode* temp = this->queueFront;
        queueFront = queueFront->next;
        if (queueFront == NULL) {
            rear = NULL;
		}
		queueSize--;
	}
};

Java

/* This is the ListNode class definition
class ListNode {
	int data;
	ListNode next;
	
	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
*/

// Implement the Queue class
class Queue{
	ListNode front;
	ListNode rear;
	int size = 0;
	int total = 0;
	
	Queue (int capacity) {
		front = rear = null;
		size = 0;
		total = capacity;

	}

	boolean isEmpty() {
		return rear == null;
	}
	
	int size() {
		return size;
	}
	
	int front() {
		if(front == null) {
			return -1;
		}
		return front.data;
	}
	
	int back() {
		if(rear == null) {
			return -1;
		}
		return rear.data;

	}
	
	void push(int element) {
		ListNode temp = new ListNode(element);
		if (rear == null) {
            front = rear = temp;
			size++;
            return;
        }
		rear.next = temp;
        rear = temp;
		size++;

	}
	
	void pop() {
		if (this.front == null) {
            return;
		}
        ListNode temp = this.front;
        front = front.next;
        if (front == null) {
            rear = null;
		}
		size--;
	}
}