Spread the love

Write a c program to implement a queue using an array and linked list

Queue is abstract data type in data structure which works as FIFO principle. FIFO means “First in First out”, i.e the element which we have inserted first will be deleted first and the element that we have inserted last will be deleted last. You can have c program to implement queue using array, using stack and using linked list. Two variables are used to implement queue, i.e “rear” and “front”. Insertion will be done at rear side and deletion will be performed at front side. Real-life example of queues are above which will use concept of queue.

 queue

Here we use circular array to implement queue which is quite efficient than tradition simple array implementation.

Array  implementation of Queue

#include <stdio.h>
 
int A[10], front=-1, rear=-1; // Creating Queue
int size_A = sizeof(A)/sizeof(A[0]); // Calculating Size of Array Dynamically
 
/* Driver Function */
int IsEmpty();
void Insert(int data);
int Delete();
void PrintQueue();
 
/* Main Method */
int main()
{
	Insert(0);
	Insert(1);
	Insert(2);
	Insert(3);
	Delete(); // Delete 0 from starting
	Delete(); // Delete 1 from starting
	PrintQueue(); //Print Queue
	return 0;
}
 
int IsEmpty()
{
	if(rear==-1 && front==-1)
		return 1;
	else
		return 0;
}
 
void Insert(int data)
{
	if(IsEmpty())
		front = rear = 0;
	else if( rear+1 == front )
		printf("\n Queue is Full \n");
	else
		rear = (rear+1)%size_A;
	A[rear] = data;
}
 
int Delete()
{
	if(IsEmpty())
		printf("\n Queue is Empty \n");
	else
		front = (front+1)%size_A;
	return A[front-1];
}
 
void PrintQueue()
{
	int i=0;
	for(i=front;i<=rear;i++)
		printf(" %d",A[i]);
}

 

Linked List implementation of Queue

#include <stdio.h>
#include <stdlib.h>

/* List Structure */
typedef struct Node
{
	int data;
	struct Node *link;
}node;

node *head=NULL;		// Head node to keep track of list

/* Driver Functions */
void EnQueque(int data);
int DeQueue();
void print(node *p);

/* Main Method */
int main()
{
	EnQueque(0);
	EnQueque(1);
	EnQueque(2);
	EnQueque(3);
	DeQueue();			// Delete 0 from list
	DeQueue();			// Delete 1 from list
	
	EnQueque(4);		// Add 4 at the end of list
	
	print(head);		// Print element of queue
	
	return 0;
}

/* Insert Element */
void EnQueque(int data)
{
	// Declaring node
	node *temp = (node*)calloc(1,sizeof(node));
	temp->data = data;
	temp->link = NULL;
	
	// If head is NULL or first node
	if(!head)
	{
		head = temp;
		return;
	}
	node *traverse=head;
	
	// Traverse list upto end
	while(traverse->link)
		traverse = traverse->link;
	
	traverse->link = temp;
}

/* Delete Element */
int DeQueue()
{
	node* temp = head;
	head = head->link;
	
	int data = temp->data;
	
	free(temp);
	
	return data;
}

/* Print queue */
void print(node *p)
{
	printf(" %d",p->data);
	if(!p->link)
		return;
	print(p->link);
}

 

Suggested Reading

  1. Program to check balanced parentheses in expression c++
  2. Write a program to reverse a linked list using stack in c++
  3. Write a program to reverse a string using stack in c++