// 第 8 周 – Go 中的循环队列（环形缓冲区）
// 运行：go run ./w08/circularqueue
package main

import (
	"errors"
	"fmt"
)

type CircularQueue struct {
	data  []int
	front int // 第一个元素的下标
	rear  int // 最后一个元素的下标
	count int
}

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

func (q *CircularQueue) IsEmpty() bool { return q.count == 0 }
func (q *CircularQueue) IsFull() bool  { return q.count == len(q.data) }

// Enqueue – O(1)
func (q *CircularQueue) Enqueue(x int) error {
	if q.IsFull() {
		return errors.New("the queue is full")
	}
	q.rear = (q.rear + 1) % len(q.data)
	q.data[q.rear] = x
	q.count++
	return nil
}

// Dequeue – O(1)
func (q *CircularQueue) Dequeue() (int, error) {
	if q.IsEmpty() {
		return 0, errors.New("the queue is empty")
	}
	x := q.data[q.front]
	q.front = (q.front + 1) % len(q.data)
	q.count--
	return x, nil
}

func (q *CircularQueue) String() string {
	s := "[front] "
	for i := 0; i < q.count; i++ {
		s += fmt.Sprint(q.data[(q.front+i)%len(q.data)], " ")
	}
	return s + fmt.Sprintf("[rear]  (front=%d, rear=%d, count=%d)", q.front, q.rear, q.count)
}

func main() {
	q := NewCircularQueue(5)
	for x := 1; x <= 5; x++ {
		q.Enqueue(x * 10)
	}
	fmt.Println("5 × enqueue: ", q)
	if err := q.Enqueue(60); err != nil {
		fmt.Println("Error:", err)
	}
	a, _ := q.Dequeue()
	b, _ := q.Dequeue()
	fmt.Println("Dequeue() =", a, ", Dequeue() =", b)
	q.Enqueue(60)
	q.Enqueue(70) // rear 绕回
	fmt.Println("2 × enqueue: ", q)

	fmt.Print("emptying (FIFO): ")
	for !q.IsEmpty() {
		x, _ := q.Dequeue()
		fmt.Print(x, " ")
	}
	fmt.Println()

	// 用切片实现的简单队列：s = append(s, x) 和 s = s[1:]
	// （s[1:] 不会释放开头的空间，但 append 会不时地复制到新数组中）
	s := []string{}
	s = append(s, "Li", "Wang", "Chen")
	first := s[0]
	s = s[1:]
	fmt.Println("slice queue: removed =", first, ", remaining =", s)
}