Operations on Queue in Data Structures

A queue is a linear structure where operations are done in a specific sequence. Queues are abstract data structures that are comparable to Stacks. A queue, unlike a stack, is open on both ends. The one end is always used to input data (enqueue), whereas the other end is always used to delete data (dequeue). The queue employs the First-In-First-Out (FIFO) mechanism, which means that the data item placed first will be accessed first.

Any line of consumers for a resource where the consumer who arrived first gets serviced is an example of a queue. A single-lane one-way road, where the vehicle enters first and departs first, is another real-world example of a queue. Queues at ticket booths and bus stations are two more real-world examples. The distinction between stacks and queues is in the removal process. In a stack, we delete the most recently added item; in a queue, we remove the least recently added item.

Queue Data Structure Applications

A queue is utilized when items do not need to be handled immediately but rather in the First In First Out sequence.

This characteristic of queue makes it handy in the following instances.

• When a resource is shared by several customers, CPU scheduling and disc scheduling are two examples.
• When data is sent asynchronously between two processes (data is not always received at the same pace as it is sent), IO Buffers, pipelines, file IO, and so on are examples.

Representation of Queues

We access both ends of the queue for distinct purposes, as we now understand. The graphic below attempts to show queue representation as a data structure Queue Example

A queue, like a stack, may be implemented using Arrays, Linked-lists, Pointers, and Structures. We'll use a one-dimensional array to build queues to keep things simple.

Fundamental Operations

Queue operations may include initializing or establishing the queue, using it, and finally wiping it completely from memory. This section will attempt to comprehend the fundamental processes related to queues.

• enqueue() adds (stores) a queue item.
• dequeue() removes (allows access to) an item from the queue.

A few extra functions are necessary to make the queue action described above efficient. These are the

• peek() that retrieves the entry at the top of the queue without deleting it.
• isfull() determines whether the queue is full.
• isempty() determines whether the queue is empty.

In a queue, we always dequeue (or access) data referenced by the front pointer, and we use the rear pointer to enqueue (or store) data in the queue.

enqueue() function

To add anything to the tail of a queue or to add something to the tail of a queue. Queues keep two data pointers, one in front and one in the back. As a result, its operations are more complicated to implement than stacks'. To enqueue (insert) data into a queue, perform the following steps:

• Step 1 Determine whether the queue is full.
• Step 2: If the queue is full, generate an overflow error and depart.
• Step 3: Move the rear pointer to the next empty slot if the queue isn't full.
• Step 4: Add a data element to the queue location indicated by the back arrow.
• Return success in step 5.

Algorithm

procedure enqueue(data)     
   if queue is full
      return overflow
   endif
   rear ← rear + 1
   queue[rear] ← data
   return true
end procedure

dequeue() function

Getting data from the queue consists of two subtasks: accessing the data where the front is pointing and removing it after it has been accessed. To remove data from the queue, perform the following steps:

• Step 1 Determine whether or not the queue is empty.
• Step 2: If the queue is empty, generate an underflow error and quit.
• Step 3: If the queue is not empty, access the data indicated by the front arrow.
• Step 4: Move the front pointer to the next accessible data element.
• Step 5:Return Success

Algorithm

procedure dequeue
  
   if a queue is empty
      return underflow
   end if
   data = queue[front]
   front ← front + 1
   return true
end procedure

peek() function

Queue Interface's peek() function returns the element at the front of the container. It doesn't remove the element from the container. This function returns the queue's head.

Algorithm

begin procedure peek
   return queue[front]
end procedure

isfull() funtion

This function determines whether the queue is full by checking if the back pointer is reached at MAXSIZE. In the isFull() procedure, the following steps are taken.

Algorithm

begin procedure isfull
   if rear equals to MAXSIZE
      return true
   else
      return false
   endif  
end procedure

isempty() funtion

If the value of the front is less than MIN or 0, it indicates that the queue has not yet been established and hence is empty.

Algorithm

begin procedure isempty
   if the front is less than MIN  OR front is greater than the rear
      return true
   else
      return false
   endif
end procedure

Final Code

When we combine all of the above functions, we obtain the program shown below.

// Queue implementation in C
#include <stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main() {
  //deQueue is not possible on empty queue
  deQueue();
  //enQueue 5 elements
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);
  // 6th element can't be added to because the queue is full
  enQueue(6);
  display();
  //deQueue removes element entered first i.e. 1
  deQueue();
  //Now we have just 4 elements
  display();
  return 0;
}
void enQueue(int value) {
  if (rear == SIZE - 1)
    printf("\nQueue is Full!!");
  else {
    if (front == -1)
      front = 0;
    rear++;
    items[rear] = value;
    printf("\nInserted -> %d", value);
  }
}
void deQueue() {
  if (front == -1)
    printf("\nQueue is Empty!!");
  else {
    printf("\nDeleted : %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}
// Function to print the queue
void display() {
  if (rear == -1)
    printf("\nQueue is Empty!!!");
  else {
    int i;
    printf("\nQueue elements are:\n");
    for (i = front; i <= rear; i++)
      printf("%d  ", items[i]);
  }
  printf("\n");
}

Output

Queue is Empty!!
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Queue is Full!!
Queue elements are:
1  2  3  4  5 
Deleted: 1
Queue elements are:
2  3  4  5

A queue is an object used to manipulate an ordered collection of various data types. You've seen Enqueue(), Dequeue(), isFull(), isEmpty(), and Peek queue actions (). When the FCFS (First Come, First Serve) strategy is required in software development, it is advised to use a queue. They can also be used when data does not need synchronous transport.

Time Complexity

Enqueue(insertion)	O(1)
Dequeue(deletion)	O(1)
Front(Get front)	O(1)
Rear(Get Rear)	O(1)

Queue's Constraints

As seen in the figure below, the queue size has been decreased after some enqueuing and dequeuing.

And we can only add indices 0 and 1 once the queue has been reset (when all the elements have been dequeued).

If we can store extra components in the empty spaces (0 and 1) once REAR reaches the last index, we may utilize the empty spaces. This is accomplished by using a customized queue known as the circular queue.

Queues of Various Types

In programming, a queue is a useful data structure. It's comparable to the ticket line outside a movie theatre, where the first person to enter the line receives the first ticket.

Queues are classified into four types:

• Simple Queue

Insertion occurs at the back of a simple queue, while removal occurs at the front. It firmly adheres to the FIFO (First In, First Out) principle.

• Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

• Double Ended Queue

Entry and deletion of elements in a double-ended queue can be done from either the front or the back. As a result, it does not adhere to the FIFO (First In, First Out) principle.

• Circular Queue

A circular queue is an extended form of a conventional queue in which the final member is linked to the first. As a result, a circle-like structure is formed. It is also known as a 'Ring Buffer.'

In a regular Queue, we can input elements till the queue is full. However, once the queue is filled, we cannot insert the following element, even if there is a vacancy in front of it.

The last entry in a circular queue points to the initial element, forming a circular connection. The key advantage of a circular queue over a simple queue is that it uses less memory. We can put an element in the first place if the last position is full and the first position is vacant. In a basic queue, this action is not feasible.

The circular queue overcomes the standard queue's fundamental shortcoming. After a little insertion and deletion, there will be non-usable space in a regular queue.

How Does a Circular Queue Work?

A circular queue operates on the principle of circular incrimination. When we try to increment the pointer and reach the end of the queue, we restart from the beginning.

In this case, the circular increment is accomplished via modulo division with the queue size. In other words,

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Operations with Circular Queues

The circular queue works like this:

• two arrows REAR AND FRONT
• FRONT keeps track of the queue's initial element.
• REAR originally tracks the queue's final members;
• Initially, set the values of FRONT and REAR to -1.

Operation Enqueue

• Check to see if the queue is filled.
• Set the value of FRONT to 0 for the first element.
• Increase the REAR index by 1 in a cyclical fashion (i.e., if the rear reaches the end, next, it would be at the start of the queue).
• Place the new element in the location indicated by REAR.

Operation of Dequeue

• check to see whether the queue is empty
• FRONT's value should be returned.
• Raise the FRONT index by 1 in a circle.
• Reset the values of FRONT and REAR to -1 for the final element.

However, the check for full queue now includes a new case:

Case 1: FRONT = 0 and REAR = SIZE - 1.
FRONT = REAR + 1 in Case 2

Implementations of Circular Queues in C

Arrays are the most often used queue implementation. However, lists can also be used.

Code

// Circular Queue implementation in C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}
// Check if the queue is empty
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}
// Adding an element
void enQueue(int element) {
  if (isFull())
    printf("\n Queue is full!! \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\n Inserted -> %d", element);
  }
}
// Removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Queue is empty !! \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    }
    // Q has only one element, so we reset the
    // queue after dequeing it. ?
    else {
      front = (front + 1) % SIZE;
    }
    printf("\n Deleted element -> %d \n", element);
    return (element);
  }
}
// Display the queue
void display() {
  int i;
  if (isEmpty())
    printf(" \n Empty Queue\n");
  else {
    printf("\n Front -> %d ", front);
    printf("\n Items -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}
int main() {
  // Fails because front = -1
  deQueue();
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);
  // Fails to enqueue because front == 0 && rear == SIZE - 1
  enQueue(6);
  display();
  deQueue();
  display();
  enQueue(7);
  display();
  // Fails to enqueue because front == rear + 1
  enQueue(8);
  return 0;
}

Output

A queue is empty !!
 Inserted -> 1
 Inserted -> 2
 Inserted -> 3
 Inserted -> 4
 Inserted -> 5
 Queue is full!!
 Front -> 0
 Items -> 1 2 3 4 5
 Rear -> 4
 Deleted element -> 1
 Front -> 1
 Items -> 2 3 4 5
 Rear -> 4