Queue Implementation in Data Structures
Queue Implementation in Data Structure: An Overview
Are you trying to learn about queue in data structure? If so, this article is for you. Queues are important data structures used in programming that provide insight and efficiency for projects involving a lot of work. In this article, we'll discuss what a queue is, its characteristics, queue program in data structure, queue operations in data structure, and application usage including some examples. We'll also cover many of the popular queue operations such as enqueueing, dequeuing, managing front/rear elements, and peek methods for quick inspection or removal from the back of the line!
What is Queue in data structure?
In computer science, the queue is a fundamental data structure that helps manage elements in a particular order. Similar to a queue of people waiting in line, the queue data structure operates on a first-in, first-out (FIFO) basis. Using FIFO, a queue arranges elements in the order of their addition and removal. The oldest object gets taken out of the front and moved to the back. It is essential for accurate data handling across a range of applications.
Implementation of Queue in Data Structure
An array, stack, or linked list can be used to implement a queue. Using an array to implement a queue is the simplest method. The queue's head (FRONT) and tail (REAR) initially point to the array's first index (beginning the index of the array at 0). The head stays at the first index as we continue to add elements to the queue, but the tail keeps moving forward and always pointing to the spot where the subsequent element will be added.
Types of Queue in data structure
- Simple Queue in data structure: In a simple queue, elements are inserted at the rear and removed from the front. It follows the FIFO (First In First Out) order.
- Circular Queue in data structure: A circular queue in data structure is similar to a simple queue, but the last element is connected to the first element, creating a circular structure. This allows for efficient use of memory, as the queue can be reused without shifting the elements.
- Priority Queue in data structure: A priority queue is a queue where each element has a priority assigned to it. The element with the highest priority is removed first. This is useful in situations where certain elements need to be processed before others.
- Deque (Double-Ended Queue) in data structure: A deque is a queue where elements can be added or removed from both the front and rear of the queue. This allows for efficient insertion and removal of elements at both ends.
Properties of queue in data structure
- Enqueue: Adding an item to the back of the queue.
- Dequeue: Removing an item from the front of the queue.
- Peek: Examining the item at the front of the queue without removing it.
- IsEmpty: Checking if the queue is empty.
- Size: Determining the number of items in the queue.
- Overflow: Occurs when trying to enqueue an item to a full queue.
- Underflow: This occurs when trying to dequeue an item from an empty queue.
Basic queue operations
Insertion operation: enqueue()
The enqueue() operation is used to insert an element at the back of a queue. It is also commonly referred to as "push" or "insert".
Algorithm
1 − START
2 – Check if the queue is full.
3 − If the queue is full, produce an overflow error and exit.
4 − If the queue is not full, increment the rear pointer to point to the next empty space.
5 − Add a data element to the queue location, where the rear is pointing.
6 − return success.
Example
class Queue:
def __init__(self):
self.queue = list()
def __str__(self):
return str(self.queue)
def addtoqueue(self,data):
# Insert method to add element
if data not in self.queue:
self.queue.insert(0,data)
return True
return False
q = Queue()
q.addtoqueue("36")
q.addtoqueue("24")
q.addtoqueue("48")
q.addtoqueue("12")
q.addtoqueue("66")
print("Queue:")
print(q)
import java.util.ArrayList;
import java.util.List;
class Queue {
private List<String> queue = new ArrayList<>();
public void addtoqueue(String data) {
// Insert method to add element
if (!queue.contains(data)) {
queue.add(0, data);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("Queue: ");
for (String element : queue) {
sb.append(element).append(" ");
}
return sb.toString();
}
}
public class Main {
public static void main(String[] args) {
Queue q = new Queue();
q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66");
System.out.println(q);
}
}
#include <iostream>
#include <list>
class Queue {
private:
std::list<std::string> queue;
public:
void addtoqueue(const std::string &data) {
// Insert method to add element
if (std::find(queue.begin(), queue.end(), data) == queue.end()) {
queue.push_front(data);
}
}
friend std::ostream &operator<<(std::ostream &os, const Queue &q) {
os << "Queue: ";
for (const std::string &element : q.queue) {
os << element << " ";
}
return os;
}
};
int main() {
Queue q;
q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66");
std::cout << q << std::endl;
return 0;
}
Explanation
The queue defined in this example uses a list to implement the fundamental queue data structure. After the addition of elements to the queue, the queue's contents are printed.
Output
Queue: 66 12 48 24 36 Deletion Operation: dequeue()
The dequeue() operation is used to remove and return the element at the front of a queue data structure. In other words, it removes the oldest element in the queue that has been waiting for the longest time.
Algorithm
1 – START
2 − Check if the queue is empty.
3 − If the queue is empty, produce an underflow error and exit.
4 − If the queue is not empty, access the data where the front is pointing.
5 − Increment the front pointer to point to the next available data element.
6 − Return success.
7 – END
Example
class Queue:
def __init__(self):
self.queue = list()
def __str__(self):
return str(self.queue)
def addtoqueue(self,data):
# Insert method to add element
if data not in self.queue:
self.queue.insert(0,data)
return True
return False
def removefromqueue(self):
if len(self.queue)>0:
return self.queue.pop()
return ("Queue is empty")
q = Queue()
q.addtoqueue("36")
q.addtoqueue("24")
q.addtoqueue("48")
q.addtoqueue("12")
q.addtoqueue("66")
print("Queue:")
print(q)
print("Element deleted from queue: ",q.removefromqueue())
class Queue {
private LinkedList<String> queue = new LinkedList<>();
public void addtoqueue(String data) {
// Insert method to add element
if (!queue.contains(data)) {
queue.addFirst(data);
}
} @Override
public String toString() {
return "Queue: " + queue.toString();
} public String removefromqueue() {
if (!queue.isEmpty()) {
return queue.removeLast();
}
return "Queue is empty";
}
}public class Main {
public static void main(String[] args) {
Queue q = new Queue(); q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66"); System.out.println("Queue:");
System.out.println(q);
System.out.println("Element deleted from queue: " + q.removefromqueue());
}
}
#include <iostream>
#include <list>class Queue {
private:
std::list<std::string> queue;public:
void addtoqueue(const std::string& data) {
// Insert method to add element
if (std::find(queue.begin(), queue.end(), data) == queue.end()) {
queue.push_front(data);
}
} friend std::ostream& operator<<(std::ostream& os, const Queue& q) {
os << "Queue: ";
for (const std::string& element : q.queue) {
os << element << " ";
}
return os;
} std::string removefromqueue() {
if (!queue.empty()) {
std::string lastElement = queue.back();
queue.pop_back();
return lastElement;
}
return "Queue is empty";
}
};int main() {
Queue q; q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66"); std::cout << "Queue:" << std::endl;
std::cout << q << std::endl;
std::cout << "Element deleted from queue: " << q.removefromqueue() << std::endl;
return 0;
}
Explanation
The queue Python class in this example uses a list to represent a queue data structure. It adds elements to the queue, prints the contents of the queue, and then removes and prints an element from the queue.
Output
Queue:
['66', '12', '48', '24', '36']
Element deleted from queue: 36The peek() Operation
In computer science, a queue is a data structure that follows the First-In-First-Out (FIFO) principle, which means that the first element that enters the queue will be the first to leave.
Algorithm
1 – START
2 – Return the element at the front of the queue
3 – END
Example
class Queue:
def __init__(self):
self.queue = list()
def __str__(self):
return str(self.queue)
def addtoqueue(self,data): # Insert method to add element
if data not in self.queue:
self.queue.insert(0,data)
return True
return False
def peek(self):
return self.queue[-1]q = Queue()
q.addtoqueue("36")
q.addtoqueue("24")
q.addtoqueue("48")
q.addtoqueue("12")
q.addtoqueue("66")
print("Queue:")
print(q)
print("The frontmost element of the queue: ",q.peek())
import java.util.LinkedList;
class Queue {
private LinkedList<String> queue = new LinkedList<>();
public void addtoqueue(String data) {
// Insert method to add element
if (!queue.contains(data)) {
queue.addFirst(data);
}
}
@Override
public String toString() {
return "Queue: " + queue.toString();
} public String peek() {
if (!queue.isEmpty()) {
return queue.getLast();
}
return "Queue is empty";
}
}
public class Main {
public static void main(String[] args) {
Queue q = new Queue();
q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66");
System.out.println("Queue:");
System.out.println(q);
System.out.println("The frontmost element of the queue: " + q.peek());
}
}
#include <iostream>
#include <list>class Queue {
private:
std::list<std::string> queue;public:
void addtoqueue(const std::string& data) {
// Insert method to add element
if (std::find(queue.begin(), queue.end(), data) == queue.end()) {
queue.push_front(data);
}
} std::string peek() {
if (!queue.empty()) {
return queue.front();
}
return "Queue is empty";
}
friend std::ostream& operator<<(std::ostream& os, const Queue& q) {
os << "Queue: ";
for (const std::string& element : q.queue) {
os << element << " ";
}
return os;
}
};int main() {
Queue q; q.addtoqueue("36");
q.addtoqueue("24");
q.addtoqueue("48");
q.addtoqueue("12");
q.addtoqueue("66"); std::cout << "Queue:" << std::endl;
std::cout << q << std::endl;
std::cout << "The frontmost element of the queue: " << q.peek() << std::endl;
return 0;
}
Explanation
In this example, a queue is defined as a list-based representation of a queue data structure. It adds elements to the queue, prints the contents of the queue, and then uses the "peek" method to get and print the queue's first entry.
Output
Queue:
['66', '12', '48', '24', '36']
The frontmost element of the queue: 36The isFull() Operation
The isFull() operation is a method commonly used in data structures that implement a queue to determine whether the queue is currently full and whether there is no more space to add new elements.
Algorithm
1 – START
2 – If the count of queue elements equals the queue size, return true
3 – Otherwise, return false
4 – END
Example
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def isFull():
return itemCount == MAX
def insert(data):
global rear, itemCount
if not isFull():
if rear == MAX - 1:
rear = -1
rear += 1
intArray[rear] = data
itemCount += 1
# insert 5 items
insert(3)
insert(5)
insert(9)
insert(1)
insert(12)
insert(15)
print("Queue:", end=' ')
for i in range(MAX):
print(intArray[i], end=' ')
print()
if isFull():
print("Queue is full!")
public class Queue {
private static final int MAX = 6;
private int[] intArray = new int[MAX];
private int front = 0;
private int rear = -1;
private int itemCount = 0; public boolean isFull() {
return itemCount == MAX;
} public void insert(int data) {
if (!isFull()) {
if (rear == MAX - 1) {
rear = -1;
}
rear += 1;
intArray[rear] = data;
itemCount += 1;
}
} public void printQueue() {
System.out.print("Queue: ");
for (int i = 0; i < MAX; i++) {
System.out.print(intArray[i] + " ");
}
System.out.println();
} public static void main(String[] args) {
Queue queue = new Queue(); queue.insert(3);
queue.insert(5);
queue.insert(9);
queue.insert(1);
queue.insert(12);
queue.insert(15); queue.printQueue();
if (queue.isFull()) {
System.out.println("Queue is full!");
}
}
}
#include <iostream>
class Queue {
private:
static const int MAX = 6;
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
public:
bool isFull() {
return itemCount == MAX;
}
void insert(int data) {
if (!isFull()) {
if (rear == MAX - 1) {
rear = -1;
}
rear += 1;
intArray[rear] = data;
itemCount += 1;
}
}
void printQueue() {
std::cout << "Queue: ";
for (int i = 0; i < MAX; i++) {
std::cout << intArray[i] << " ";
}
std::cout << std::endl;
}
};
int main() {
Queue queue;
queue.insert(3);
queue.insert(5);
queue.insert(9);
queue.insert(1);
queue.insert(12);
queue.insert(15);
queue.printQueue();
if (queue.isFull()) {
std::cout << "Queue is full!" << std::endl;
}
return 0;
}
Explanation
The circular queue shown in this example has a maximum capacity of 6. It adds 5 things to the queue, determines whether it is full, and prints the contents of the queue along with a message if it is.
Output:
Queue: 3 5 9 1 12 15
Queue is full!The isEmpty() operation
The isEmpty() operation on a queue data structure is a method that returns a boolean value indicating whether the queue is empty or not. If the queue has no elements, the isEmpty() method returns true, otherwise, it returns false.
Algorithm
1 – START
2 – If the count of queue elements equals zero, return true
3 – Otherwise, return false
4 – END
Example
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def isEmpty():
return itemCount == 0
if __name__ == '__main__':
print("Queue: ", end="")
for i in range(MAX):
print(intArray[i], end=" ")
print()
if isEmpty():
print("Queue is Empty!")
public class Queue {
private static final int MAX = 6;
private int[] intArray = new int[MAX];
private int front = 0;
private int rear = -1;
private int itemCount = 0;
public boolean isEmpty() {
return itemCount == 0;
}
public static void main(String[] args) {
Queue queue = new Queue();
System.out.print("Queue: ");
for (int i = 0; i < MAX; i++) {
System.out.print(queue.intArray[i] + " ");
}
System.out.println();
if (queue.isEmpty()) {
System.out.println("Queue is Empty!");
}
}
}
#include <iostream>
class Queue {
private:
static const int MAX = 6;
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
public:
bool isEmpty() {
return itemCount == 0;
}
void printQueue() {
std::cout << "Queue: ";
for (int i = 0; i < MAX; i++) {
std::cout << intArray[i] << " ";
}
std::cout << std::endl;
}
};
int main() {
Queue queue; std::cout << "Queue: ";
for (int i = 0; i < Queue::MAX; i++) {
std::cout << queue.intArray[i] << " ";
}
std::cout << std::endl;
if (queue.isEmpty()) {
std::cout << "Queue is Empty!" << std::endl;
}
return 0;
}
Explanation
In this example, a list with a 6-item maximum size is used to start up an empty queue. It then determines whether the queue is empty & prints a message indicating that it is.
Output
Queue: 0 0 0 0 0 0
Queue is Empty!FIFO Principle of Queue
- The FIFO principle of queue is a fascinating concept that is widely used in computer science and programming.
- The term "FIFO" stands for "first in, first out," which means that the items or data that enter the queue first will be the first ones to come out.
- This principle is used in various scenarios such as job scheduling, process management, and packet switching, among others.
- It is an efficient system that ensures the order and fairness of how items are handled in a queue.
- With the help of this principle, a large number of tasks or processes can be managed smoothly without any hiccups.
- The FIFO principle of queue is undoubtedly an essential aspect of programming that plays a pivotal role in optimizing system performance.
Advantages of queue in data structure
- Efficient data processing: A queue can be used to efficiently process data in the order it was received. For example, in a computer system, a queue can be used to schedule processes in the order they were submitted.
- Resource management: A queue can be used to manage resources that are shared among multiple processes or threads. For example, a printer can use a queue to manage print jobs.
- Buffering: A queue can be used to buffer incoming data so that it can be processed at a later time. For example, a network device can use a queue to buffer incoming data packets before forwarding them to their destination.
- Synchronization: A queue can be used to synchronize multiple threads or processes. For example, a producer-consumer problem can be solved using a queue where the producer adds data to the queue, and the consumer removes data from the queue.
- Memory management: A queue can be used to manage memory by allocating and deallocating memory blocks in sequential order.
Disadvantages of queue in data structure
- Limited flexibility: Queues follow a strict First-In-First-Out (FIFO) order, meaning the element that enters first is the first one to be removed. This lack of flexibility can be a disadvantage in some use cases where other priorities or requirements must be considered.
- No random access: Unlike arrays or linked lists, queues do not allow random access to the elements. The user can only access the first element in the queue, and to access any other element, they need to remove all the elements that come before it. This can be a disadvantage when the user needs to access an element in the middle of the queue.
- Overhead: Queues require extra overhead to maintain the order of elements. Whenever an element is added or removed from the queue, all the other elements must be shifted accordingly, which can be time-consuming for large queues.
- Limited size: In some implementations, queues have a limited size, which can be a disadvantage when dealing with large amounts of data. Once the queue reaches its maximum size, it can no longer accept new elements.
- No search operation: Queues do not provide a search operation. The user cannot search for a specific element in the queue they can only remove the elements in the order they were added and hope to find the element they are looking for.
Complexity of Queue
| Data Structure | Time Complexity | Space Complexity |
| Average | Worst | Worst |
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Queue | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
FAQs
1. What is the queue in data structure and its application?
The first element added is the first to be withdrawn in a queue, which is a linear data structure that follows to the FIFO (First-In-First-Out) principle. It's often used for jobs like running a printer queue or serving requests on a web server.
2. What are the 4 types of queues?
Simple Queues, Circular Queues, Priority Queue, and Double-ended Queue (Deque) are the four different types of queues.
3. Is the queue a LIFO or FIFO?
A FIFO (First-In, First-Out) data structure is a queue.
4. How to implement a queue in data structure?
In a data structure, a queue can be implemented using arrays or linked lists. To handle the queue in an array-based approach, use two pointers—one for the front and one for the back. Each element in a linked list-based implementation maintains a reference to the element after it.
5. What are the three basic implementations of a queue?
There are three fundamental ways to implement a queue Implementation using arrays, Implementation based on linked lists, and Implementation of a circular queue.
Summary
As you can see, a queue in data structure offers many useful features and applications. It is essential to understand how it works and how to use it properly in order to take advantage of the potential power of its effectiveness. Queue data structures are useful for a variety of programming applications because they are flexible and efficient. Queues are a useful tool in your programming toolbox since knowing their use cases can improve your ability to design online applications, games, and more.
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
