Queue

2 Comments / Data Structure, Queue

Queue is a linear data structure. It follows First In First Out (FIFO). In other words, the item which is inserted first is accessed/deleted first.

For example, when you go to cashier in a mall, then the person first in line is served first. This is a queue.

Basic Operations:-

  1. enqueue/push: Insert item in the queue.
  2. dequeue/pop: pops/deletes an item from the queue.
  3. peek/front: access the element in front.

Implementation:

  1. using Array
  2. using LinkedList

Queue using array

This method is never used for practical purposes.

Steps

  1. We declare an array que.
  2. We initialize 2 variables front and rear, front stores the index of the beginning and rear stores index of the end of the queue.
  3. For enqueue operation, we increment rear and insert data at que[rear].
  4. For dequeue operation, we increment front.
queue using array queue operations
using array

Code

#include<stdio.h>

/*
First, we declare 4 global variables 
que: stores the queue elements
size: maximum size of the que
front: index of first element of que
rear: index of last element of que
*/

int que[100];
int size = 100;
int rear = -1;
int front = 0;

/*
The qneueue(x) function pushes the value 'x' at the end of the queue
If the queue is full, "OverFlow" message is printed on screen else
*/
void enqueue(int x){
        // check if queue is full or not
	if(rear==size-1){
		printf("OverFlow \n");
	}
	else{
		++rear;
		que[rear] = x;
	}
}

/* returns true if queue is empty */
int isEmpty(){
	if(front>rear)
		return 1;
	else
		return 0;
}

/*
Returns front elemnt of the queue
*/
int peek(){
        // check if stack is empty or not
	if(isEmpty()){
		printf("UnderFlow \n");
		return -1;
	}
	else{
		return que[front];
	}
}

/*
removes front element from the queue
*/
void dequeue(){
        // check if stack is empty or not
	if(isEmpty()){
		printf("UnderFlow \n");
	}
	else{
		printf("%d removed from the queue\n",que[front]);
		++front;
	}
}

int main()
{	
	int choice,x;	
	printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
	do{
		printf("ENTER YOUR CHOICE: ");
		scanf("%d",&choice);
		switch(choice){
			case 1:
				printf("Enter data: ");
				scanf("%d",&x);
				enqueue(x);
				break;
			case 2:
				dequeue();
				break;
			case 3:
				printf("Element at front of queue is: %d\n",peek());
				break;
			case 4:
				if(isEmpty())	printf("Queue is Empty\n");
				else			printf("Queue is not Empty\n");
		}
		
	}while(choice>=1&&choice<=4);
}

Output

1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 150
ENTER YOUR CHOICE: 1
Enter data: 50
ENTER YOUR CHOICE: 2
100 removed from the queue
ENTER YOUR CHOICE: 2
150 removed from the queue
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 300
ENTER YOUR CHOICE: 3
Element at front of queue is: 50
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0

Advantages

  • Easy to implement.
  • No need to store the address of the next element.

Disadvantages

  • Suppose we have an array of size 100. Due to repeated dequeue, enqueue operations, the front and rear become 99. This means there’s only 1 element in the queue. We want to enqueue again. Even tho the array is mostly empty, we won’t be able to enqueue because of rear == size-1.
    To perform enqueue, we will need to shift data from the end to the front of the array. This increases the complexity from O(1) to O(N), where N is the size of the array.
    To overcome this problem, we use a circular queue.

Queue using LinkedList

Steps

  1. Initialize 2 nodes, front, and rear. front point to the beginning and rear point to the node at the end of the queue.
  2. To enqueue,
    1. Initialize a new node temp.
    2. Store temp address in the rear.
    3. Make temp the new rear.
  3. To dequeue, make the node next to front the new front.
queue using linked list queue operations
using linkedlist

Code


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

struct node{
	int v; // value to be store in queue
	struct node *next; // to store address os the next node
};

// points to the top of the stack
struct node *front,*rear;

/*
The push(x) function pushes the value 'x' at the end of the queue
*/
void enqueue(int x){
	struct node *temp = (struct node*)malloc(sizeof(struct node));
	if(temp==NULL){
		printf("failed to allocated memory\n");
		return;
	}
	temp->v = x;
	temp->next = NULL;
	if(front==NULL){
		// this block will run if queue is empty
		front = rear = temp;
	}
	else{
		rear->next = temp;
		rear = temp;
	}
}

/*
Returns front node value of the queue
*/
int peek(){
	if(front==NULL){
		printf("UnderFlow \n");
		return -1;
	}
	else{
		return front->v;
	}
}

/*
deletes the front node of the queue
*/
void dequeue(){
	if(front==NULL){
		printf("UnderFlow \n");
	}
	else{
		printf("%d removed form the queue\n",front->v);
		// initialize temp with front node address
		node *temp = front;
		// Set Top to node just below it
		front = front->next;
		// release memory of popped element
		// since it is no longer of out use
		// if memory is not released
		// then at one point system will have no memory left
		// and operations which may required new memory
		// will fail, like creation of new node
		free(temp);
	}
}

int isEmpty(){
	if(front==NULL)
		return 1;
	else
		return 0;
}

int main()
{	
	front = rear = NULL;
    int choice,x;	
	printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
	do{
		printf("ENTER YOUR CHOICE: ");
		scanf("%d",&choice);
		switch(choice){
			case 1:
				printf("Enter data: ");
				scanf("%d",&x);
				enqueue(x);
				break;
			case 2:
				dequeue();
				break;
			case 3:
				printf("Element at front of queue is: %d\n",peek());
				break;
			case 4:
				if(isEmpty())	printf("Queue is Empty\n");
				else			printf("Queue is not Empty\n");
		}
		
	}while(choice>=1&&choice<=4);
	return 0;
}

Output

1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 200
ENTER YOUR CHOICE: 2
100 removed form the queue
ENTER YOUR CHOICE: 2
400 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 200
ENTER YOUR CHOICE: 1
Enter data: 500
ENTER YOUR CHOICE: 2
200 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 500
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0

Advantages

  • The number of nodes is equal to the number of elements in the queue. No need to allocated more memory than required, unlike arrays.
  • LinkedList can easily grow/shrink.

Disadvantages

  • Complex as compared to arrays.
  • Extra memory required to store the address of the next node.

Applications

  1. It is used to implement First Come First Serve (FCFS) algorithms.
  2. In the operating system, the interrupts of equal priority are served on a first-come basis.
  3. It is used by some network protocols like Token-Bucket, to handle packets.

References

https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues#Linked_List_Implementation_2

Leave a Comment

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