Basic Queue Operations in Data Structure

In this article, we will discuss what is queue, and queue operations. One of the most well-liked data structures is the queue. In the programming world, a queue is the most useful data structure. It is comparable to the line for tickets outside a movie theater, where the person who joins the line first receives the first ticket. Let’s get into more detail about queues and basic queue operations.

What is Queue?

The First In First Out (FIFO) rule is used in queues; the first item entered is the first item exited.

Since 1 was retained in the queue above before 2, it is also the first item to be taken out of the queue. The FIFO principle is followed.

Enqueue and dequeue are programming phrases for adding and deleting items from a queue, respectively.

Any programming language, including C, C++, Java, Python, or C#, can be used to implement the queue because the specification is basically the same.

Basic Operations of Queue

The following operations are possible with a queue, which is an object (abstract data structure – ADT):

  • Enqueue: Insert an element at the end of the queue.
  • Dequeue: Simply remove an element from the front of the queue.
  • IsEmpty: Used to check if the queue is completely empty.
  • IsFull: Used to check if the queue is completely full.
  • Peek: Without removing it, obtain the value from the front of the queue.

peek()

This function is used to see the data at the front of the queue. The peek() function’s algorithm is as follows −

Algorithm

begin procedure peek
   return queue[front]
end procedure

C programming language implementation of the peek() function −

int peek() {
   return queue[front];
}

isfull()

We simply check for the rear pointer to reach at MAXSIZE to check that the queue is full because we are utilizing a single dimension array to create the queue. The algorithm will be different if we retain the queue as a circular linked list. The isfull() function’s algorithm −

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif

end procedure

C programming language implementation of the isfull() function −

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

isempty()

This function is used to check if a queue is empty. We can say that a queue is empty if no element is present in it. Also we can find a queue is empty if the front is less than min or front is greater than rear.

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif

end procedure

If the value of front is less than MIN or 0, it signifies that the queue is not yet initialized, hence empty.

C programming language implementation of the isempty() function −

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Enqueue Operation

Front and rear data pointers are kept in queues. As a result, compared to stack operations, its operations are more complex to implement.

To enqueue (insert) data into a queue, execute these instructions:

Step 1: Determine whether the queue is full.

Step 2: Produce an overflow error and quit if the queue is full.

Step 3: If the queue is not full, move the rear pointer forward to the next empty space.

Step 4: Where the rear is pointing, add the data element to the queue location.

Step 5: Return a success.

To prepare for any unforeseen circumstances, we may also check to verify if a queue has been initialized or not.

Algorithm for enqueue operation

procedure enqueue(data)      

   if queue is full
      return overflow
   endif

   rear ← rear + 1
   queue[rear] ← data
   return true

end procedure

C programming language implementation of the enqueue() function −

int enqueue(int data)      
   if(isfull())
      return 0;

   rear = rear + 1;
   queue[rear] = data;

   return 1;

Dequeue Operation

It takes two steps to access data from a queue: first, access the data where the front is pointing, and second, remove the data after access. The dequeue operation is carried out in the manner described below:

Step1: Check whether the queue is empty.

Step 2: If there is no one in the queue, generate an underflow error and exit.

Step 3: Access the information at the front of the queue if it is not empty.

Step 4: Increment the front pointer to the next element.

Step 5: Successful return.

Algorithm for dequeue operation

procedure dequeue

   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

C programming language implementation of the dequeue() function −

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Let’s combine and see the program having all the basic queue operations.

Queue Implementation in Python, Java, C, and C++

In Java and C++, queues are typically implemented using arrays. For Python, we make use of lists.

#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");
}
#include <iostream>
#define SIZE 5

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }

  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }

  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  void enQueue(int element) {
    if (isFull()) {
      cout << "Queue is full";
    } else {
      if (front == -1) front = 0;
      rear++;
      items[rear] = element;
      cout << endl
         << "Inserted " << element << endl;
    }
  }

  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "Queue is empty" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front++;
      }
      cout << endl
         << "Deleted -> " << element << endl;
      return (element);
    }
  }

  void display() {
    /* Function to display elements of Queue */
    int i;
    if (isEmpty()) {
      cout << endl
         << "Empty Queue" << endl;
    } else {
      cout << endl
         << "Front index-> " << front;
      cout << endl
         << "Items -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "Rear index-> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  //deQueue is not possible on empty queue
  q.deQueue();

  //enQueue 5 elements
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // 6th element can't be added to because the queue is full
  q.enQueue(6);

  q.display();

  //deQueue removes element entered first i.e. 1
  q.deQueue();

  //Now we have just 4 elements
  q.display();

  return 0;
}
class Queue {
  int SIZE = 5;
  int items[] = new int[SIZE];
  int front, rear;

  Queue() {
    front = -1;
    rear = -1;
  }

  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }

  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  void enQueue(int element) {
    if (isFull()) {
      System.out.println("Queue is full");
    } else {
      if (front == -1)
        front = 0;
      rear++;
      items[rear] = element;
      System.out.println("Inserted " + element);
    }
  }

  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front++;
      }
      System.out.println("Deleted -> " + element);
      return (element);
    }
  }

  void display() {
    /* Function to display elements of Queue */
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("\nFront index-> " + front);
      System.out.println("Items -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      System.out.println("\nRear index-> " + rear);
    }
  }

  public static void main(String[] args) {
    Queue q = new Queue();

    // deQueue is not possible on empty queue
    q.deQueue();

    // enQueue 5 elements
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // 6th element can't be added to because the queue is full
    q.enQueue(6);

    q.display();

    // deQueue removes element entered first i.e. 1
    q.deQueue();

    // Now we have just 4 elements
    q.display();

  }
}
class Queue:

    def __init__(self):
        self.queue = []

    # Add an element
    def enqueue(self, item):
        self.queue.append(item)

    # Remove an element
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    # Display  the queue
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)


q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

q.display()

q.dequeue()

print("After removing an element")
q.display()

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  

Conclusion
Hoping this article has explained what is queue and what are the basic queue operations. Queues are a very important topic in terms of data structures. Practice more and more to become an expert in data structures.

Leave a Reply

Your email address will not be published. Required fields are marked *