Kuyruk (Queue) ve Deque

package main

import "fmt"

// naiveQueue: q = q[1:] kullanır — kapasite hiç geri kazanılmaz
type naiveQueue []int

func (q *naiveQueue) Enqueue(v int) { *q = append(*q, v) }

func (q *naiveQueue) Dequeue() (int, bool) {
	if len(*q) == 0 {
		return 0, false
	}
	v := (*q)[0]
	*q = (*q)[1:] // baş işaretçisi ilerler; öndeki bellek boşa gider
	return v, true
}

// Queue: ön indeksi tutar ve gerektiğinde sıkıştırır
type Queue[T any] struct {
	items []T
	head  int // ilk geçerli elemanın indeksi
}

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

func (q *Queue[T]) Dequeue() (T, bool) {
	var zero T
	if q.head >= len(q.items) {
		return zero, false
	}
	v := q.items[q.head]
	q.items[q.head] = zero // işaretçiyi serbest bırak
	q.head++

	// Ön yarıdan fazlası boşaldıysa sıkıştır: amortize O(1)
	if q.head > len(q.items)/2 {
		n := copy(q.items, q.items[q.head:])
		q.items = q.items[:n]
		q.head = 0
	}
	return v, true
}

func (q *Queue[T]) Len() int { return len(q.items) - q.head }

func main() {
	// Naif sürümün kapasitesi büyümeye devam eder
	var naive naiveQueue
	for i := range 1000 {
		naive.Enqueue(i)
		naive.Dequeue()
	}
	fmt.Println("naif kuyruk — uzunluk:", len(naive), "kapasite:", cap(naive))

	// Sıkıştıran sürüm kapasiteyi geri kazanır
	var q Queue[int]
	for i := range 1000 {
		q.Enqueue(i)
		q.Dequeue()
	}
	fmt.Println("sıkıştıran kuyruk — uzunluk:", q.Len(), "kapasite:", cap(q.items))

	// Doğruluk kontrolü: FIFO sırası korunuyor mu
	var fifo Queue[string]
	for _, s := range []string{"birinci", "ikinci", "üçüncü"} {
		fifo.Enqueue(s)
	}
	for fifo.Len() > 0 {
		v, _ := fifo.Dequeue()
		fmt.Print(v, " ")
	}
	fmt.Println()
	_, ok := fifo.Dequeue()
	fmt.Println("boş kuyruktan alınabildi mi:", ok)
}

package main

import (
	"errors"
	"fmt"
)

var ErrFull = errors.New("tampon dolu")

type RingBuffer[T any] struct {
	data  []T
	head  int // ilk elemanın indeksi
	count int // eleman sayısı
}

func NewRingBuffer[T any](capacity int) *RingBuffer[T] {
	return &RingBuffer[T]{data: make([]T, max(1, capacity))}
}

func (r *RingBuffer[T]) Cap() int     { return len(r.data) }
func (r *RingBuffer[T]) Len() int     { return r.count }
func (r *RingBuffer[T]) IsFull() bool { return r.count == len(r.data) }

// Enqueue: O(1), tampon doluysa hata döner
func (r *RingBuffer[T]) Enqueue(v T) error {
	if r.IsFull() {
		return ErrFull
	}
	tail := (r.head + r.count) % len(r.data)
	r.data[tail] = v
	r.count++
	return nil
}

// Push: doluysa en eskiyi atarak yazar (kayan pencere günlükleri için)
func (r *RingBuffer[T]) Push(v T) (evicted T, didEvict bool) {
	if r.IsFull() {
		evicted, _ = r.Dequeue()
		didEvict = true
	}
	_ = r.Enqueue(v)
	return evicted, didEvict
}

// Dequeue: O(1)
func (r *RingBuffer[T]) Dequeue() (T, bool) {
	var zero T
	if r.count == 0 {
		return zero, false
	}
	v := r.data[r.head]
	r.data[r.head] = zero
	r.head = (r.head + 1) % len(r.data)
	r.count--
	return v, true
}

func (r *RingBuffer[T]) Slice() []T {
	out := make([]T, 0, r.count)
	for i := range r.count {
		out = append(out, r.data[(r.head+i)%len(r.data)])
	}
	return out
}

func main() {
	rb := NewRingBuffer[int](5)

	for i := 1; i <= 5; i++ {
		_ = rb.Enqueue(i)
	}
	fmt.Println("dolu tampon:", rb.Slice(), "kapasite:", rb.Cap())
	fmt.Println("bir daha eklemeyi dene:", rb.Enqueue(6))

	v, _ := rb.Dequeue()
	fmt.Println("çıkan:", v, "→", rb.Slice())

	_ = rb.Enqueue(6) // 6, dizinin başına sarar
	fmt.Println("6 eklendi:", rb.Slice())

	// Son N kaydı tutan günlük tamponu
	log := NewRingBuffer[string](3)
	for _, line := range []string{"başladı", "bağlandı", "sorgu", "yanıt", "kapandı"} {
		if old, did := log.Push(line); did {
			fmt.Printf("  %q atıldı\n", old)
		}
	}
	fmt.Println("son 3 kayıt:", log.Slice())
}

package main

import "fmt"

type Deque[T any] struct {
	items []T
	head  int
}

func (d *Deque[T]) Len() int { return len(d.items) - d.head }

func (d *Deque[T]) PushBack(v T) {
	d.items = append(d.items, v)
}

func (d *Deque[T]) PushFront(v T) {
	if d.head > 0 { // önde yer varsa kaydırma yapma
		d.head--
		d.items[d.head] = v
		return
	}
	d.items = append([]T{v}, d.items...) // yer yoksa yeniden ayır
}

func (d *Deque[T]) PopFront() (T, bool) {
	var zero T
	if d.Len() == 0 {
		return zero, false
	}
	v := d.items[d.head]
	d.items[d.head] = zero
	d.head++
	if d.head > len(d.items)/2 {
		n := copy(d.items, d.items[d.head:])
		d.items = d.items[:n]
		d.head = 0
	}
	return v, true
}

func (d *Deque[T]) PopBack() (T, bool) {
	var zero T
	if d.Len() == 0 {
		return zero, false
	}
	last := len(d.items) - 1
	v := d.items[last]
	d.items[last] = zero
	d.items = d.items[:last]
	return v, true
}

func (d *Deque[T]) Front() (T, bool) {
	var zero T
	if d.Len() == 0 {
		return zero, false
	}
	return d.items[d.head], true
}

func (d *Deque[T]) Back() (T, bool) {
	var zero T
	if d.Len() == 0 {
		return zero, false
	}
	return d.items[len(d.items)-1], true
}

func (d *Deque[T]) Slice() []T { return d.items[d.head:] }

func main() {
	var d Deque[string]

	d.PushBack("b")
	d.PushBack("c")
	d.PushFront("a")
	fmt.Println("deque:", d.Slice(), "uzunluk:", d.Len())

	front, _ := d.Front()
	back, _ := d.Back()
	fmt.Println("ön:", front, "arka:", back)

	v1, _ := d.PopFront()
	v2, _ := d.PopBack()
	fmt.Println("önden:", v1, "arkadan:", v2, "→", d.Slice())

	// Yığın gibi kullanım (tek uçtan)
	var stackLike Deque[int]
	for i := 1; i <= 3; i++ {
		stackLike.PushBack(i)
	}
	fmt.Print("yığın gibi: ")
	for stackLike.Len() > 0 {
		v, _ := stackLike.PopBack()
		fmt.Print(v, " ")
	}
	fmt.Println()

	// Kuyruk gibi kullanım
	var queueLike Deque[int]
	for i := 1; i <= 3; i++ {
		queueLike.PushBack(i)
	}
	fmt.Print("kuyruk gibi: ")
	for queueLike.Len() > 0 {
		v, _ := queueLike.PopFront()
		fmt.Print(v, " ")
	}
	fmt.Println()
}

package main

import (
	"fmt"
	"sort"
	"sync"
)

type Job struct {
	ID    int
	Input int
}

func main() {
	// Tamponlu kanal = eşzamanlı, sınırlı kapasiteli FIFO kuyruk
	jobs := make(chan Job, 10)
	results := make(chan int, 10)

	var wg sync.WaitGroup
	for range 3 { // üç işçi aynı kuyruktan besleniyor
		wg.Go(func() {
			for job := range jobs { // kanal kapanınca döngü biter
				results <- job.Input * job.Input
			}
		})
	}

	for i := 1; i <= 8; i++ {
		jobs <- Job{ID: i, Input: i}
	}
	close(jobs)
	wg.Wait()
	close(results)

	var out []int
	for r := range results {
		out = append(out, r)
	}
	sort.Ints(out) // varış sırası belirsiz: deterministik çıktı için sırala
	fmt.Println("sonuçlar:", out)

	// Kanal kapasitesi ve doluluk
	buf := make(chan string, 3)
	buf <- "a"
	buf <- "b"
	fmt.Printf("kapasite=%d uzunluk=%d\n", cap(buf), len(buf))

	// Bloklanmadan deneme: select + default
	buf <- "c"
	select {
	case buf <- "d":
		fmt.Println("d eklendi")
	default:
		fmt.Println("kuyruk dolu, d eklenemedi")
	}

	fmt.Println("önden çıkan:", <-buf)
}

package main

import "fmt"

// maxSlidingWindow, k genişliğindeki her pencerenin maksimumunu O(n) sürede bulur.
func maxSlidingWindow(nums []int, k int) []int {
	if k <= 0 || len(nums) < k {
		return nil
	}
	out := make([]int, 0, len(nums)-k+1)
	var deque []int // indeksler; karşılık gelen değerler AZALAN sırada

	for i, v := range nums {
		// 1) Pencereden çıkan indeksi önden at
		if len(deque) > 0 && deque[0] <= i-k {
			deque = deque[1:]
		}
		// 2) Arkada kalan küçük değerler artık maksimum olamaz
		for len(deque) > 0 && nums[deque[len(deque)-1]] <= v {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)

		// 3) Pencere tamamlandıysa cevabı yaz: her zaman deque'in önü
		if i >= k-1 {
			out = append(out, nums[deque[0]])
		}
	}
	return out
}

// bruteForce: doğrulama için O(n·k) sürüm
func bruteForce(nums []int, k int) []int {
	if k <= 0 || len(nums) < k {
		return nil
	}
	out := make([]int, 0, len(nums)-k+1)
	for i := 0; i+k <= len(nums); i++ {
		best := nums[i]
		for _, v := range nums[i : i+k] {
			best = max(best, v)
		}
		out = append(out, best)
	}
	return out
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}

	for _, k := range []int{1, 3, 4, 8} {
		fast := maxSlidingWindow(nums, k)
		slow := bruteForce(nums, k)
		same := fmt.Sprint(fast) == fmt.Sprint(slow)
		fmt.Printf("k=%d → %v (kaba kuvvetle aynı mı: %t)\n", k, fast, same)
	}

	fmt.Println("k dizi boyundan büyük:", maxSlidingWindow(nums, 20))
	fmt.Println("azalan dizi:", maxSlidingWindow([]int{9, 7, 5, 3}, 2))
}