C Queue

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

Introduction to queue data structure

A 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 the 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., the customer who first came 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 an 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;
}
Code language: C++ (cpp)

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;
}
Code language: C++ (cpp)

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

void enqueue(int *q,int *tail, int element)
{
    q[(*tail)++] = element;
}
Code language: C++ (cpp)

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)++];
}
Code language: C++ (cpp)

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;
}
Code language: C++ (cpp)

The following program demonstrates the queue data structure:

queue.h

/*
 * File   : queue.h
 * Author : learnc.net
 * 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
Code language: C++ (cpp)

queue.c

/*
 * File   : queue.c
 * Author : learnc.net
 * 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");
}
Code language: C++ (cpp)

main.c

/*
 * File   : main.c
 * Author : learnc.net
 * 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;
}
Code language: C++ (cpp)

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
Code language: CSS (css)

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