Linked List Representation of Queue

• Linked list is the another way of Queue Implementation.
• EnQueue Operation will be apply at the end of List.
• DeQueue operation will be apply at the beginning.
• Linked List representation is something good approach,because it is growable and shrinkable as per requirements.

We can implement the Queue in two ways :
1-: Using HeadPointer Only (Not a good Approach,we will not discuss).
2-: Using HeadPointer and TailPointer (Preferable Approach)

• EnQueue Operation is similar to the Insertion of node at last(end) in SLL.
• DeQueue Operation is similar to the Deletion of node at beginning(front) in SLL.

1- EnQueue & DeQueue(Insertion & Deletion Operation)

Working process of EnQueue and DeQueue is following :

Code Implementation

                       /*Using HeaderPointer and TailPointer*/
#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct CreateNode   // Node Structure Initialization
{
	int  data;          // for data element
	struct CreateNode* nextNode;   //for storing the address of next element
};
struct CreateNode *front = NULL;    // Initialization of HeadPointer/front
struct CreateNode *rear = NULL;    //  Initialization of TailPointer/rear
bool IsEmptyQueue()    // Method to check the Empty status of Queue.
{
	return front == NULL;
}
void EnQueue(int data)   // Method of EnQueue Operation
{
	//Memory Initialization for NewNode
	struct CreateNode* NewNode = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	if (NewNode != NULL)
	{
		if (front == NULL || rear == NULL)
		{
			NewNode->data = data;
			front = NewNode;
			rear =  NewNode;
			NewNode->nextNode = NULL;
			printf("DataElement %d has been inserted...\n",data);
		}
		else
		{
			NewNode->data = data;
			NewNode->nextNode = NULL;
			rear->nextNode = NewNode;
			rear = NewNode;
			printf("DataElement %d has been inserted...\n", data);
		}
	}
	else
	{
		printf("Memory is not Initialized for New DataElement.");
	}
}
void DeQueue()   // Method of DeQueue Operation
{
	if (!IsEmptyQueue())
	{
		struct CreateNode* TempNode = NULL;  // Create one TempNode 
		TempNode = front;
		front = front->nextNode;
		printf("%d is deleted from the front\n ", TempNode->data);
		free(TempNode);  // delete the front node or Memory deallocation of front node.
	}
	else
		printf("Queue is in the Underflow Condition...");
}
int main()
{
	int data, choice, ChooseEnQDeQ;
	do
	{
		printf("1 : for EnQueue Operation\n");
		printf("2 : for DeQueue Operation\n");
		printf("Press 1 or 2 --- : ");
		std::cin >> ChooseEnQDeQ;
		switch (ChooseEnQDeQ)
		{
		case 1:
			do
			{
				printf("Enter the data for EnQueue :");
				std::cin >> data;
				EnQueue(data);
				printf("Press 0 for more EnQueue :");
				std::cin >> choice;
			} while (choice == 0);
			break;
		case 2:
			do
			{
				DeQueue();
				printf("\nPress 0 for more DeQueue Operation :");
				std::cin >> choice;
			} while (choice == 0);
			break;
		}
	} while (ChooseEnQDeQ==1 || ChooseEnQDeQ==2);

	printf("DataElement after EnQueue/DeQueue process :\n");
	struct CreateNode *Temp = front;
	while (Temp->nextNode != NULL)
	{
		printf("%d ", Temp->data);
		Temp = Temp->nextNode;
	}
	printf("%d ", Temp->data);
	_getch();
	return 0;
}

Time & Space Complexity

• EnQueue Time Complexity will be O(1).
• DeQueue Time Complexity will be O(1).
• IsEmptyQueue Time Complexity will be O(1).
• Space Complexity will be O(n).