package queue

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
)

/*
	链表中的元素
*/
type Node struct {
	// 节点的值
	value interface{}
	// 下一个元素的指针
	next *Node
}

/*
	设置节点的值
*/
func (node *Node) SetValue(value interface{}) {
	node.value = value
}

/*
	设置下一个节点
*/
func (node *Node) SetNext(next *Node) {
	node.next = next
}

/*
	获取节点的值
*/
func (node Node) GetValue() interface{} {
	return node.value
}

/*
	获取下一个节点
*/
func (node Node) GetNext() *Node {
	return node.next
}

/*
	打印node
*/
func (node Node) String() string {
	return fmt.Sprint(node.value)
}

/*
	基于链表实现的队列
*/
type LinkedListQueue struct {
	head, tail *Node
	size       int
}

/*
	O(1)
	队列的尾部添加元素
*/
func (queue *LinkedListQueue) Enqueue(item interface{}) {
	if queue.tail == nil {
		queue.tail = &Node{value: item, next: nil}
		queue.head = queue.tail
	} else {
		// 在队列的尾部添加元素.因为queue.tail是指针，因此也更新了head.next或者是以head为头部链表中的尾部的next
		queue.tail.next = &Node{value: item, next: nil}
		// 更新队尾的元素,下次在这队尾添加元素
		queue.tail = queue.tail.next
	}
	queue.size++
}

/*
	O(1)
　	删除队列头部的元素
*/
func (queue *LinkedListQueue) Dequeue() (interface{}, error) {
	if queue.IsEmpty() {
		return nil, common.IndexError{}
	}
	// 获取要出队的元素
	retNode := queue.head
	// 更新队列首的元素
	queue.head = retNode.next
	// 如果新的队列的首部元素为nil,则表示队列为空,需要将队尾也重置为nil
	if queue.head == nil {
		queue.tail = nil
	}
	queue.size--
	return retNode.value, nil
}

/*
	查看队首元素
*/
func (queue LinkedListQueue) GetFront() (interface{}, error) {
	if queue.IsEmpty() {
		return nil, common.IndexError{}
	}
	return queue.head.value, nil
}

/*
	获取队列大小
*/
func (queue LinkedListQueue) GetSize() int {
	return queue.size
}

/*
	获取队列是否为空
*/
func (queue LinkedListQueue) IsEmpty() bool {
	return queue.size == 0
}

func (queue LinkedListQueue) String() string {
	res := "Queue : front "
	for cur := queue.head; cur != nil; cur = cur.next {
		res += fmt.Sprintf("%v->", cur.value)
	}
	res += "NIL tail"
	return res
}