Algorithm
In a queue, elements are added at the rear (enqueue) and removed from the front (dequeue). This ensures that the oldest elements are processed first. The process of adding an element to the rear of the queue is called enqueue, and the process of removing an element from the front is called dequeue.
The basic operations of a queue include:
- Enqueue (Insert): Adding an element to the rear of the queue.
- Dequeue (Delete): Removing an element from the front of the queue.
- Front: Returning the element at the front of the queue without removing it.
- Rear: Returning the element at the rear of the queue without removing it.
- IsEmpty: Checking if the queue is empty.
- Size: Getting the number of elements in the queue.
Let's discuss these operations in more detail:
1. Enqueue (Insert):
- Description: Adds an element to the rear (end) of the queue.
- Implementation: Typically involves appending the element to the end of the queue.
2. Dequeue (Delete):
- Description: Removes the element from the front (beginning) of the queue.
- Implementation: Typically involves removing the element at the front of the queue. In some implementations, this may require shifting the remaining elements to fill the gap.
3. Front:
- Description: Returns the element at the front of the queue without removing it.
- Implementation: Simply retrieves the element at the front without modifying the queue.
4. Rear:
- Description: Returns the element at the rear of the queue without removing it.
- Implementation: Simply retrieves the element at the rear without modifying the queue.
5. IsEmpty:
- Description: Checks if the queue is empty.
- Implementation: Typically involves checking if the internal data structure representing the queue has no elements.
6. Size:
- Description: Returns the number of elements in the queue.
- Implementation: Typically involves returning the length or size of the internal data structure representing the queue.
Code Examples
#1 Queue Implementations in Python-Using Lists:
Code -
Python Programming
class QueueUsingList:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
else:
print("Queue is empty")
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Example Usage:
queue_list = QueueUsingList()
queue_list.enqueue(1)
queue_list.enqueue(2)
queue_list.enqueue(3)
print(queue_list.dequeue()) # Output: 1
print(queue_list.size()) # Output: 2
#2 Queue Implementations in Python-Using collections.deque:
Code -
Python Programming
from collections import deque
class QueueUsingDeque:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.popleft()
else:
print("Queue is empty")
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Example Usage:
queue_deque = QueueUsingDeque()
queue_deque.enqueue(1)
queue_deque.enqueue(2)
queue_deque.enqueue(3)
print(queue_deque.dequeue()) # Output: 1
print(queue_deque.size()) # Output: 2
#3 Queue Implementations in Java- Linked List Implementation:
Code -
Java Programming
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListQueueExample {
public static void main(String[] args) {
// Creating a linked list queue
Queue < String> linkedListQueue = new LinkedList<>();
// Enqueue elements
linkedListQueue.add("Element 1");
linkedListQueue.add("Element 2");
linkedListQueue.add("Element 3");
// Dequeue elements
while (!linkedListQueue.isEmpty()) {
System.out.println("Dequeued: " + linkedListQueue.poll());
}
}
}
#4 Queue Implementations in Java- Array Implementation:
Code -
Java Programming
import java.util.ArrayDeque;
import java.util.Queue;
public class ArrayQueueExample {
public static void main(String[] args) {
// Creating an array-based queue
Queue < String> arrayQueue = new ArrayDeque<>();
// Enqueue elements
arrayQueue.add("Element 1");
arrayQueue.add("Element 2");
arrayQueue.add("Element 3");
// Dequeue elements
while (!arrayQueue.isEmpty()) {
System.out.println("Dequeued: " + arrayQueue.poll());
}
}
}
#5 Queue Implementations in C - Using Arrays:
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
// Function to initialize a queue
void initializeQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return (queue->front == -1 && queue->rear == -1);
}
// Function to check if the queue is full
int isFull(struct Queue* queue) {
return (queue->rear == MAX_SIZE - 1);
}
// Function to enqueue an element
void enqueue(struct Queue* queue, int value) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue %d.\n", value);
return;
}
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
// Function to dequeue an element
int dequeue(struct Queue* queue) {
int dequeuedItem;
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1;
}
dequeuedItem = queue->items[queue->front];
if (queue->front == queue->rear) {
initializeQueue(queue);
} else {
queue->front++;
}
return dequeuedItem;
}
// Function to display the elements in the queue
void displayQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements: ");
for (int i = queue->front; i <= queue->rear; i++) {
printf("%d ", queue->items[i]);
}
printf("\n");
}
int main() {
struct Queue myQueue;
initializeQueue(&myQueue);
enqueue(&myQueue, 10);
enqueue(&myQueue, 20);
enqueue(&myQueue, 30);
displayQueue(&myQueue);
printf("Dequeued item: %d\n", dequeue(&myQueue));
displayQueue(&myQueue);
return 0;
}
#6 Queue Implementations in C - Using Linked Lists:
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
// Function to initialize a queue
void initializeQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return (queue->front == NULL);
}
// Function to enqueue an element
void enqueue(struct Queue* queue, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed. Cannot enqueue %d.\n", value);
return;
}
newNode->data = value;
newNode->next = NULL;
if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
// Function to dequeue an element
int dequeue(struct Queue* queue) {
int dequeuedItem;
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1;
}
struct Node* temp = queue->front;
dequeuedItem = temp->data;
if (queue->front == queue->rear) {
initializeQueue(queue);
} else {
queue->front = queue->front->next;
}
free(temp);
return dequeuedItem;
}
// Function to display the elements in the queue
void displayQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements: ");
struct Node* current = queue->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Queue myQueue;
initializeQueue(&myQueue);
enqueue(&myQueue, 10);
enqueue(&myQueue, 20);
enqueue(&myQueue, 30);
displayQueue(&myQueue);
printf("Dequeued item: %d\n", dequeue(&myQueue));
displayQueue(&myQueue);
return 0;
}
#7 Queue Implementations in C ++ : Using std::queue
Code -
C++ Programming
#include <iostream>
#include <queue>
int main() {
// Create a queue of integers
std::queue<int> myQueue;
// Enqueue elements
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
// Display front and back elements
std::cout << "Front element: " << myQueue.front() << std::endl;
std::cout << "Back element: " << myQueue.back() << std::endl;
// Dequeue elements
myQueue.pop();
// Display front and back elements after dequeue
std::cout << "Front element after dequeue: " << myQueue.front() << std::endl;
std::cout << "Back element after dequeue: " << myQueue.back() << std::endl;
// Check if the queue is empty
if (myQueue.empty()) {
std::cout << "Queue is empty." << std::endl;
} else {
std::cout << "Queue is not empty." << std::endl;
}
// Display the size of the queue
std::cout << "Size of the queue: " << myQueue.size() << std::endl;
return 0;
}
#8 Implementing a Queue using Arrays:
Code -
C++ Programming
#include <iostream>
class ArrayQueue {
private:
static const int maxSize = 100;
int arr[maxSize];
int front, rear;
public:
ArrayQueue() : front(-1), rear(-1) {}
bool isEmpty() {
return front == -1 && rear == -1;
}
bool isFull() {
return (rear + 1) % maxSize == front;
}
void enqueue(int data) {
if (isFull()) {
std::cout << "Queue is full. Cannot enqueue." << std::endl;
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % maxSize;
}
arr[rear] = data;
}
void dequeue() {
if (isEmpty()) {
std::cout << "Queue is empty. Cannot dequeue." << std::endl;
return;
}
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % maxSize;
}
}
int getFront() {
if (isEmpty()) {
std::cout << "Queue is empty. No front element." << std::endl;
return -1; // Or throw an exception
}
return arr[front];
}
};
int main() {
ArrayQueue myQueue;
myQueue.enqueue(10);
myQueue.enqueue(20);
myQueue.enqueue(30);
std::cout << "Front element: " << myQueue.getFront() << std::endl;
myQueue.dequeue();
std::cout << "Front element after dequeue: " << myQueue.getFront() << std::endl;
return 0;
}
Demonstration
Queue Data Structure-DevsEnv