Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we will take a look into how we can implement Queue data structure using array. We have explained all operations in depth along with implementations.

A Queue is a type of data structure used in programming, and like all data structures, it can used to store data. In computer science, a data structure is a format used to store, manage and organize data in an efficient manner; enabling faster and easier access to the stored data. Some examples of data structures in programming include arrays, trees, graphs, linked lists etc.

Queues are often categorized as abstract data types and linear data structures which follow the First In First Out (FIFO) principle for the storage and retrieval of data, in which the first element inserted from one end of the array called the REAR is removed from the other end called the FRONT.

Analogously, you could think of Queue as a queue of customers at a bank, waiting to withdraw or deposit cash. Usually in situations like that, the first person on the queue would first be attended to, by the cashier - in similitude with the "FIFO" mechanism.

Queues can be implemented using any of the three (3) data structures, namely;

Arrays
Linked Lists
Stacks

However, the scope of this article does not cover other kinds of implementation; only the implementation of the queue data structure using an array.

To define a queue using an array, we defined:

a variable named front (to store the position of the first element)
a variable named rear (to store the position of the last element)
array: an array to store elements of queue

int front = 0;
int rear = 0;
int arr[N]; // N is the size (can be made dynamic)

Operations In Queue

Common operations or function calls associated with the implementation of Queue are:

Enqueue: This operation adds element(s) to the queue (if the array is not full)
Dequeue: This operation removes element(s) from the queue (if the array is not empty).
Display: This operation prints out all the elements of the queue (if the array is not empty), starting from the front index to the rear.
Front: This operation prints out the first element of the queue (if the array is not empty).
Size: The operation prints the size of the queue that is the number of elements within the queue

We will go through each of the functions in detail and see how array can be used to implement them.

Enqueue

Enqueue operation is used to insert an element into the queue provided it is not full. Queue will be full when the rear reaches the last position of the array. This is taken care by the condition:

if rear == N
    queue is full
    cannot insert elements

If the queue is not full, we can insert elements by set the element at the index denoted by rear and then, increment rear. This is covered by:

if rear != N
    array[rear] = element
    ++ rear

The complete pseudocode for enqueue operation is as follows:

STEP 1: IF REAR == N 
   Return OVERFLOW
   Goto STEP 3

STEP 2: IF REAR != N
   Set ARR[REAR] = INTEGER
   INCREMENT REAR BY 1
   {END OF LOOP}

STEP 3: EXIT LOOP

Dequeue

In dequeue operation, we remove an element. In queue, we can only remove the element that was inserted first. This operation will fail if the queue is empty and it is denoted by the condition that front and rear are same (may not be 0).

if front == rear
    queue is empty

If the queue is not empty, we simply return the element at index front and increment the value of front.

if front != rear
    return array[front]
    ++ front

The complete pseudocode is as follows:

STEP 1: IF FRONT == REAR
        Return UNDERFLOW
        Goto STEP 2
        ELSE
        Return ARR[FRONT]
        INCREMENT FRONT BY 1

STEP 2: EXIT

Display

Printing all elements of the queue is simple as we need to traverse the array from index "front" to "rear" and print all elements. This is as follows:

for i from front to rear
    print array[i]

Size

To get the size of the queue, we can simply substract rear and front and the resulting value will be the size of the queue. This will be as follows:

size = rear - front

Utilizing all space

You will notice that after the certain number of operations (enqueue and dequeue), the queue may have some space left but it will still show that it is full. This is because we keep on incrementing front and never decrement it.

To tackle this, we need to reset front to 0 if:

rear == N-1 (at the end) but front != 0

This is the case when there is some space at the front but due to our algorithm, it will show the space is full. In this case, we will simply shift all elements such that it starts from index 0 and set front to 0 and rear to rear - previous value of front.

This is executed as follows:

if rear == N-1 and front != 0
    for i from 0 to rear - front
        array[i] = array[front + i]
    rear = rear - front
    front = 0

This test can be done during enqueue operation. If an element needs to be inserted and the queue is full, we can check if the front of queue is empty and if yes, we can use the above approach to first adjust the queue and then, insert the new element.

This will consume linear time O(N) but will make your queue implementation space efficient. Another alternative will be to use Circular queue which will have better time complexity O(1).

Let us go through some implementations as we have the complete idea of implementing queue using array.

In this article, I'd be making use of the C and Python programming languages respectively for my algorithms. But before we jump into algorithms, let's take a look into another interesting and vital concept in programming, which is the time complexity of an algorithm.

Time Complexity of an Algorithm

Time complexity of the operations are as follows:

Enqueue: O(1) time
Dequeue: O(1) time
Display: O(N) time
Size: O(1) time

If we utilize all the space of queue using the technique we illustrate, the time complexity will be as follows:

Enqueue: O(N) time (worst case), O(1) time (best case), O(1) time (average case)
Dequeue: O(1) time
Display: O(N) time
Size: O(1) time

Implementation of a Queue in C

To implement a queue data structure using arrays in C programming language, a one-dimensional array is declared with a constant size N, with two variables front and rear also declared; both of which are initialized to 0, signifying an empty array.

To insert (enqueue) an element, we check if the array is full (i.e. rear == N) or not (i.e. rear < N). If the array is full, it is said to be an overflow condition. Else, the element is added to the array, and rear is incremented.

To delete (dequeue) an element, we check if there's atleast one element in the array (i.e. rear > 0). If the array is empty, it is said to be an underflow condition. Else, the element at the front is deleted from the array, and front is incremented.

#include <stdio.h>
#define N 100

int front = 0;
int rear = 0;
int arr[N];
void Enqueue();
void Dequeue();
void Display();
void Front();

int main()
{
    int input;

    printf("Choose your request:\n");

    while(1)
    {
        printf("1. Enqueue\n");
        printf("2. Dequeue\n");
        printf("3. Display\n");
        printf("4. Front\n");
        printf("5. Exit\n");
        scanf("%d", &input);

        switch(input)
        {
            case 1:
                Enqueue();
                break;
            case 2:
                Dequeue();
                break;
            case 3:
                Display();
                break;
            case 4:
                Front();
                break;
            case 5:
                exit(1);
            default:
                printf("oops... no request\n");
        }
    }
}


// Enqueue function
void Enqueue()
{
    int item;

    if (rear == N)
    {
    printf("oops... it's an overflow\n\n");
    }
    else
    {
        if (front == 0)

        printf("Insert element: ");
        scanf("%d", &item);
        arr[rear] = item;
        rear = rear + 1;
    }
}

// Dequeue function
void Dequeue()
{
    if (front == rear)
    {
        printf("oops... it's an underflow\n\n");
    }
    else
    {
        printf("The element dequeued from the array is: %d\n\n", arr[front]);
        front = front + 1;
    }

    /* NB: No actual deletions are done in this function.  */
}

// Display function
void Display()
{
    if (front == rear)
    {
        printf("oops... empty array\n\n");
    }
    else
    {
        printf("displaying elements in array...\n\n");

        for (int i = front; i < rear; i++)
            printf("%d ", arr[i]);
    }
    printf("\n\n");
}

// Front function
void Front()
{
  int j = arr[front];
  
  if (front == rear)
  {
    printf("oops... empty array\n\n");
  }
  else
  {
    printf("%d\n\n", j);
  }
}

Implementation of a Queue in Python

Unlike most programming languages such as C, Java, C# etc., Python's implementation of an array is quite unique. When you hear people talk about arrays in Python, they are most likely talking about lists Which means, instead of enqueue() and dequeue() functions, we'd be making use of append() and pop(). The program below shows how queues are implemented in Python.

#empty array declaration
arr = []

#built-in list function that adds three elements to the array.
arr.append(1)
arr.append(2)
arr.append(3)

print("printing array...")
print(arr)

#built-in list function that removes elements from an array
print("removing two elements from array...")
arr.pop(0)
arr.pop(0)

print("printing the remaining element(s) in array...")
print(arr)

Applications of Queue Data Structure

Interrupt handling. Interrupts in real-time systems can be handled effectively using the "FIFO" mechanism.
Resource scheduling algorithmns in an operating system are written using Queue data structure.
Queues are used for asynchronous data transfer (Pipes, Buffers, File IO)

Question

What type of data structure is Queue?

Linear

Constant

Stack

Round

Queue is a known as an abstract or linear data structure.

Learn more:

Queue data structure by Gaurav Kumar Ponkiya
Dynamic Array by Mudit Garg
Implementing Stack using queues in two ways by Vaibhav Gupta
Implementing Queue using Linked Lists by Akshit Desai
Circular Queue data structure by Vedant Wakalkar
Lists in Python by Tanmayi Patibandla
List of Python topics by OpenGenus

With this article at OpenGenus, you will have the complete idea of implementing queue using array. Enjoy.

Queue using Array

Algorithms Data Structures queue