注册登录

golang数据结构和算法之QueueLinkedList链表队列

队列和堆栈不一样的地方在于进出顺序：

堆栈是后进先出，

队列是先进先出。

ueueLinkedList.go
知识兔
ackage QueueLinkedList

type Node struct {
	data int
	next *Node
}

type Queue struct {
	rear *Node
}

func (list *Queue) Enqueue(i int) {
	data := &Node{data: i}
	if list.rear != nil {
		data.next = list.rear
	}
	list.rear = data
}

func (list *Queue) Dequeue() (int, bool) {
	if list.rear == nil {
		return 0, false
	}
	
	if list.rear.next == nil {
		i := list.rear.data
		list.rear = nil
		return i, true
	}
	current := list.rear
	for {
		if current.next.next == nil {
			i := current.next.data
			current.next = nil
			return i, true
		}
		current = current.next
	}
}

func (list *Queue) Peek() (int, bool) {
	if list.rear == nil {
		return 0, false
	}
	return list.rear.data, true
}

func (list *Queue) Get() []int {
	var items []int
	current := list.rear
	for current != nil {
		items = append(items, current.data)
		current = current.next
	}
	return items
}

func (list *Queue) IsEmpty() bool {
	return list.rear == nil
}

func (list *Queue) Empty() {
	list.rear = nil
}
知识兔

　　

ueueLinkedList_test.go
知识兔
ackage QueueLinkedList

import (
	"fmt"
	"math/rand"
	"testing"
	"time"
)

func TestQueueLinkedList(t *testing.T) {
	random := rand.New(rand.NewSource(time.Now().UnixNano()))
	headNode := &Node{
		data: random.Intn(100),
		next: nil,
	}
	queue := &Queue{
		rear: headNode,
	}
	fmt.Println(queue.Get())

	randNumber := random.Intn(100)
	queue.Enqueue(randNumber)
	queue.Enqueue(random.Intn(100))
	queue.Enqueue(random.Intn(100))
	fmt.Println(queue.Get())
	queue.Dequeue()
	fmt.Println(queue.Get())
	retResult, retBool := queue.Peek()
	if retBool == true {
		fmt.Println(retResult)
	}
	queue.Empty()

	if queue.IsEmpty() == false {
		t.Fail()
	}

}
知识兔

　　

输出：
知识兔
:/Go/bin/go.exe test -v [D:/go-project/src/QueueLinkedList]
=== RUN   TestQueueLinkedList
[68]
[12 49 69 68]
[12 49 69]
12
--- PASS: TestQueueLinkedList (0.00s)
PASS
ok  	QueueLinkedList	2.177s
成功: 进程退出代码 0.
知识兔

　　

计算机