Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Basic Queue Operations in Data Structure

Last Updated on June 8, 2023 by Mayank Dham

In this post, we’ll talk about what a queue is and how it works. The queue is one of the most used data structures. The most helpful data structure in programming is a queue. The individual who joins the queue first receives the first ticket, similar to the queue for tickets outside a movie theatre. Let’s go further into queues and fundamental 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.In conclusion, understanding basic queue operations is essential for effectively implementing and utilizing queues in data structures. Queues provide a straightforward approach to managing elements in a First-In-First-Out (FIFO) manner. The main operations associated with queues are enqueue (adding elements to the rear of the queue) and dequeue (removing elements from the front of the queue). Additionally, we have explored other frequently asked questions (FAQs) related to basic queue operations to provide further clarity on the topic.

Frequently Asked Questions (FAQs) related to Basic Queue Operations:

Q1. What is a queue in data structure?
A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle. It represents a collection of elements where new elements are added to the rear and existing elements are removed from the front.

Q2. What are the basic operations performed on a queue?
The basic operations performed on a queue are:
Enqueue: Adds an element to the rear of the queue.
Dequeue: Removes an element from the front of the queue.
IsEmpty: Checks if the queue is empty.
IsFull: Checks if the queue is full (applies to fixed-size queues).
Front: Retrieves the element at the front of the queue without removing it.

Q3. How is a queue different from a stack?
Queues and stacks are both linear data structures, but they differ in their principle of access. A queue follows the FIFO principle, while a stack follows the LIFO (Last-In-First-Out) principle. In a stack, the last element added is the first one to be removed, whereas in a queue, the first element added is the first one to be removed.

Q4. What is the time complexity of enqueue and dequeue operations in a queue?
The time complexity of enqueue and dequeue operations in a standard queue implementation is O(1) (constant time). It means that the time taken to perform these operations does not depend on the number of elements present in the queue.

Q5. Can a queue be implemented using an array?
Yes, a queue can be implemented using an array. In such an implementation, the rear of the queue is associated with the end of the array, and the front is associated with the beginning. However, it is important to handle cases of overflow (when the queue is full) and underflow (when the queue is empty) properly.

Leave a Reply

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