Queue Implementations

Relevant source files

• src/main/java/com/thealgorithms/ciphers/ECC.java
• src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java
• src/main/java/com/thealgorithms/datastructures/dynamicarray/DynamicArray.java
• src/main/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMap.java
• src/main/java/com/thealgorithms/datastructures/hashmap/hashing/Map.java
• src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java
• src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java
• src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java
• src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java
• src/main/java/com/thealgorithms/datastructures/trees/PrintTopViewofTree.java
• src/main/java/com/thealgorithms/maths/LeastCommonMultiple.java
• src/main/java/com/thealgorithms/maths/ParseInteger.java
• src/main/java/com/thealgorithms/searches/UnionFind.java
• src/test/java/com/thealgorithms/ciphers/ECCTest.java
• src/test/java/com/thealgorithms/datastructures/buffers/CircularBufferTest.java
• src/test/java/com/thealgorithms/datastructures/dynamicarray/DynamicArrayTest.java
• src/test/java/com/thealgorithms/datastructures/hashmap/hashing/LinearProbingHashMapTest.java
• src/test/java/com/thealgorithms/datastructures/hashmap/hashing/MapTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java
• src/test/java/com/thealgorithms/datastructures/queues/CircularQueueTest.java
• src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java
• src/test/java/com/thealgorithms/datastructures/queues/PriorityQueuesTest.java
• src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java
• src/test/java/com/thealgorithms/maths/LeastCommonMultipleTest.java
• src/test/java/com/thealgorithms/maths/PalindromeNumberTest.java
• src/test/java/com/thealgorithms/maths/ParseIntegerTest.java
• src/test/java/com/thealgorithms/searches/UnionFindTest.java

This document details the queue data structure implementations in The Algorithms Java repository. Queues are fundamental data structures that follow the First-In-First-Out (FIFO) principle, where elements are added at the rear and removed from the front. The repository offers multiple queue implementations with different underlying mechanisms and performance characteristics.

Overview of Queue Implementations

The repository provides several specialized queue implementations:

1. CircularQueue - An array-based implementation that efficiently utilizes space by wrapping around src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java25
2. LinkedQueue - A linked list-based implementation offering dynamic size allocation src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java6
3. PriorityQueue - A queue where elements are removed based on their value (priority) rather than just insertion order src/test/java/com/thealgorithms/datastructures/queues/PriorityQueuesTest.java10
4. QueueByTwoStacks - An implementation of a queue using two stacks src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java1
5. CircularBuffer - A specialized ring buffer often used for streaming or fixed-size history src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java14
6. LeftistHeap - A specialized priority queue that supports efficient merging of two heaps src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java23

Sources: src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java

Queue Operations

Operation	Description	CircularQueue	LinkedQueue	CircularBuffer
Enqueue	Add element to rear	enQueue(T value)	enqueue(T data)	put(Item item)
Dequeue	Remove element from front	deQueue()	dequeue()	get()
Peek	View front element	peek()	peekFront()	N/A
Size	Get number of elements	size()	size()	size.get()
IsEmpty	Check if queue is empty	isEmpty()	isEmpty()	isEmpty()

Sources: src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java55-137 src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java39-175 src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java42-94

CircularQueue Implementation

The CircularQueue implements a queue using a fixed-size array with circular wrapping behavior.

Internal Structure

The CircularQueue uses beginningOfQueue to track the front and topOfQueue to track the rear src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java27-28 Wrapping is handled via modulo: (topOfQueue + 1) % size src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java81

Sources: src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java25-48 src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java74-105

LinkedQueue Implementation

The LinkedQueue uses a dynamic node-based structure.

Internal Structure

It maintains a front pointer for removals and a rear pointer for insertions src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java21-22 It implements Iterable<T> src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java6 allowing traversal via an internal Iterator src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java138-158

Sources: src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java6-32 src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java49-85

Specialized Implementations

CircularBuffer

Unlike CircularQueue, the CircularBuffer allows overwriting the oldest data when the buffer is full src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java8-9 It uses AtomicInteger for thread-safe size tracking src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java18 and a helper CircularPointer class to manage indices src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java106-132

LeftistHeap (Priority Queue)

The LeftistHeap is a priority queue variant that maintains the "leftist property": the null-path length (npl) of the left child is at least as large as the npl of the right child src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java11-13

Key Functions:

• merge(Node a, Node b): The primary operation used for both insertion and deletion src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java81-113
• extractMin(): Removes the root and merges the left and right subtrees src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java129-137

Sources: src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java

Comparison of Implementations

Feature	CircularQueue	LinkedQueue	CircularBuffer	LeftistHeap
Capacity	Fixed src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java46	Dynamic src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java62	Fixed src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java31	Dynamic src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java121
Full Behavior	Throws Exception src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java76	Never Full	Overwrites src/main/java/com/thealgorithms/datastructures/buffers/CircularBuffer.java86-87	Never Full
Ordering	FIFO	FIFO	FIFO	Priority (Min)
Merge Efficiency	O(N)	O(1) (if tail known)	O(N)	O(log N) src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java13-14

Usage Examples

CircularBuffer Overwrite Behavior

Sources: src/test/java/com/thealgorithms/datastructures/buffers/CircularBufferTest.java37-49

LeftistHeap Merging

Sources: src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java36-56

QueueByTwoStacks

This implementation simulates a queue by using one stack for enqueuing and another for dequeuing, ensuring FIFO order through stack transfers. Sources: src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java1