Queues: Like Waiting in Line

Welcome! You learned about stacks (like a stack of plates). Now let’s learn about Queues - the opposite of stacks!

What is a Queue? (Real Life Analogy)

The Grocery Store Line

Imagine you’re at the grocery store. People join the line at the back and get served from the front.

• First person in line gets served first
• Last person in line gets served last
• No cutting in line!

That’s exactly how a queue works!

Queue Rules:

• First In, First Out (FIFO): The first thing you add is the first thing you remove
• Add to back, remove from front
• Like waiting in line at a store, bank, or restaurant

Queue Operations (Like Line Management)

The Basic Actions

// Our queue will hold integers (like customer numbers)
type Queue struct {
    customers []int  // Using a slice to store our customers
}

1. Enqueue: Add Customer to Back of Line

func (q *Queue) Enqueue(customer int) {
    // Add customer to the end of our slice (back of line)
    q.customers = append(q.customers, customer)
}

// Example: Customers joining the line
queue := &Queue{customers: []int{}}

queue.Enqueue(1)  // Line: [1]
queue.Enqueue(2)  // Line: [1, 2]
queue.Enqueue(3)  // Line: [1, 2, 3]

2. Dequeue: Serve Customer from Front of Line

func (q *Queue) Dequeue() (int, bool) {
    // Check if line is empty
    if len(q.customers) == 0 {
        return 0, false  // No customers waiting!
    }
    
    // Get the first customer
    firstCustomer := q.customers[0]
    
    // Remove them from line
    q.customers = q.customers[1:]
    
    return firstCustomer, true
}

// Example: Serving customers
customer, success := queue.Dequeue()  // Gets 1, Line now: [2, 3]
customer, success := queue.Dequeue()  // Gets 2, Line now: [3]
customer, success := queue.Dequeue()  // Gets 3, Line now: []

3. Peek: Check Who’s Next (Without Serving)

func (q *Queue) Peek() (int, bool) {
    if len(q.customers) == 0 {
        return 0, false
    }
    
    return q.customers[0], true
}

// Example: Checking next customer
nextCustomer, exists := queue.Peek()  // Sees 1, but doesn't remove them

4. Check if Line is Empty

func (q *Queue) IsEmpty() bool {
    return len(q.customers) == 0
}

// Example
if queue.IsEmpty() {
    fmt.Println("No customers waiting!")
}

5. Count People in Line

func (q *Queue) Size() int {
    return len(q.customers)
}

// Example
waiting := queue.Size()  // How many customers are waiting

Real Life Example: Print Queue

package main

import "fmt"

type PrintQueue struct {
    jobs []string  // Queue of print jobs
}

func NewPrintQueue() *PrintQueue {
    return &PrintQueue{
        jobs: []string{},
    }
}

func (pq *PrintQueue) AddJob(document string) {
    // Add job to back of queue
    pq.jobs = append(pq.jobs, document)
    fmt.Printf("Added print job: %s\n", document)
}

func (pq *PrintQueue) ProcessJob() string {
    if len(pq.jobs) == 0 {
        return "No jobs in queue!"
    }
    
    // Get first job
    job := pq.jobs[0]
    
    // Remove it from queue
    pq.jobs = pq.jobs[1:]
    
    fmt.Printf("Processing: %s\n", job)
    return job
}

func (pq *PrintQueue) ShowQueue() {
    if len(pq.jobs) == 0 {
        fmt.Println("Print queue is empty")
        return
    }
    
    fmt.Println("Print queue:")
    for i, job := range pq.jobs {
        status := "waiting"
        if i == 0 {
            status = "NEXT"
        }
        fmt.Printf("  %s: %s\n", status, job)
    }
}

func main() {
    printer := NewPrintQueue()
    
    printer.AddJob("Important Report.pdf")
    printer.AddJob("Homework.docx")
    printer.AddJob("Photo.jpg")
    
    printer.ShowQueue()
    
    printer.ProcessJob()  // Print Important Report.pdf
    printer.ProcessJob()  // Print Homework.docx
    
    printer.ShowQueue()
}

Output:

Added print job: Important Report.pdf
Added print job: Homework.docx
Added print job: Photo.jpg
Print queue:
  NEXT: Important Report.pdf
  waiting: Homework.docx
  waiting: Photo.jpg
Processing: Important Report.pdf
Processing: Homework.docx
Print queue:
  NEXT: Photo.jpg

Real Life Example: Customer Service

package main

import "fmt"

type CustomerService struct {
    tickets []string  // Queue of customer tickets
}

func NewCustomerService() *CustomerService {
    return &CustomerService{
        tickets: []string{},
    }
}

func (cs *CustomerService) NewTicket(customer string) {
    cs.tickets = append(cs.tickets, customer)
    position := len(cs.tickets)
    fmt.Printf("Ticket created for %s (position %d)\n", customer, position)
}

func (cs *CustomerService) ServeNext() string {
    if len(cs.tickets) == 0 {
        return "No customers waiting!"
    }
    
    customer := cs.tickets[0]
    cs.tickets = cs.tickets[1:]
    
    fmt.Printf("Now serving: %s\n", customer)
    return customer
}

func (cs *CustomerService) CheckPosition(customer string) int {
    for i, name := range cs.tickets {
        if name == customer {
            return i + 1  // Position in line (1-based)
        }
    }
    return -1  // Not in line
}

func main() {
    service := NewCustomerService()
    
    service.NewTicket("Alice")
    service.NewTicket("Bob")
    service.NewTicket("Charlie")
    
    fmt.Printf("Bob is at position: %d\n", service.CheckPosition("Bob"))
    
    service.ServeNext()  // Serve Alice
    service.ServeNext()  // Serve Bob
    
    fmt.Printf("Charlie is now at position: %d\n", service.CheckPosition("Charlie"))
}

Output:

Ticket created for Alice (position 1)
Ticket created for Bob (position 2)
Ticket created for Charlie (position 3)
Bob is at position: 2
Now serving: Alice
Now serving: Bob
Charlie is now at position: 1

Real Life Example: Breadth-First Search (BFS)

Queues are perfect for exploring things level by level:

package main

import "fmt"

// Simple graph represented as adjacency list
var graph = map[string][]string{
    "A": {"B", "C"},
    "B": {"A", "D", "E"},
    "C": {"A", "F"},
    "D": {"B"},
    "E": {"B", "F"},
    "F": {"C", "E"},
}

type Queue struct {
    items []string
}

func (q *Queue) Enqueue(item string) {
    q.items = append(q.items, item)
}

func (q *Queue) Dequeue() (string, bool) {
    if len(q.items) == 0 {
        return "", false
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item, true
}

func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}

func breadthFirstSearch(start string) []string {
    visited := make(map[string]bool)
    queue := &Queue{}
    result := []string{}
    
    // Start with the first node
    queue.Enqueue(start)
    visited[start] = true
    
    for !queue.IsEmpty() {
        // Get next node from queue
        current, _ := queue.Dequeue()
        result = append(result, current)
        
        // Add all unvisited neighbors to queue
        for _, neighbor := range graph[current] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue.Enqueue(neighbor)
            }
        }
    }
    
    return result
}

func main() {
    // Explore the graph starting from A
    path := breadthFirstSearch("A")
    fmt.Printf("BFS traversal: %v\n", path)
    // Output: [A B C D E F] - visits all nodes level by level
}

Queue Implementation Using Linked List

For better performance, we can implement queues using linked lists:

type Node struct {
    data string
    next *Node
}

type LinkedQueue struct {
    front *Node  // Front of line (where we dequeue)
    rear  *Node  // Back of line (where we enqueue)
    size  int
}

func (lq *LinkedQueue) Enqueue(data string) {
    newNode := &Node{data: data, next: nil}
    
    if lq.rear == nil {
        // Empty queue
        lq.front = newNode
        lq.rear = newNode
    } else {
        // Add to back
        lq.rear.next = newNode
        lq.rear = newNode
    }
    
    lq.size++
}

func (lq *LinkedQueue) Dequeue() (string, bool) {
    if lq.front == nil {
        return "", false
    }
    
    // Get data from front
    data := lq.front.data
    
    // Move front forward
    lq.front = lq.front.next
    
    // If queue is now empty
    if lq.front == nil {
        lq.rear = nil
    }
    
    lq.size--
    return data, true
}

func (lq *LinkedQueue) Peek() (string, bool) {
    if lq.front == nil {
        return "", false
    }
    return lq.front.data, true
}

func (lq *LinkedQueue) IsEmpty() bool {
    return lq.front == nil
}

func (lq *LinkedQueue) Size() int {
    return lq.size
}

Circular Queue (Fixed Size)

Sometimes you want a queue with a maximum size that wraps around:

type CircularQueue struct {
    items    []int
    front    int
    rear     int
    size     int
    capacity int
}

func NewCircularQueue(capacity int) *CircularQueue {
    return &CircularQueue{
        items:    make([]int, capacity),
        front:    -1,
        rear:     -1,
        size:     0,
        capacity: capacity,
    }
}

func (cq *CircularQueue) Enqueue(item int) bool {
    if cq.IsFull() {
        return false  // Queue is full!
    }
    
    if cq.front == -1 {
        cq.front = 0
    }
    
    // Move rear pointer (wrap around if needed)
    cq.rear = (cq.rear + 1) % cq.capacity
    cq.items[cq.rear] = item
    cq.size++
    
    return true
}

func (cq *CircularQueue) Dequeue() (int, bool) {
    if cq.IsEmpty() {
        return 0, false
    }
    
    item := cq.items[cq.front]
    
    if cq.front == cq.rear {
        // Queue is now empty
        cq.front = -1
        cq.rear = -1
    } else {
        // Move front pointer (wrap around if needed)
        cq.front = (cq.front + 1) % cq.capacity
    }
    
    cq.size--
    return item, true
}

func (cq *CircularQueue) IsEmpty() bool {
    return cq.size == 0
}

func (cq *CircularQueue) IsFull() bool {
    return cq.size == cq.capacity
}

Practice Time!

Exercise 1: Restaurant Waitlist

Create a restaurant waitlist system where:

• Parties join the waitlist
• Tables become available and serve the next party
• Show current waitlist
• Check wait time for a party

Exercise 2: Song Playlist Queue

Create a music player with:

• Add songs to playlist
• Play next song (removes from queue)
• Show upcoming songs
• Shuffle remaining songs

Exercise 3: Help Desk Ticket System

Create a help desk system where:

• Customers submit tickets
• Support agents work on tickets in order
• Show open tickets
• Mark tickets as resolved

Exercise 4: Level-Order Tree Traversal

Use a queue to traverse a tree level by level (breadth-first).

Exercise 5: Sliding Window Maximum

Find the maximum in each window of size k as you slide through an array.

When to Use Queues

Use queues when:

• You need FIFO (First In, First Out) behavior
• You’re processing tasks in the order they arrive
• You’re doing breadth-first search or traversal
• You’re managing waiting lines (customers, jobs, requests)
• You’re implementing buffers or pipelines

Don’t use queues when:

• You need LIFO behavior (use stacks instead)
• You need to access arbitrary elements quickly
• You need priority-based processing (use priority queues)

Stack vs Queue Comparison

What’s Next?

Great! You’ve learned both stacks and queues. Next, we’ll explore Trees - hierarchical data structures like family trees or folder structures!

Quick Quiz

1. What’s the difference between a stack and a queue?
2. What does FIFO mean?
3. Can you access the middle element of a queue directly?
4. Name three real-life examples of queues.
5. Why do queues use linked lists for better performance?

Remember: Queues are like waiting in line - first come, first served!