Queues - What Does Computing & Nigerian Petrol Stations Have in Common?
It's a typical day in Lagos, and word has gotten out that there might be fuel scarcity coming up. Within hours, a long line of cars forms at every filling station. Some drivers doze off in their cars, others stand in groups discussing the state of the nation, but everyone follows one simple rule - newcomers join at the back of the line.
Welcome to a perfect real-world example of a Queue data structure!
What is a Queue?
A Queue is a data structure that follows the First-In-First-Out (FIFO) principle. Like that fuel station line where Oga John (waiting since 4 AM) must be served first, the first element added to the queue will be the first one removed.
Let's implement a basic Queue in Go:
// Queue represents a thread-safe FIFO queue structure
type Queue struct {
items []interface{}
mu sync.Mutex // For thread safety
}
// NewQueue creates and returns a new empty queue
func NewQueue() *Queue {
return &Queue{
items: make([]interface{}, 0),
}
}
// Enqueue adds an item to the back of the queue
// Time Complexity: O(1)
func (q *Queue) Enqueue(item interface{}) {
q.mu.Lock()
defer q.mu.Unlock()
q.items = append(q.items, item)
}
// Dequeue removes and returns the front item
// Time Complexity: O(n) with slices, O(1) with linked lists
func (q *Queue) Dequeue() (interface{}, error) {
q.mu.Lock()
defer q.mu.Unlock()
if len(q.items) == 0 {
return nil, errors.New("queue is empty")
}
item := q.items[0]
q.items = q.items[1:]
return item, nil
}
// Peek returns the front item without removing it
func (q *Queue) Peek() (interface{}, error) {
q.mu.Lock()
defer q.mu.Unlock()
if len(q.items) == 0 {
return nil, errors.New("queue is empty")
}
return q.items[0], nil
}
// IsEmpty checks if the queue has no items
func (q *Queue) IsEmpty() bool {
return len(q.items) == 0
}
// Size returns the number of items in the queue
func (q *Queue) Size() int {
return len(q.items)
}
Queue Variations
1. Circular Queue
Perfect for fuel stations! When a car leaves the front, the space can be reused:
type CircularQueue struct {
items []interface{}
front int
rear int
size int
capacity int
}
2. Priority Queue
For emergency vehicles or VIP customers:
type PriorityQueue struct {
items []*PQItem
}
type PQItem struct {
value interface{}
priority int
}
Real-World Applications
1. Print Job Scheduling
When the office printer is handling multiple print jobs, it's just like cars lining up at a fuel pump - first come, first served!
type PrintJob struct {
documentName string
pages int
}
func demonstratePrinterQueue() error {
printerQueue := NewQueue()
// Add print jobs
printerQueue.Enqueue(PrintJob{"Quarterly_Report.pdf", 50})
printerQueue.Enqueue(PrintJob{"Team_Photo.jpg", 1})
// Process jobs with error handling
for !printerQueue.IsEmpty() {
job, err := printerQueue.Dequeue()
if err != nil {
return fmt.Errorf("printer queue error: %v", err)
}
printJob := job.(PrintJob)
fmt.Printf("Printing: %s (%d pages)\n",
printJob.documentName, printJob.pages)
}
return nil
}
2. Modern Fuel Station Management
Let's simulate how a modern fuel station might handle its queue of vehicles:
type VehicleRequest struct {
plateNumber string
fuelType string
litersNeeded float64
arrivalTime time.Time
}
type QueueStats struct {
averageWaitTime time.Duration
totalServed int
}
func demonstrateFuelQueue() (*QueueStats, error) {
fuelQueue := NewQueue()
stats := &QueueStats{}
// Process vehicles with wait time tracking
for !fuelQueue.IsEmpty() {
vehicle, err := fuelQueue.Dequeue()
if err != nil {
return nil, err
}
request := vehicle.(VehicleRequest)
waitTime := time.Since(request.arrivalTime)
stats.averageWaitTime += waitTime
stats.totalServed++
fmt.Printf("Serving: %s - Wait time: %v\n",
request.plateNumber, waitTime)
}
if stats.totalServed > 0 {
stats.averageWaitTime /= time.Duration(stats.totalServed)
}
return stats, nil
}
3. Message Buffering in Communication Systems
Just like how vehicles in a fuel queue move forward one at a time, message queues ensure orderly processing of data in communication systems:
type Message struct {
sender string
content string
timestamp time.Time
}
func demonstrateMessageBuffer() {
messageQueue := NewQueue()
// Messages arriving
messageQueue.Enqueue(Message{
sender: "System Alert",
content: "Low fuel warning at Pump 3",
timestamp: time.Now(),
})
messageQueue.Enqueue(Message{
sender: "Payment Gateway",
content: "Transaction successful for LAG-123-XY",
timestamp: time.Now(),
})
// Processing messages in order
fmt.Println("Processing system messages...")
for !messageQueue.IsEmpty() {
msg, _ := messageQueue.Dequeue()
message := msg.(Message)
fmt.Printf("From %s: %s\n", message.sender, message.content)
}
}
Common Pitfalls
Memory Leaks: Not properly removing references to dequeued items
Race Conditions: Forgetting thread safety in concurrent operations
Overflow/Underflow: Not checking queue bounds
Performance Issues: Using slices instead of linked lists for large queues
Limitations
Fixed-Size Queues: Must handle overflow scenarios
Memory Usage: Linear space complexity
Performance: Dequeue operations with slices are O(n)
Conclusion
Queues bring order to chaos, whether in computing or at fuel stations. They come in various forms (circular, priority, double-ended) and can be implemented using different underlying structures (arrays, linked lists) depending on your needs.
Remember: Like a well-managed fuel queue prevents chaos at the station, a well-implemented queue prevents chaos in your system!
Pro Tip: Next time you're in a queue, ponder whether it's implemented as a circular queue or if it needs priority queue features for those emergency vehicles! (But maybe keep the data structure jokes to yourself - the person behind you might not appreciate your technical humor under the hot Lagos sun).