Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Visualization
Interactive visualization for Queue
Queue follows FIFO (First In, First Out) principle
Size: 4 | Front: 5 | Rear: 1
Enqueue Operation
Adds element to the rear of the queue. O(1) time complexity.
Dequeue Operation
Removes and returns the front element. O(1) time complexity.
Front/Peek Operation
Returns the front element without removing it. O(1) time.
Interactive visualization with step-by-step execution
Implementation
1class Queue<T> {
2 private items: T[] = [];
3
4 enqueue(element: T): void {
5 this.items.push(element);
6 }
7
8 dequeue(): T | undefined {
9 return this.items.shift();
10 }
11
12 front(): T | undefined {
13 return this.items[0];
14 }
15
16 isEmpty(): boolean {
17 return this.items.length === 0;
18 }
19
20 size(): number {
21 return this.items.length;
22 }
23}Deep Dive
Theoretical Foundation
Queue follows FIFO (First-In-First-Out) principle where the first element added is the first to be removed. It supports two primary operations: enqueue (add element to rear) and dequeue (remove element from front). Additional operations include front/peek (view front element) and isEmpty. Queues can be implemented using arrays (circular queue to avoid shifting), linked lists, or two stacks. Circular queues use modular arithmetic to wrap around array indices. Time complexity is O(1) for all operations with proper implementation, space complexity is O(n). Queue overflow occurs when enqueueing to full queue, underflow when dequeueing from empty queue.
Complexity
Time
O(1)
O(1)
O(1)
Space
O(n)
Applications
Industry Use
CPU task scheduling in operating systems
Print job spooling in printer queues
Breadth-First Search (BFS) graph traversal
Buffer management in I/O operations
Handling requests in web servers
Call center phone queue systems
Keyboard buffer for keystroke processing
Producer-consumer problems in multithreading
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.
Heap (Priority Queue)
A complete binary tree data structure that satisfies the heap property: in a max heap, parent nodes are greater than or equal to children; in a min heap, parents are less than or equal to children. Heaps provide O(1) access to the maximum/minimum element and O(log n) insertion and deletion. They're typically implemented as arrays for efficiency and are the foundation of heap sort and priority queues.