In Computer Science, Queue is a Linear Data Structure, which is open from both ends unlike Stacks. In Queue data is inserted from one end known as the REAR end and deleted from the other end called FRONT end. Queue follow First In First Out property(FIFO), where the element inserted first is deleted first than the other elements.

Visualise a queue of people in-front of Movie-Tickets Booking counter. As soon as the person at the very first gets his ticket, he moves out of the queue, and similar approach is followed in Data Structure : Queue also.

As we learnt earlier that Queues are very much similar to Stacks, in means of operations that can be performed on them, the only difference lies in the approach they follow to delete the elements, i.e in Stacks - FILO where as in Queue - FIFO.

Implementing Queues

There are 2 methods of implementing Queues, either by Arrays or by Linked Lists.

Basic Operations on Queue

These basic operations are very much similar to Push and Pop operations that we performed on Stacks.

EnQueue - The process of adding elements in the Queue. It occurs from the REAR end. If the Queue gets completely filled, then that is known as OVERFLOW condition.

DeQueue - The process of removing/deleting the elements from the Queue, but here, the element which was inserted at the first would be removed first. It occurs at the FRONT end. If the Queue gets emptied then that condition is called UNDERFLOW.

Enqueue or Insertion Operation

To perform this operation we need to create a Enqueue() function, so that our code doesn't look messed up at the end.

Algorithm: Initially, both the TOP and REAR variables are initialised with NULL, as soon as we insert a new element the value of REAR and FRONT increments by 1. Indicating that 1 element is now present in the Queue, at index 1. Note at this point REAR and TOP have same value, as the First element that we inserted in the empty Queue, is also the last element. And then as we add more and more elements, only the value of REAR increases, as the First element is at its original position and only the index of the last element is changing as we insert more elements. But if the value of REAR becomes equal to the SIZE of Queue, then this condition is called Overflow.

INSERT (QUEUE, N, FRONT, REAR, ITEM)

{

If REAR == N then

Write OVERFLOW and Exit.

If FRONT == NULL, then

FRONT = 1 and REAR = 1.

Else

REAR = REAR + 1.

QUEUE [REAR] = ITEM.

Exit.

}

Program :

Array Implementation

#include <stdio.h>
#define SIZE 10
int front=-1, rear=-1;
int array[SIZE];

void enqueue(int item)
{
  if (rear == SIZE)   // Queue is full
    return;
  if(front == -1 && rear == -1){
    front++;
    rear++;
  }
  else
    rear++;
  array[rear] = item;
  printf("%d enqueued to queue.\n",item);
}

int main()
{
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(10);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(20);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(30);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(40);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(50);
  printf("Front = %d, Rear = %d\n",front,rear);
}

OUTPUT

Front = -1, Rear = -1
10 enqueued to queue.
Front = 0, Rear = 0
20 enqueued to queue.
Front = 0, Rear = 1
30 enqueued to queue.
Front = 0, Rear = 2
40 enqueued to queue.
Front = 0, Rear = 3

Linked List Implementation

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SIZE 10

struct node
{
    int data;
    struct node *next;
};
typedef struct node node;

struct queue
{
    int count;
    node *front;
    node *rear;
};
typedef struct queue queue;

void initialize(queue *q)
{
    q->count = 0;
    q->front = NULL;
    q->rear = NULL;
}

int isempty(queue *q)
{
    return (q->rear == NULL);
}

void enqueue(queue *q, int value)
{
    if (q->count < SIZE)
    {
        node *tmp;
        tmp = malloc(sizeof(node));
        tmp->data = value;
        tmp->next = NULL;
        if(!isempty(q))
        {
            q->rear->next = tmp;
            q->rear = tmp;
        }
        else
        {
            q->front = q->rear = tmp;
        }
        q->count++;
    }
    else
    {
        printf("OVERFLOW\n");
    }
}

void display(node *head)
{
    if(head == NULL)
    {
        printf("NULL\n");
    }
    else
    {
        printf("%d\n", head -> data);
        display(head->next);
    }
}

int main()
{
    queue *q;
    q = malloc(sizeof(queue));
    initialize(q);
    enqueue(q,10);
    enqueue(q,20);
    enqueue(q,30);
    printf("Your Queue is:\n");
    display(q->front);
    
    return 0;
}

OUTPUT

Your Queue is:
10
20
30
NULL

* malloc() function helps in Dynamic Memory Allocation. Learn more about Dynamic Memory Allocation at https://en.wikipedia.org/wiki/C_dynamic_memory_allocation

2. Dequeue or Deletion Operation

Algorithm: In the Dequeue() function, it is first of all checked whether there are elements in the Queue or is it a case of Under-Flow. Then the element at the FRONT index is stored in another variable, so that we can return it at the end, and after storing , we just need to increase the FRONT variable value by 1. Thus it will point to the next element, making that element, the first element of Queue.

DELETE (QUEUE, N, FRONT, REAR, ITEM)

If FRONT = NULL then

Write UNDERFLOW and Exit.

ITEM = QUEUE[FRONT].

If FRONT = REAR then

FRONT = NULL and REAR = NULL.

Else

FRONT = FRONT+1.

Return ITEM

Exit

Program :

Array Implementation
#include <stdio.h>
#define SIZE 10
int front=0, rear=0;
int array[SIZE];

void enqueue(int item)
{
  if (rear == SIZE)   // Queue is full
    return;
  if(front == -1 && rear == -1){
    front++;
    rear++;
  }
  else
    rear++;
  array[rear] = item;
  printf("%d enqueued to queue.\n",item);
}

int dequeue()
{
  if (front > rear)
  {
    printf("Queue is Empty.\n");
    return -1;
  }
  int item = array[front];
  front++;
  printf("%d dequeued from queue.\n",item);
  return item;
}

int main()
{
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(10);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(20);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(30);
  printf("Front = %d, Rear = %d\n",front,rear);
  enqueue(40);
  printf("Front = %d, Rear = %d\n",front,rear);

  dequeue();
  printf("Front = %d, Rear = %d\n",front,rear);
  dequeue();
  printf("Front = %d, Rear = %d\n",front,rear);
  dequeue();
  printf("Front = %d, Rear = %d\n",front,rear);
  dequeue();
  printf("Front = %d, Rear = %d\n",front,rear);
  dequeue();
  printf("Front = %d, Rear = %d\n",front,rear);

  enqueue(50);
  printf("Front = %d, Rear = %d\n",front,rear);
}

OUTPUT
Front = 0, Rear = 0
10 enqueued to queue.
Front = 1, Rear = 1
20 enqueued to queue.
Front = 1, Rear = 2
30 enqueued to queue.
Front = 1, Rear = 3
40 enqueued to queue.
Front = 1, Rear = 4
10 dequeued from queue.
Front = 2, Rear = 4
20 dequeued from queue.
Front = 3, Rear = 4
30 dequeued from queue.
Front = 4, Rear = 4
40 dequeued from queue.
Front = 5, Rear = 4
Queue is Empty.
Front = 5, Rear = 4
50 enqueued to queue.
Front = 5, Rear = 5
Linked List Implementation

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

typedef struct node {
  int data;
  struct node *next;
}node;

typedef struct linked_list {
  struct node *head;
  struct node *tail;
}queue;

node* new_node(int data) {
  node *z;
  z = malloc(sizeof(struct node));
  z->data = data;
  z->next = NULL;

  return z;
}


queue* new_queue() {
  queue *q = malloc(sizeof(queue));
  q->head = NULL;
  q->tail = NULL;

  return q;
}

void display(queue *q) {
  node *temp = q->head; 

  while(temp != NULL) { 
    printf("%d\t", temp->data);
    temp = temp->next;
  }

  printf("\n");
}

int is_empty(queue *q) {
  if(q->head == NULL)
    return 1;
  return 0;
}

void enqueue(queue *q, node *n) {
  if(is_empty(q)) {
    q->head = n;
    q->tail = n;
  }
  else {
    q->tail->next = n;
    q->tail = n;
  }
}

int dequeue(queue *q) {
  if(is_empty(q)) {
    printf("Underflow\n");
    return -1000;
  }
  else {
    int x = q->head->data;
    node *temp = q->head;
    q->head = q->head->next;
    free(temp);
    return x;
  }
}

int main() {
  queue *q = new_queue();

  node *a, *b, *c, *d;
  a = new_node(10);
  b = new_node(20);
  c = new_node(30);
  d = new_node(40);

  dequeue(q);
  enqueue(q, a);
  enqueue(q, b);
  enqueue(q, c);
  enqueue(q, d);

  display(q);
  dequeue(q);
  dequeue(q);
  dequeue(q);
  display(q);


  return 0;
}

OUTPUT

Underflow
10  20  30       40 

Implementing Queue in C

Implementing Queues

Basic Operations on Queue

Enqueue or Insertion Operation

Array Implementation

Linked List Implementation

2. Dequeue or Deletion Operation

Linked List Implementation

Contact Form