Queues

// Package queue is Module 5: queues (FIFO) and deques.
//
// The naive Go queue — append to enqueue, q = q[1:] to dequeue — works but
// never reuses the front of its backing array. A ring buffer fixes that, and
// it's what you'll build first.
package queue

// RingQueue is a FIFO queue on a circular buffer.
//
//	buf:  [ . . C D E . . ]      head = 2, size = 3
//	             ^ head
//
// The element at logical position i lives at buf[(head+i) % len(buf)].
type RingQueue[T any] struct {
	buf  []T
	head int // index of the front element
	size int // number of elements stored
}

// NewRingQueue returns an empty queue with the given starting capacity (min 1).
func NewRingQueue[T any](capacity int) *RingQueue[T] {
	if capacity < 1 {
		capacity = 1
	}
	return &RingQueue[T]{buf: make([]T, capacity)}
}

// Len returns the number of elements.
func (q *RingQueue[T]) Len() int { return q.size }

// Cap returns the current buffer size.
func (q *RingQueue[T]) Cap() int { return len(q.buf) }

// StackQueue is a FIFO queue built from two LIFO stacks (slices).
// Enqueue pushes onto in; Dequeue pops from out, refilling out from in
// only when out is empty.
type StackQueue[T any] struct {
	in  []T
	out []T
}

// Len returns the number of elements.
func (q *StackQueue[T]) Len() int { return len(q.in) + len(q.out) }

// RecentCounter counts requests in a sliding 3000 ms window.
type RecentCounter struct {
	times []int // timestamps still inside the window, oldest first
}

package queue

import (
	"slices"
	"testing"
)

func TestRingQueueBasics(t *testing.T) {
	q := NewRingQueue[int](4)
	for i := 1; i <= 3; i++ {
		q.Enqueue(i)
	}
	if v, ok := q.Peek(); !ok || v != 1 {
		t.Fatalf("Peek() = (%d, %v), want (1, true)", v, ok)
	}
	for _, want := range []int{1, 2, 3} {
		if v, ok := q.Dequeue(); !ok || v != want {
			t.Fatalf("Dequeue() = (%d, %v), want (%d, true)", v, ok, want)
		}
	}
	if _, ok := q.Dequeue(); ok {
		t.Error("Dequeue() on empty queue should return ok=false")
	}
	if q.Len() != 0 {
		t.Errorf("Len() = %d, want 0", q.Len())
	}
}

func TestRingQueueWrapAndGrow(t *testing.T) {
	q := NewRingQueue[int](4)
	// Move head into the middle of the buffer so the next writes wrap around.
	for i := 0; i < 3; i++ {
		q.Enqueue(-1)
	}
	for i := 0; i < 3; i++ {
		q.Dequeue()
	}
	for i := 1; i <= 4; i++ {
		q.Enqueue(i) // fills the buffer exactly, wrapped
	}
	if q.Cap() != 4 {
		t.Errorf("Cap() = %d, want 4 (no growth needed yet — are you reusing slots?)", q.Cap())
	}
	for i := 5; i <= 20; i++ {
		q.Enqueue(i) // forces growth while wrapped
	}
	if q.Len() != 20 {
		t.Fatalf("Len() = %d, want 20", q.Len())
	}
	for want := 1; want <= 20; want++ {
		if v, ok := q.Dequeue(); !ok || v != want {
			t.Fatalf("Dequeue() = (%d, %v), want (%d, true) — order broken after growth", v, ok, want)
		}
	}
}

func TestStackQueue(t *testing.T) {
	var q StackQueue[string]
	q.Enqueue("a")
	q.Enqueue("b")
	if v, _ := q.Dequeue(); v != "a" {
		t.Fatalf("Dequeue() = %q, want a", v)
	}
	q.Enqueue("c")
	q.Enqueue("d")
	for _, want := range []string{"b", "c", "d"} {
		if v, ok := q.Dequeue(); !ok || v != want {
			t.Fatalf("Dequeue() = (%q, %v), want (%q, true)", v, ok, want)
		}
	}
	if _, ok := q.Dequeue(); ok {
		t.Error("Dequeue() on empty queue should return ok=false")
	}
}

func TestJosephus(t *testing.T) {
	for _, tc := range []struct{ n, k, want int }{
		{7, 3, 4},
		{5, 2, 3},
		{1, 5, 1},
		{6, 1, 6},
		{41, 3, 31},
	} {
		if got := Josephus(tc.n, tc.k); got != tc.want {
			t.Errorf("Josephus(%d, %d) = %d, want %d", tc.n, tc.k, got, tc.want)
		}
	}
}

func TestSlidingWindowMax(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		k    int
		want []int
	}{
		{[]int{1, 3, -1, -3, 5, 3, 6, 7}, 3, []int{3, 3, 5, 5, 6, 7}},
		{[]int{9, 8, 7, 6}, 2, []int{9, 8, 7}},
		{[]int{1, 2, 3}, 1, []int{1, 2, 3}},
		{[]int{4, 2, 12, 3}, 4, []int{12}},
		{[]int{1}, 2, nil},
	} {
		if got := SlidingWindowMax(tc.in, tc.k); !slices.Equal(got, tc.want) {
			t.Errorf("SlidingWindowMax(%v, %d) = %v, want %v", tc.in, tc.k, got, tc.want)
		}
	}
}

func TestRecentCounter(t *testing.T) {
	var c RecentCounter
	for _, step := range []struct{ t, want int }{
		{1, 1}, {100, 2}, {3001, 3}, {3002, 3}, {7000, 1},
	} {
		if got := c.Ping(step.t); got != step.want {
			t.Fatalf("Ping(%d) = %d, want %d", step.t, got, step.want)
		}
	}
}

//go:build solutions

package queue

func (q *RingQueue[T]) Enqueue(v T) {
	if q.size == len(q.buf) {
		// Unwrap into a buffer twice the size, front element at index 0.
		bigger := make([]T, len(q.buf)*2)
		for i := 0; i < q.size; i++ {
			bigger[i] = q.buf[(q.head+i)%len(q.buf)]
		}
		q.buf, q.head = bigger, 0
	}
	q.buf[(q.head+q.size)%len(q.buf)] = v
	q.size++
}

func (q *RingQueue[T]) Dequeue() (T, bool) {
	var zero T
	if q.size == 0 {
		return zero, false
	}
	v := q.buf[q.head]
	q.buf[q.head] = zero
	q.head = (q.head + 1) % len(q.buf)
	q.size--
	return v, true
}

func (q *RingQueue[T]) Peek() (T, bool) {
	var zero T
	if q.size == 0 {
		return zero, false
	}
	return q.buf[q.head], true
}

func (q *StackQueue[T]) Enqueue(v T) { q.in = append(q.in, v) }

func (q *StackQueue[T]) Dequeue() (T, bool) {
	var zero T
	if len(q.out) == 0 {
		for len(q.in) > 0 {
			last := len(q.in) - 1
			q.out = append(q.out, q.in[last])
			q.in = q.in[:last]
		}
	}
	if len(q.out) == 0 {
		return zero, false
	}
	last := len(q.out) - 1
	v := q.out[last]
	q.out = q.out[:last]
	return v, true
}

func Josephus(n, k int) int {
	q := NewRingQueue[int](n)
	for i := 1; i <= n; i++ {
		q.Enqueue(i)
	}
	for q.Len() > 1 {
		for i := 1; i < k; i++ {
			v, _ := q.Dequeue()
			q.Enqueue(v)
		}
		q.Dequeue()
	}
	v, _ := q.Dequeue()
	return v
}

func SlidingWindowMax(nums []int, k int) []int {
	if k <= 0 || k > len(nums) {
		return nil
	}
	var dq []int // indices; nums[dq[i]] strictly decreasing
	out := make([]int, 0, len(nums)-k+1)
	for i, v := range nums {
		if len(dq) > 0 && dq[0] <= i-k {
			dq = dq[1:] // front fell out of the window
		}
		for len(dq) > 0 && nums[dq[len(dq)-1]] <= v {
			dq = dq[:len(dq)-1] // can never be a max again
		}
		dq = append(dq, i)
		if i >= k-1 {
			out = append(out, nums[dq[0]])
		}
	}
	return out
}

func (c *RecentCounter) Ping(t int) int {
	c.times = append(c.times, t)
	for c.times[0] < t-3000 {
		c.times = c.times[1:]
	}
	return len(c.times)
}