C Queue

Summary: in this tutorial, you will learn how to implement the C queue data structure using array.

Introduction to queue data structure

Queue is a collection of objects that are added and removed based on the first-in first-out (FIFO) principle. It means that the first element added to the queue will be first one to be removed from the queue.

Don’t be confused a queue with a stack, because a stack works based on the last-in first-out (LIFO) principle.

A good example of a queue is a line of customers in front of a shop. A new addition to the queue made to the back of the queue, whereas removal from the queue i.e., customer is served happens in the front of the queue. This is called first-come first-served.

There are two main operations in a queue: enqueue and dequeue.

• Enqueue: inserts an element into the back of the queue.
• Dequeue: removes an element from the front of the queue.

C queue implementation

We can implement the queue data structure in C using array. We add an element to the back of the queue, whereas we remove an element from the front of the queue. Therefore we need two pointers: head and tail to track the front and the back of the queue.

The queue first is empty so we need to initialize the head and tail pointers:

void init(int *head, int *tail)
{
    *head = *tail = 0;
}

The queue is empty when the head and the tail pointers point to the same position:

int empty(int head, int tail)
{
    return head == tail;
}

Whenever we enqueue an element, we increase the tail pointer 1 position:

void enqueue(int *q,int *tail, int element)
{
    q[(*tail)++] = element;
}

When we dequeue an element, we increase the head pointer 1 position until the head pointer reaches the tail pointer i.e., the queue is empty.

int dequeue(int *q,int *head)
{
    return q[(*head)++];
}

The queue is full when the tail and the size of the queue are equal.

int full(int tail,const int size)
{
    return tail == size;
}

The following program demonstrates the queue data structure:

queue.h

/*
 * File   : queue.h
 * Author : zentut.com
 * Purpose: stack header file
 */
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

void init(int *head, int *tail);
void enqueue(int *q,int *tail, int element);
int dequeue(int *q,int *head);
int empty(int head,int tail);
int full(int tail,const int size);
void display(int *q,int head,int tail);
#endif // QUEUE_H_INCLUDED

queue.c

/*
 * File   : queue.c
 * Author : zentut.com
 * Purpose: stack header file
 */
/*
    initialize queue pointers
*/
void init(int *head, int *tail)
{
    *head = *tail = 0;
}

/*
   enqueue an element
   precondition: the queue is not full
*/
void enqueue(int *q,int *tail, int element)
{
    q[(*tail)++] = element;
}

/*
    dequeue an element
    precondition: queue is not empty
*/
int dequeue(int *q,int *head)
{
    return q[(*head)++];
}

/*
    return 1 if queue is full, otherwise return 0
*/
int full(int tail,const int size)
{
    return tail == size;
}

/*
  return 1 if the queue is empty, otherwise return 0
*/
int empty(int head, int tail)
{
    return tail == head;
}

/*
  display queue content
*/
void display(int *q,int head,int tail)
{
    int i = tail - 1;
    while(i >= head)
        printf("%d ",q[i--]);
    printf("\n");
}

main.c

/*
 * File   : main.c
 * Author : zentut.com
 * Purpose: queue program
 */
#include <stdio.h>
#include <stdlib.h>

#include "queue.h";

int main()
{
    const int SIZE = 5; /* queue's size */
    int head, tail, element;
    int queue[SIZE];

    init(&head,&tail);

    printf("--Enqueue elements--\n");
    /* push elements into stack */
    while(!full(tail,SIZE))
    {
        printf("Enter a number to enqueue:");
        scanf("%d",&element);

        enqueue(queue,&tail,element);

        display(queue,head,tail);
    }
    printf("Queue is full\n\n");

    printf("--Dequeue elements --\n");
    while(!empty(head,tail))
    {
        element = dequeue(queue,&head);
        printf("dequeue element %d \n",element);

        display(queue,head,tail);
    }
    printf("Queue is empty\n");
    return 0;
}

The following is the output of the program when we enqueue 1, 2, 3, 4, 5.

--Enqueue elements--
Enter a number to enqueue:1
1
Enter a number to enqueue:2
2 1
Enter a number to enqueue:3
3 2 1
Enter a number to enqueue:4
4 3 2 1
Enter a number to enqueue:5
5 4 3 2 1
Queue is full

--Dequeue elements --
dequeue element 1
5 4 3 2
dequeue element 2
5 4 3
dequeue element 3
5 4
dequeue element 4
5
dequeue element 5

Queue is empty

You can download the C queue implementation project in the following link.

In this tutorial, you have learned how to implement queue data structure in C using array.