// 11. hét – Verem és sor láncolt listával (generikusan), közös interfésszel
// Futtatás: go run ./h11/linkedstackqueue
package main

import (
	"errors"
	"fmt"
	"strings"
)

type Stack[T any] interface {
	Push(x T)
	Pop() (T, error)
	IsEmpty() bool
}

type node[T any] struct {
	value T
	next  *node[T]
}

// LinkedStack: a teteje a lista eleje – O(1)
type LinkedStack[T any] struct{ top *node[T] }

func (s *LinkedStack[T]) Push(x T) { s.top = &node[T]{x, s.top} }

func (s *LinkedStack[T]) Pop() (T, error) {
	var zero T
	if s.top == nil {
		return zero, errors.New("üres verem")
	}
	x := s.top.value
	s.top = s.top.next
	return x, nil
}

func (s *LinkedStack[T]) IsEmpty() bool { return s.top == nil }

// SliceStack: ugyanaz az interfész szelettel (7. hét)
type SliceStack[T any] struct{ items []T }

func (s *SliceStack[T]) Push(x T) { s.items = append(s.items, x) }
func (s *SliceStack[T]) Pop() (T, error) {
	var zero T
	if len(s.items) == 0 {
		return zero, errors.New("üres verem")
	}
	x := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return x, nil
}
func (s *SliceStack[T]) IsEmpty() bool { return len(s.items) == 0 }

// LinkedQueue: kivétel az elejéről, betétel a végére – O(1)
type LinkedQueue[T any] struct {
	front, rear *node[T]
}

func (q *LinkedQueue[T]) Enqueue(x T) {
	n := &node[T]{value: x}
	if q.rear == nil {
		q.front = n
	} else {
		q.rear.next = n
	}
	q.rear = n
}

func (q *LinkedQueue[T]) Dequeue() (T, error) {
	var zero T
	if q.front == nil {
		return zero, errors.New("üres sor")
	}
	x := q.front.value
	q.front = q.front.next
	if q.front == nil {
		q.rear = nil // kiürült
	}
	return x, nil
}

func (q *LinkedQueue[T]) IsEmpty() bool { return q.front == nil }

// reverse csak az interfészt ismeri
func reverse(s string, st Stack[rune]) string {
	for _, c := range s {
		st.Push(c)
	}
	var sb strings.Builder
	for !st.IsEmpty() {
		c, _ := st.Pop()
		sb.WriteRune(c)
	}
	return sb.String()
}

func main() {
	fmt.Println("reverse listás veremmel:  ", reverse("数据结构", &LinkedStack[rune]{}))
	fmt.Println("reverse szeletes veremmel:", reverse("数据结构", &SliceStack[rune]{}))

	var q LinkedQueue[string]
	q.Enqueue("Li")
	q.Enqueue("Wang")
	q.Enqueue("Chen")
	x, _ := q.Dequeue()
	q.Enqueue("Anna")
	fmt.Print("sor: Dequeue = ", x, ", maradék: ")
	for !q.IsEmpty() {
		v, _ := q.Dequeue()
		fmt.Print(v, " ")
	}
	fmt.Println()
}