Golang链表队列

链表

// 最简单的链表
type LinkNode struct {
	Value interface{}
	Next  *LinkNode
}

队列

// 链表队列，先进先出
type LinkQueue struct {
	root *LinkNode  // 链表起点
	size int        // 队列的元素数量
	lock sync.Mutex // 为了并发安全使用的锁
}

// 入队
// 将元素放在链表的末尾，所以需要遍历链表，时间复杂度为：O(n)
func (queue *LinkQueue) Push(v interface{}) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 如果栈顶为空，那么增加节点
	if queue.root == nil {
		queue.root = new(LinkNode)
		queue.root.Value = v
	} else {
		// 否则新元素插入链表的末尾
		// 新节点
		newNode := new(LinkNode)
		newNode.Value = v

		// 一直遍历到链表尾部
		nowNode := queue.root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}

		// 新节点放在链表尾部
		nowNode.Next = newNode
	}

	// 队中元素数量+1
	queue.size = queue.size + 1
}

// 出队
// 链表第一个节点出队即可，时间复杂度为：O(1)
func (queue *LinkQueue) Pop() interface{} {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队中元素已空
	if queue.size == 0 {
		panic("队列元素为空")
	}

	// 顶部元素要出队
	topNode := queue.root
	v := topNode.Value

	// 将顶部元素的后继链接链上
	queue.root = topNode.Next

	// 队中元素数量-1
	queue.size = queue.size - 1

	return v
}

// 获取队列最后一个元素
// 时间复杂度为：O(n)，不建议使用。尽量少的获取队列的最后一个元素是什么
func (queue *LinkQueue) Last() interface{} {
	// 栈中元素已空
	if queue.size == 0 {
		panic("队列元素为空")
	}

	// 队列最后一个元素的值
	v := queue.root.Value
	next := queue.root.Next
	for {
		if next != nil {
			v = next.Value
			next = next.Next
			continue
		}
		break
	}
	return v
}

// 获取队列第一个元素
func (queue *LinkQueue) First() interface{} {
	// 栈中元素已空
	if queue.size == 0 {
		panic("队列元素为空")
	}

	// 队列第一个元素的值
	v := queue.root.Value
	return v
}

// 队列大小
// 时间复杂度都是：O(1)
func (queue *LinkQueue) Size() int {
	return queue.size
}

// 队列是否为空
// 时间复杂度都是：O(1)
func (queue *LinkQueue) IsEmpty() bool {
	return queue.size == 0
}

package zgo_algorithm

import (
	"fmt"
	"testing"
)

func TestLinkQueue(t *testing.T) {
	linkQueue := new(LinkQueue)
	linkQueue.Push("a")
	linkQueue.Push("b")
	linkQueue.Push("c")
	if linkQueue.First() != "a" {
		panic("校验First方法失败")
	}
	if linkQueue.Last() != "c" {
		panic("校验Last方法失败")
	}
	fmt.Println(linkQueue.First(), linkQueue.Last())
	fmt.Println("size:", linkQueue.Size())
	fmt.Println("pop:", linkQueue.Pop())
	fmt.Println("pop:", linkQueue.Pop())
	fmt.Println("size:", linkQueue.Size())
	linkQueue.Push("d")
	fmt.Println("pop:", linkQueue.Pop())
}

=== RUN   TestLinkQueue
a c
size: 3
pop: a
pop: b
size: 1
pop: c
--- PASS: TestLinkQueue (0.00s)
PASS