Queue Linked List Implementation

Queue:

A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.

Basic Operations of Queue:

Given below are the operations of the queue:

  • Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).

  • Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).

  • Front: This function returns the front element of the queue. The time complexity of this function is O(1).

  • Rear: This function returns the last element of the queue. The time complexity of this function is O(1).

  • Peek(): This operation is used to get the value of the element from the front of the queue.

Linked List:

Linked list is a linear data structure just like arrays. In the linked list the elements are not stored in contiguous locations, the elements are connected or linked using pointers. Each node stores the data and the address of the next node.

  • Data: The Data which is stored at the particular address.
  • Reference: The address of the next node of the linked list.

Linked List Representation:

#include 
#include 

struct QNode {
	int key;
	struct QNode* next;
};

struct Queue {
	struct QNode *front, *rear;
};

struct QNode* newNode(int k)
{
	struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
	temp->key = k;
	temp->next = NULL;
	return temp;
}

struct Queue* createQueue()
{
	struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
	q->front = q->rear = NULL;
	return q;
}

void enQueue(struct Queue* q, int k)
{
	struct QNode* temp = newNode(k);

	if (q->rear == NULL) {
		q->front = q->rear = temp;
		return;
	}

	q->rear->next = temp;
	q->rear = temp;
}

void deQueue(struct Queue* q)
{
	if (q->front == NULL)
		return;

	struct QNode* temp = q->front;

	q->front = q->front->next;

	if (q->front == NULL)
		q->rear = NULL;

	free(temp);
}

int main()
{
	struct Queue* q = createQueue();
	enQueue(q, 100);
	enQueue(q, 200);
	deQueue(q);
	deQueue(q);
	enQueue(q, 300);
	enQueue(q, 400);
	enQueue(q, 500);
	deQueue(q);
	printf("Queue Front : %d \n", q->front->key);
	printf("Queue Rear : %d", q->rear->key);
	return 0;
}

#include 
using namespace std;

struct QNode {
	int data;
	QNode* next;
	QNode(int d)
	{
		data = d;
		next = NULL;
	}
};

struct Queue {
	QNode *front, *rear;
	Queue()
	{
		front = rear = NULL;
	}

	void enQueue(int x)
	{

		QNode* temp = new QNode(x);

		if (rear == NULL) {
			front = rear = temp;
			return;
		}

		rear->next = temp;
		rear = temp;
	}

	void deQueue()
	{
		if (front == NULL)
			return;

		QNode* temp = front;
		front = front->next;

		if (front == NULL)
			rear = NULL;

		delete (temp);
	}
};

int main()
{

	Queue q;
	q.enQueue(100);
	q.enQueue(200);
	q.deQueue();
	q.deQueue();
	q.enQueue(300);
	q.enQueue(400);
	q.enQueue(500);
	q.deQueue();
	cout << "Queue Front : " << (q.front)->data << endl;
	cout << "Queue Rear : " << (q.rear)->data;
}

import java.util.*;
import java.lang.*;
import java.io.*;


class QNode {
	int key;
	QNode next;

	public QNode(int key)
	{
		this.key = key;
		this.next = null;
	}
}

class Queue {
	QNode front, rear;

	public Queue()
	{
		this.front = this.rear = null;
	}

	void enqueue(int key)
	{

		QNode temp = new QNode(key);

		if (this.rear == null) {
			this.front = this.rear = temp;
			return;
		}

		this.rear.next = temp;
		this.rear = temp;
	}

	void dequeue()
	{
		if (this.front == null)
			return;

		
		QNode temp = this.front;
		this.front = this.front.next;

		if (this.front == null)
			this.rear = null;
	}
}

 class Test {
	public static void main(String[] args)
	{
		Queue q = new Queue();
		q.enqueue(100);
		q.enqueue(200);
		q.dequeue();
		q.dequeue();
		q.enqueue(300);
		q.enqueue(400);
		q.enqueue(500);
		q.dequeue();
		System.out.println("Queue Front : " + q.front.key);
		System.out.println("Queue Rear : " + q.rear.key);
	}
}

class Node:
	
	def __init__(self, data):
		self.data = data
		self.next = None

class Queue:
	
	def __init__(self):
		self.front = self.rear = None

	def isEmpty(self):
		return self.front == None
	
	def EnQueue(self, item):
		temp = Node(item)
		
		if self.rear == None:
			self.front = self.rear = temp
			return
		self.rear.next = temp
		self.rear = temp

	def DeQueue(self):
		
		if self.isEmpty():
			return
		temp = self.front
		self.front = temp.next

		if(self.front == None):
			self.rear = None


if __name__== '__main__':
	q = Queue()
	q.EnQueue(100)
	q.EnQueue(200)
	q.DeQueue()
	q.DeQueue()
	q.EnQueue(300)
	q.EnQueue(400)
	q.EnQueue(500)
	q.DeQueue()
	print("Queue Front " + str(q.front.data))
	print("Queue Rear " + str(q.rear.data))
	

Complexity

  • Time complexity of both the operations (enqueue and dequeue) is O(1), as there is no loop required.
  • Space complexity is also constant O(1).

This article tried to discuss Queue Linked List Implementation. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *