Queue (Array implementation)

A queue is a sequential storage structure that permits access only at the two ends of the sequence. We refer to the ends of the sequence as the front and rear.

A queue inserts new elements at the rear and removes elements from the front of the sequence.

You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come / first-served), ordering.

The difference between stack and queue is in removing. In stack we remove the item the most recently added; in queue we remove the item the least recently added.

---

---

Operations on Queue:

Enqueue: In a queue data structure, enQueue() is a function used to insert a new element into the queue. In a queue, the new element is always inserted at rear position.

The enQueue() function takes one integer value as parameter and inserts that value into the queue.

We can use the following steps to insert an element into the queue: • 1) Check whether queue is FULL. (rear == SIZE-1) • 2) If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function. • 3) If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.

deQueue: In a queue data structure, deQueue() is a function used to delete an element from the queue. In a queue, the element is always deleted from front position.

The deQueue() function does not take any value as parameter.

We can use the following steps to delete an element from the queue: • 1) Check whether queue is EMPTY. (front == rear) • 2) If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function. • 3) If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).

display:

We can use the following steps to display the elements of a queue: • 1) Check whether queue is EMPTY. (front == rear) • 2) If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function. • 3) If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'. • 4) Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is equal to rear (i <= rear) Front: Get the front item from queue. Rear: Get the last item from queue.

---

Implementation of queue using C:

#include <stdio.h>
 
#define MAX 50
 
void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
    int choice;
    while (1)
    {
        printf("1.Insert element to queue \n");
        printf("2.Delete element from queue \n");
        printf("3.Display all elements of queue \n");
        printf("4.Quit \n");
        printf("Enter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:
            insert();
            break;
            case 2:
            delete();
            break;
            case 3:
            display();
            break;
            case 4:
            exit(1);
            default:
            printf("Wrong choice \n");
        } 
    } 
} 
 
void insert()
{
    int add_item;
    if (rear == MAX - 1)
    printf("Queue Overflow \n");
    else
    {
        if (front == - 1)
            front = 0;
        printf("Insert the element in queue : ");
        scanf("%d", &add_item);
        rear = rear + 1;
        queue_array[rear] = add_item;
    }
} 
 
void delete()
{
    if (front == - 1 || front > rear)
    {
        printf("Queue Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from queue is : %d\n", queue_array[front]);
        front = front + 1;
    }
} 
 
void display()
{
    int i;
    if (front == - 1)
        printf("Queue is empty \n");
    else
    {
        printf("Queue is : \n");
        for (i = front; i <= rear; i++)
            printf("%d ", queue_array[i]);
        printf("\n");
    }
}

Output:
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 1
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 2
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 3
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 4
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 1
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is :
2 3 4
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 4

---

Miscellaneous:

Time complexity of enQueue: O(1)

Time complexity of deQueue: O(n)

---

We will discuss Linked list implementation of Queue later.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Follow Programmers Door for more.

#programming #blog #queue #array