Implementation & Application of Queue using Array | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

Queue implementation using Array

For the implementation of queue, we need to initialize two pointers i.e. front and rear, we insert an element from the rear and remove the element from the front, and if we increment the rear and front pointers we may occur error, Due to this, the front pointer may reach the end.

The solution to the above problem is to increase the front and rear pointers in a circular manner.

Enqueue Operation / Insertion

• First, check if the queue is full or not.
• For the first element, set the FRONT pointer to 0.
• Increment the REAR index by 1.
• Add the new element in the position which was pointed by REAR.

Dequeue Operation / Remove

• First, check if the queue is empty or not.
• Return the value which was pointed by FRONT.
• Increment the FRONT index by 1.
• For the last element, reset the values of FRONT and REAR to -1.

Code:

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

struct Queue {

    int front, rear, size;

    unsigned capacity;

    int* array;

};

struct Queue* createQueue(unsigned capacity)

{

    struct Queue* queue = (struct Queue*)malloc(

        sizeof(struct Queue));

    queue->capacity = capacity;

    queue->front = queue->size = 0; 

    queue->rear = capacity - 1;

    queue->array = (int*)malloc(

        queue->capacity * sizeof(int));

    return queue;

} 

int isFull(struct Queue* queue)

{

    return (queue->size == queue->capacity);

} 

int isEmpty(struct Queue* queue)

{

    return (queue->size == 0);

} 

void enqueue(struct Queue* queue, int item)

{

    if (isFull(queue))

        return;

    queue->rear = (queue->rear + 1)

                % queue->capacity;

    queue->array[queue->rear] = item;

    queue->size = queue->size + 1;

    printf("%d enqueued to queue\n", item);

} 

int dequeue(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    int item = queue->array[queue->front];

    queue->front = (queue->front + 1)

                % queue->capacity;

    queue->size = queue->size - 1;

    return item;

} 

int front(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->front];

} 

int rear(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->rear];

} 

int main()

{

    struct Queue* queue = createQueue(1000); 

    enqueue(queue, 1);

    enqueue(queue, 2);

    enqueue(queue, 3);

    enqueue(queue, 4); 

    printf("%d dequeued from queue\n\n",

        dequeue(queue)); 

    printf("Front item is %d\n", front(queue));

    printf("Rear item is %d\n", rear(queue)); 

    return 0;

}

</stdlib.h></stdio.h></limits.h>

Time complexity

• Enqueue: O(1)
• Dequeue: O(1)
• Front: O(1)
• Rear: O(1)

Space complexity
O(N) where N is the size of the array.

Applications of queue

• Applied as buffers on playing music in the mp3 players or CD players.
• Applied on handling the interruption in the operating system.
• Applied to add a song at the end of the playlist.
• Applied as the waiting queue for using the single shared resources like CPU, Printers, or Disk.
• Applied to the chat application when someone sends messages to us and we don’t have an internet connection then the messages are stored in the server of the chat application