What is Queue? How to implement queue in C? Explain with an example.

What is Queue?

A queue arranges elements in such a way that a new element gets added at the back and older existing elements gets removed from the front.

Queue of People

Queue operations

A new queue element always gets added in the back of the previously added element. The first added element stands at the front and later added elements are placed behind it one by one in the order they are added in the queue.

When comes to the removal of the queue element, it removes the last or oldest element or which is the first element in the queue. So the next to the first element becomes the first element in the queue. The first added element always be the first element to be removed. It is also known as FIFO or First In First Out in terms of design.

Queue example

Let us take a situation of a long row of a queue of people at the entrance. Now when the entrance will be open the first person who was waiting will be removed. Then every person will be shifted one position in the front. If some new person comes he/she has to stand at the back of the last person.

Queue with linked list

A queue can easily be visualized with the help of a linked list where nodes are added at tail and deleted from head or from the front. We take two node pointers named as head and tail in our queue data structure. Head will point to the front element of the queue and tail will point to the back of the queue. An addition should happen after tail and deletion should remove the element at head.

Enqueue and dequeue with linked list

Enqueue: Adding a new element in the queue is also known as the enqueue operation. queue_add() function implements the operation of enqueueing in the linked list. We allocate a node in dynamic memory. Then we assign a node value given by the user. Now we add this new node at the tail pointer of the list. The beginning of the queue happens where head = tail = null situation. Now the first node will be head = tail = first node. Thereafter every new node will be added after the tail (at tail->next) and the tail will move forward to the end.

Dequeue: Removing a node from the queue is known as dequeue operation. queue_remove() function implements the operation of dequeue in the linked list. Our head pointer is always pointing to the front node of the queue. We take this node and move to the next node. We make this next node the new head of this queue. We can delete this old head and free up the memory.

Queue using linked list

Queue implementation with linked list


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

typedef struct _node
{
  int value;
  struct _node * next;
}node_t;

typedef struct _queue_t
{
  node_t * head;
  node_t * tail;
}queue_t;

void queue_add(queue_t *queue, int value)
{
  node_t * new_node = NULL;
  new_node = (node_t *)malloc(sizeof(node_t));
  if(new_node == NULL)
  {
    printf("Terminating: no more memory left! ");
    exit(-1);
    return;
  }
  new_node->value = value;
  new_node->next = NULL;
  if(queue->head == NULL)
  {
    queue->head = new_node;
    queue->tail = new_node;
  }
  else
  {
    queue->tail->next = new_node;
    queue->tail = new_node;

  }
  printf("node(0x%p) value = %d ", new_node, new_node->value);
  return;

}
void queue_remove(queue_t *queue)
{
  node_t * temp;
  if(queue->head == NULL)
  {
    printf("Queue is empty! ");
    return;
  }
  else
  {
    temp = queue->head;
    queue->head = queue->head->next;
    printf("Deleted [%p] = %d ", temp, temp->value);
    free(temp);
    return;
  }
}
void queue_printall(queue_t *queue)
{
  node_t * temp;
  if(queue->head == NULL)
  {
    printf("Queue is empty! ");
    return;
  }
  temp = queue->head;
  while(temp != NULL)
  {
    printf("node(0x%p) value = %d ", temp, temp->value);
    temp = temp->next;
  }
}
void queue_removeall(queue_t *queue)
{
  node_t * temp = NULL;
  node_t * temp2 = NULL;
  temp = queue->head;
  while(temp != NULL)
  {

    printf("deleting node(0x%p) value = %d ",
            temp,
            temp->value);
    temp2 = temp;
    temp = temp->next;
    free(temp2);
  }
}
void queue_init(queue_t *queue)
{
  queue->head = NULL;
  queue->tail = NULL;

}
int main(int argc, char* argv[])
{
  queue_t queue;
  char action[10];
  int node_val;
  
  queue_init(&queue);
  
  printf("Queue example using linked list\n");
  printf("Add a new element [add]\n"
           "Delete a new element [del]\n"
           "Print queue [print]\n"
           "Exit [exit]\n");
  while(1)
  {
    printf("Action: ");
    gets(action);
    if(strcmp(action, "add") == 0)
    {
        printf("Enter a number :");
        scanf("%d", &node_val);
        queue_add(&queue, node_val);

    }
    else if(strcmp(action, "del") == 0)
    {
        queue_remove(&queue);
    }
    else if(strcmp(action, "print") == 0)
    {
       queue_printall(&queue);
    }
    else if(strcmp(action, "exit") == 0)
    {
       break;
    }

  }
  queue_removeall(&queue);
  return 0;
}

Queue implementation output

Queue example using linked list
Add a new element [add]
Delete a new element [del]
Print queue [print]
Exit [exit]
Action: add
Enter a number :1
node(0x0x7ff008d00000) value = 1
Action: Action: add
Enter a number :2
node(0x0x7ff008e00000) value = 2
Action: Action: add
Enter a number :3
node(0x0x7ff008f00000) value = 3
Action: Action: print
node(0x0x7ff008d00000) value = 1
node(0x0x7ff008e00000) value = 2
node(0x0x7ff008f00000) value = 3
Action: del
Deleted [0x7ff008d00000] = 1
Action: print
node(0x0x7ff008e00000) value = 2
node(0x0x7ff008f00000) value = 3
Action: del
Deleted [0x7ff008e00000] = 2
Action: print
node(0x0x7ff008f00000) value = 3
Action: del
Deleted [0x7ff008f00000] = 3
Action: print
Queue is empty!
Action: del
Queue is empty!
Action: add 
Enter a number :1
node(0x0x7ff009800000) value = 1
Action: Action: add
Enter a number :2
node(0x0x7ff008c00630) value = 2
Action: Action: exit
deleting node(0x0x7ff009800000) value = 1
deleting node(0x0x7ff008c00630) value = 2

Queue in C with array

The queue data structure can be implemented using a fixed array in C. Queue using array does not require dynamic memory allocation at runtime. This is good for systems where memory is limited by design. Embedded systems and real-time systems with low memory footprint systems may require implementing a queue using an array.

We have defined our queue data structure with a pointer to the array. We can allocate a dynamic array or we can use a global array of integers. There is a member to hold the max number of elements in the queue. There is also a member element to hold the number of elements in the queue.

Enqueue and dequeue with array

Enqueue: queue_add() function implements the operation of enqueuing in the array. The queue should start with count member as zero. Now we take the input from the user and place it in the current count position. We shift the count to next i.e. increment the counter. This way count will reach to the max value. At this point, queue will be full and no more addition is not possible. Designing a queue with an array imposes this limitation. Linked list does not have this limitation.

Dequeue: queue_remove() function implements the operation of dequeue in the queue. The count variable tells us how many elements are present in the queue. A value of zero in count indicates the queue is empty. So dequeue of any element in an empty queue is not possible. Now array index zero element is the front element in the queue when this queue is having one or more elements. During this time we take out the element[0] and shift all other elements one position ahead in the front. This way dequeuing happens. We also need to decrement the counter since one element has been reduced.

Queue implementation with array

/* queue.c Queue using array in C */

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

typedef struct _queue_t
{
  int *elements;
  int count;
  int max;
}queue_t;

int queue_add(queue_t *queue, int value)
{

  if(queue->count >= queue->max)
  {
    printf("Queue is full! ");
    return -1;
  }
  queue->elements[queue->count] = value;
  queue->count++;
  printf("Element #%d = %d added ", queue->count-1, value);
  return queue->count-1;

}
int queue_remove(queue_t *queue)
{
  int index, value;
  if(queue->count <= 0)
  {
    printf("Queue is empty! ");
    return -1;
  }
  
  value = queue->elements[0];
  printf("Element #0 = %d removed ", value);
  for (index = 0; index < queue->count; index++)
  {
    queue->elements[index] = queue->elements[index+1];
  }
  
  queue->count--;

  return queue->count;

}
void queue_print(queue_t *queue)
{
  int index, value;
  if(queue->count <= 0)
  {
    printf("Queue is empty! ");
    return;
  }
  printf("Queue elements ");
  for (index = 0; index < queue->count; index++)
  {
    printf("Element #%d : %d ", index, queue->elements[index]);
  }
}
void queue_init(queue_t *queue, int max)
{
  queue->max = 0;
  queue->count = 0;
  queue->elements = (int *)malloc(sizeof(int)*max);
  if(queue->elements == NULL)
  {
    printf("queue_init: memory allocation error ");
    return;
  }
  printf("queue_init: max queue length %d ", max);
  queue->max = max;

}
void queue_cleanup(queue_t *queue)
{
  queue->max = 0;
  queue->count = 0;
  free(queue->elements);

}
int main(int argc, char* argv[])
{
  queue_t queue;
  char input[10];
  int value;

   printf("Queue example using C "
           "Queue menu actions "
           "Add a new element [add] "
           "Delete a new element [del] "
           "Print queue [print] "
           "Exit [exit] "
           " "
           "Enter length of this queue :");
  scanf("%d", &value);
  queue_init(&queue, value);
  
  while(1)
  {
    printf("Action: ");
    fflush(stdin);
    gets(input);
    if (strcmp(input, "add") == 0)
    {
        printf("Enter a number :");
        scanf("%d", &value);
        queue_add(&queue, value);

    }
    else if(strcmp(input, "del") == 0)
    {
        queue_remove(&queue);
    }
    else if(strcmp(input, "print") == 0)
    {
         queue_print(&queue);
    }
        else if(strcmp(input, "exit") == 0)
    {
         break;
    }

  }
  queue_cleanup(&queue);
  return 0;
}

Queue implementation output

Queue example using C
Queue menu actions
Add a new element [add]
Delete a new element [del]
Print queue [print]
Exit [exit]

Enter length of this queue :3
queue_init: max queue length 3

Action: Action: print
Queue is empty!
Action: del
Queue is empty!
Action: add
Enter a number :1
Element #0 = 1 added
Action: Action: print
Queue elements
Element #0 : 1
Action: add
Enter a number :2
Element #1 = 2 added
Action: Action: add
Enter a number :3
Element #2 = 3 added
Action: Action: print
Queue elements
Element #0 : 1
Element #1 : 2
Element #2 : 3
Action: add
Enter a number :4
Queue is full!
Action: Action: del
Element #0 = 1 removed
Action: print
Queue elements
Element #0 : 2
Element #1 : 3
Action: del
Element #0 = 2 removed
Action: print
Queue elements
Element #0 : 3
Action: del
Element #0 = 3 removed
Action: print
Queue is empty!
Action: exit

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions