Queue -- Middle Level¶

package main

import (
    "errors"
    "fmt"
)

type dequeNode struct {
    val        int
    prev, next *dequeNode
}

type Deque struct {
    front, rear *dequeNode
    size        int
}

func NewDeque() *Deque {
    return &Deque{}
}

func (d *Deque) AddFront(val int) {
    node := &dequeNode{val: val}
    if d.front == nil {
        d.front = node
        d.rear = node
    } else {
        node.next = d.front
        d.front.prev = node
        d.front = node
    }
    d.size++
}

func (d *Deque) AddRear(val int) {
    node := &dequeNode{val: val}
    if d.rear == nil {
        d.front = node
        d.rear = node
    } else {
        node.prev = d.rear
        d.rear.next = node
        d.rear = node
    }
    d.size++
}

func (d *Deque) RemoveFront() (int, error) {
    if d.size == 0 {
        return 0, errors.New("deque is empty")
    }
    val := d.front.val
    d.front = d.front.next
    if d.front != nil {
        d.front.prev = nil
    } else {
        d.rear = nil
    }
    d.size--
    return val, nil
}

func (d *Deque) RemoveRear() (int, error) {
    if d.size == 0 {
        return 0, errors.New("deque is empty")
    }
    val := d.rear.val
    d.rear = d.rear.prev
    if d.rear != nil {
        d.rear.next = nil
    } else {
        d.front = nil
    }
    d.size--
    return val, nil
}

func main() {
    d := NewDeque()
    d.AddRear(1)
    d.AddRear(2)
    d.AddFront(0)
    // Deque: 0, 1, 2

    v, _ := d.RemoveFront()
    fmt.Println("Front:", v) // 0
    v, _ = d.RemoveRear()
    fmt.Println("Rear:", v)  // 2
}

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap implements heap.Interface for a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func main() {
    h := &IntHeap{5, 3, 8, 1}
    heap.Init(h)

    heap.Push(h, 2)

    for h.Len() > 0 {
        fmt.Print(heap.Pop(h), " ") // 1 2 3 5 8
    }
    fmt.Println()
}

package main

import "fmt"

func bfs(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    visited[start] = true
    order := []int{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    return order
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 3, 4},
        2: {0, 4},
        3: {1},
        4: {1, 2},
    }
    fmt.Println(bfs(graph, 0)) // [0 1 2 3 4]
}

package main

import "fmt"

// slidingWindowMax returns the maximum in each window of size k.
func slidingWindowMax(nums []int, k int) []int {
    // deque stores indices, not values
    deque := []int{}
    result := []int{}

    for i := 0; i < len(nums); i++ {
        // Remove indices outside the window
        if len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        // Remove smaller elements from rear (they will never be the max)
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)

        // Window is fully formed starting at i >= k-1
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }
    return result
}

func main() {
    nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
    fmt.Println(slidingWindowMax(nums, 3)) // [3, 3, 5, 5, 6, 7]
}

package main

import (
    "fmt"
    "sync"
    "time"
)

func producer(ch chan<- int, id int, wg *sync.WaitGroup) {
    defer wg.Done()
    for i := 0; i < 5; i++ {
        val := id*100 + i
        ch <- val
        fmt.Printf("Producer %d: sent %d\n", id, val)
        time.Sleep(50 * time.Millisecond)
    }
}

func consumer(ch <-chan int, id int, wg *sync.WaitGroup) {
    defer wg.Done()
    for val := range ch {
        fmt.Printf("  Consumer %d: received %d\n", id, val)
        time.Sleep(100 * time.Millisecond)
    }
}

func main() {
    ch := make(chan int, 10) // buffered channel = queue with capacity 10
    var prodWg, consWg sync.WaitGroup

    // Start 2 producers
    for i := 0; i < 2; i++ {
        prodWg.Add(1)
        go producer(ch, i, &prodWg)
    }

    // Start 3 consumers
    for i := 0; i < 3; i++ {
        consWg.Add(1)
        go consumer(ch, i, &consWg)
    }

    prodWg.Wait()
    close(ch) // signal consumers that no more data is coming
    consWg.Wait()
    fmt.Println("All done.")
}