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 procedureC 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 procedureC 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 procedureIf 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 procedureC 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 procedureC 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.