A queue is a linear data structure that follows the First In First Out principle, meaning the first element added is the first one to be removed. It operates like a real-world queue or line where people are served in the order they arrive.
The fundamental operations of a queue are enqueue which adds an element to the rear end with O of 1 time complexity, dequeue which removes and returns the element from the front in O of 1 time, front or peek which returns the front element without removing it, rear which returns the last element, isEmpty which checks if the queue is empty, and size which returns the number of elements. Operations happen at two different ends unlike stacks where all operations occur at one end.
Queues can be implemented using arrays which provide fast access but have fixed size, using linked lists which offer dynamic size and efficient enqueue and dequeue operations, or using circular arrays which efficiently utilize space by wrapping around when reaching the end.
The key difference between stack and queue is the order of element removal. Stacks use Last In First Out where the most recently added element is removed first, like a stack of books. Queues use First In First Out where the oldest element is removed first, like a waiting line. Stacks have one access point called top, while queues have two points called front and rear.
Use cases for stacks include function call management in recursion, undo and redo operations, expression evaluation and syntax parsing, backtracking in algorithms, and browser back button functionality. Use cases for queues include CPU and disk scheduling in operating systems, handling asynchronous data transfer like IO buffers and pipes, breadth-first search traversal in graphs and trees, printer job scheduling where documents are printed in order received, and call center systems where calls are answered in order they arrive.
Example code
// Queue implementation using linked list
class Queue {
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
private Node front, rear;
void enqueue(int value) {
Node newNode = new Node(value);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
int dequeue() {
if (front == null) {
System.out.println("Queue is empty");
return -1;
}
int value = front.data;
front = front.next;
if (front == null) rear = null;
return value;
}
int peek() {
if (front == null) return -1;
return front.data;
}
boolean isEmpty() {
return front == null;
}
}
// Stack vs Queue comparison
Stack: push(1), push(2), push(3), pop() -> 3 (LIFO)
Queue: enqueue(1), enqueue(2), enqueue(3), dequeue() -> 1 (FIFO)