Queue

A Queue is a linear data structure which follows a particular order in which the operations are performed. The order is First in First out (FIFO).

A good example for Queue is, any queue of consumers for resource where the consumer that came first is served first. The main difference between the stack and queue is in removing. In a stack, we remove the most recently added item to the stack; in a queue, we remove the least recently added item to the queue.

Operations on Queue

The following are the basic operations performed on queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front element from queue.

Rear: Get the rear element from queue.

Queue Implementation

The Queue can be implemented using following ways, such as:

• Array implementation of Queue
• Linked List implementation of Queue

Array Implementation of Queue

The Queue can be implemented using Array. For this, we need to keep track of two indices front and rear.  We Enqueue the item at the rear and we Dequeue the item at the front. If we simply increment the front and rear indices in the Array, then there may be problems such as it may reach end of the array. The solution to this problem is to increase front and rear in circular manner.

In Queue, insertion and deletion happens at opposite ends, so implementation of Queue using arrays is not as simple as Stack. To implement a queue using array, create an array arr of size n and take two variables front and rear both of which will be initialized to 0 which means the queue is currently empty. The variable rear is the index value which stores the rear index of the array whereas the variable front stores the index of the first element of the array. Following are the some of the implementations of Queue operations such as:

1. Enqueue: This is an addition of element to the Queue. Adding an element to the queue is performed only after checking whether the Queue is full or not. Once the queue is full, we simply return by saying that the Queue is full. Let n be the maximum limit of the queue. If rear<n which means that the array is not full, then store the value at arr[rear] and increment the value for rear by 1 but if rear==n, then it is said to be an Overflow Condition as the array is full.
2. Dequeue: This is a removal of element from the Queue.  Deleting an element to the queue is performed only after checking whether the Queue is not null. Once the queue is empty, we simply return by saying that the Queue is empty. If rear>0, then the element at arr[front] can be removed from the queue and shift all the remaining element have to shifted to the left by one position in order for the Dequeue operation.
3. Front: Get the front element of the queue i.e., arr[front] if queue is not empty.
4. Display: To print all the elements of the queue. If the queue is non-empty, traverse and print all the elements from index front to rear. 

                            

                        

        

                            

From the above figure, the queue is implemented using Array. The queue has an array of integer values. In the second figure, Enqueue a data at the rear end and the value of rear is incremented by 1. In the third figure, Dequeue a data from the front and all the values are shifted from rear to front by 1 position.

The following is the C code for the implementation of Queue using Array:

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

#define CAPACITY 100
#define INT_MIN -1

int queue[CAPACITY];
unsigned int rear = 0;
unsigned int front = 0;
unsigned int size = 0;

//Check the overflow condition
int isFull()
{
    return(size==CAPACITY);
}

//Check the underflow condition
int isEmpty()
{
    return(size==0);
}

//Add element at rear of the queue
int enqueue(int data)
{
    if(isFull())
    {
        return 0;
    }
    if(rear > 0 || !isEmpty())
        rear = rear+1;
    size++;
    printf("=====Rear value is %d", rear);
    queue[rear] = data;
    return 1;
}

//Delete an element from front of the queue
int dequeue()
{
    int data;
    if(isEmpty())
    {
        return INT_MIN;
    }
    data = queue[front];
    size--;
    for(int i=0; i<size; i++)
    {
        queue[i] = queue[i+1];
    }
    rear--;
    return data;
}

//Get the front element from the Queue
int getFront()
{
    return(isEmpty())?INT_MIN:queue[front];
}

//Get the rear element from the Queue
int getRear()
{
    return(isEmpty())?INT_MIN:queue[rear];
}

//Print all the elements at the Queue
int printQueue()
{
    if(isEmpty())
    {
        return INT_MIN;
    }
    for (int i=0; i<size; i++)
    {
        printf("%d\t", queue[i]);
    }
    return 1;
}

int main()
{
    int ch, data;

    while(1)
    {
        printf("1.Enqueue\t2.Dequeue\t3.Print the Queue\n");
        printf("4.GetFront\t5.GetRear\t0.Exit\n");
        scanf("%d", &ch);

        switch(ch)
        {
            case 1:
                printf("Enter the data to enqueue : ");
                scanf("%d", &data);
                if(enqueue(data))
                    printf("Element is added to the queue");
                else
                    printf("Queue is full");
                break;

            case 2:
                data = dequeue();
                if(data == INT_MIN)
                    printf("Queue is empty");
                else
                    printf("Data dequeued is %d ", data);
                break;

            case 3:
                if(printQueue() == INT_MIN)
                    printf("Queue is empty");
                break;

            case 4:
                data = getFront();
                if(data == INT_MIN)
                    printf("Queue is empty");
                else
                    printf("The front data is %d", data);
                break;

            case 5:
                data = getRear();
                if(data == INT_MIN)
                    printf("Queue is empty");
                else
                    printf("The rear data is %d", data);
                break;

            case 0:
                printf("Exiting from the loop");
                exit(0);

            default:
                printf("Invalid choice, please input b/w (0-5).");
                break;
        }
        printf("\n");
    }
}

1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
1
Enter the data to enqueue : 2
=====Rear value is 0Element is added to the queue
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
1
Enter the data to enqueue : 4
=====Rear value is 1Element is added to the queue
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
3
2       4
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
4
The front data is 2
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
5
The rear data is 4
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
2
Data dequeued is 2
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
2
Data dequeued is 4
1.Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit
2
Queue is empty
1. Enqueue       2.Dequeue       3.Print the Queue
4.GetFront      5.GetRear       0.Exit

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

// A linked list (LL) node to store a queue entry
struct QNode {
	int key;
	struct QNode* next;
};

// The queue, front stores the front node of LL and rear stores the
// last node of LL
struct Queue {
	struct QNode *front, *rear;
};

// To create a new linked list node.
struct QNode* newNode(int k)
{
	struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
	temp->key = k;
	temp->next = NULL;
	return temp;
}

// To create a empty Queue
struct Queue* createQueue()
{
	struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
	q->front = q->rear = NULL;
	return q;
}

// To add a key k to q
void enQueue(struct Queue* q, int k)
{
	// Create a new List node
	struct QNode* temp = newNode(k);

	// If queue is empty, then new node is front and rear both
	if (q->rear == NULL) {
		q->front = q->rear = temp;
		return;
	}

	// Add the new node at the end of queue and change rear
	q->rear->next = temp;
	q->rear = temp;
}

// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
	// If queue is empty, return NULL.
	if (q->front == NULL)
		return NULL;

	// Store previous front and move front one node ahead
	struct QNode* temp = q->front;
	printf("Dequeued element is %d\n", temp->key);
	q->front = q->front->next;
	free(temp);

	// If front becomes NULL, then change rear also as NULL
	if (q->front == NULL)
		q->rear = NULL;
}

// Driver Program to test anove functions
int main()
{
	struct Queue* q = createQueue();
	enQueue(q, 15);
	enQueue(q, 25);
	deQueue(q);
	deQueue(q);
	enQueue(q, 35);
	enQueue(q, 45);
	enQueue(q, 55);
	deQueue(q);
	return 0;
}

Dequeued element is 15
Dequeued element is 25
Dequeued element is 35