The Concept of a Queue as a "First In, First Out" (FIFO) Data Structure
- A queue is a fundamental data structure that operates on the principle of First In, First Out (FIFO).
- This means that the first element added to the queue is the first one to be removed, much like a line of people waiting for service.
Core Operations of a Queue
- Enqueue: Adds an element to the back of the queue.
- Dequeue: Removes the element from the front of the queue.
- Front: Returns the element at the front without removing it.
- isEmpty: Checks if the queue is empty.
Implementing a Queue
- Array-based Queue: Fixed size, uses indices for front and rear.
- Linked List Queue: Dynamic, grows/shrinks as needed.
- Circular Queue: Optimized version of array queue; reuses empty spaces.
Python example (using lists):
queue = []
# Enqueue
queue.append("A")
# Dequeue
item = queue.pop(0)
# Peek
front = queue[0] if queue else NoneJava example (using Queue interface):
import java.util.LinkedList;
import java.util.Queue;
Queue<String> q = new LinkedList<>();
q.add("A"); // Enqueue
q.remove(); // Dequeue
q.peek(); // Front
q.isEmpty(); // Check emptyUse built-in queue libraries (like collections.deque in Python) for efficiency.
Using Python list.pop(0) → inefficient (O(n)) since it shifts all elements.
