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.