Implement Circular Queue using linked list

Circular Queue

A circular queue can be implemented using array and linked list. To implement a circular queue using a linked list, you must use a circular linked list where the rear node is connected to the front node.

geeksforgeeks - Circular Linked List

Complexity

• Time Complexity
  • Enqueue : \(O(1)\) 
  • Dequeue: \(O(1)\)
• Space Complexity : \(O(n)\) as the queue is size of \(n\)

Implement Circular Queue using linked list

header

//
//  CircularQueue_LinkedList.hpp
//  c++
//

#ifndef CircularQueue_LinkedList_hpp
#define CircularQueue_LinkedList_hpp

#include <iostream>

namespace CircularLinkedListQueue {
template<typename T>
struct Node {
	T data;
	Node* next;
	
	Node() : data(NULL), next(nullptr) {}
	Node(T data) : data(data), next(nullptr) {}
};

template<typename T>
class Queue {
private:
	// rear of the queue
	Node<T>* rear;
	// front of the queue
	Node<T>* front;
	
public:
	// constructor
	Queue();
	// destructor
	~Queue();
	// check if the queue is empty
	bool isEmpty();
	// enqueue a value
	void enqueue(T value);
	// dequeue a value
	T dequeue();
	// print all values in the queue
	void printAll();
};
}

#endif /* CircularQueue_LinkedList_hpp */

implementation

//
//  CircularQueue_LinkedList.cpp
//  c++
//

#include "CircularQueue_LinkedList.hpp"
using namespace CircularLinkedListQueue;

template <typename T>
Queue<T>::Queue() {
	rear = nullptr;
	front = nullptr;
}

template <typename T>
Queue<T>::~Queue() {
	Node<T>* temp = front;
	while(temp != rear) {
		Node<T>* next = temp->next;
		delete temp;
		temp = next;
	}
	delete rear;
}

template <typename T>
bool Queue<T>::isEmpty() {
	return rear == nullptr && front == nullptr;
}

template <typename T>
void Queue<T>::enqueue(T value) {
	Node<T>* newNode = new Node<T>(value);
	if(isEmpty()) {
		front = rear = newNode;
		rear->next = front;
	} else {
		rear->next = newNode;
		rear = newNode;
		rear->next = front;
	}
}

template <typename T>
T Queue<T>::dequeue() {
	// return default value for T if the queue is empty
	if(isEmpty()) return T();
	
	// if there is only one element in the queue
	if(front == rear) {
		T value = front->data;
		front = rear = nullptr;
		delete front;
		return value;
	}
	
	Node<T>* temp = front;
	T value = front->data;
	front = front->next;
	rear->next = front;
	delete temp;
	return value;
}

template<typename T>
void Queue<T>::printAll() {
	if(isEmpty()) {
		std::cout << "Queue is empty" << std::endl;
		return;
	}
	
	Node<T>* current = front;
	do {
		std::cout << current->data << "->";
		current = current->next;
	} while(current != front);
	std::cout << std::endl;
}

Example

#include <iostream>
#include "CircularQueue_LinkedList.hpp"
using namespace CircularLinkedListQueue;

int main() {
	Queue<int> queue;
	queue.enqueue(1);
	queue.printAll();
	queue.enqueue(2);
	queue.printAll();
	queue.enqueue(3);
	queue.printAll();
	queue.enqueue(4);
	queue.printAll();
	
	queue.dequeue();
	queue.printAll();
	queue.dequeue();
	queue.printAll();
	queue.dequeue();
	queue.printAll();
	queue.dequeue();
	queue.printAll();
	queue.enqueue(5);
	queue.printAll();
	return 0;
}

/*
1->
1->2->
1->2->3->
1->2->3->4->
2->3->4->
3->4->
4->
Queue is empty
5->
*/