WikiGalaxy
Queue Structures
Introduction to Queues:
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed. Queues are used in various applications such as scheduling, buffering, and resource management.
// Queue Structure Diagram
[Front] -> [Data | Next] -> [Data | Next] -> [Rear]
Basic Operations:
The basic operations of a queue include enqueue (adding an element to the rear), dequeue (removing an element from the front), peek (viewing the front element), and checking if the queue is empty.
Example 1: Implementing a Queue using Arrays
import java.util.*;
class ArrayQueue {
int front, rear, size;
int capacity;
int array[];
public ArrayQueue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
boolean isFull() {
return (this.size == this.capacity);
}
boolean isEmpty() {
return (this.size == 0);
}
void enqueue(int item) {
if (isFull()) return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size++;
}
int dequeue() {
if (isEmpty()) return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size--;
return item;
}
}
Explanation:
This example demonstrates the implementation of a queue using an array. The queue supports basic operations like enqueue and dequeue while managing the circular nature of the array.
Example 2: Implementing a Queue using Linked List
import java.util.*;
class LinkedListQueue {
Node front, rear;
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public LinkedListQueue() {
this.front = this.rear = null;
}
void enqueue(int key) {
Node temp = new Node(key);
if (this.rear == null) {
this.front = this.rear = temp;
return;
}
this.rear.next = temp;
this.rear = temp;
}
Node dequeue() {
if (this.front == null) return null;
Node temp = this.front;
this.front = this.front.next;
if (this.front == null) this.rear = null;
return temp;
}
}
Explanation:
This example shows how a queue can be implemented using a linked list. Each node in the linked list represents an element in the queue, with pointers to the next node.
Example 3: Priority Queue
import java.util.*;
class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(15);
System.out.println(pq.peek());
System.out.println(pq.poll());
System.out.println(pq.poll());
}
}
Explanation:
A priority queue is a special type of queue where each element is associated with a priority. Elements are dequeued based on their priority rather than their order in the queue. The example uses Java's built-in PriorityQueue class.
Example 4: Double-ended Queue (Deque)
import java.util.*;
class DequeExample {
public static void main(String[] args) {
Deque deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(3);
System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());
}
}
Explanation:
A deque is a type of queue where elements can be added or removed from both ends. This example demonstrates the use of Java's Deque interface implemented by LinkedList.
Example 5: Circular Queue
import java.util.*;
class CircularQueue {
int front, rear, size;
int capacity;
int array[];
public CircularQueue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
boolean isFull() {
return (this.size == this.capacity);
}
boolean isEmpty() {
return (this.size == 0);
}
void enqueue(int item) {
if (isFull()) return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size++;
}
int dequeue() {
if (isEmpty()) return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size--;
return item;
}
}
Explanation:
A circular queue is a linear data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This example illustrates the circular nature of the queue, allowing efficient use of space.
