数据结构： Go 链表实现队列

队列的特点

• 只允许一端进行插入，而另一端进行删除的线性表。
• 遵从 先入先出 原则

队列的抽象数据类型

Data

元素具有相同的类型，相邻元素具有前驱和后继

操作

• 初始化
• 清空
• 添加元素
• 删除元素
• 队列长度

代码

package main

import "fmt"

/*
   我们用单链表来实现队列的功能。
   头指针指向 队列的第一个元素。
   尾指针指向 队列的最后一个元素。
*/
type Element interface{}

type Node struct {
    Data Element
    Next *Node
}

type Queue struct {
    Head   *Node
    Tail   *Node
    Length int
}

// 创建一个栈
func Create() *Queue {
    head := &Node{Data: nil, Next: nil}
    tail := &Node{Data: nil, Next: nil}

    return &Queue{Head: head, Tail: tail, Length: 0}
}

// 返回栈的长度
func (q *Queue) Len() int {
    return q.Length
}

// 判断栈是否为空
func (q *Queue) IsEmpty() bool {
    if q.Len() == 0 {
        return true
    }
    return false
}

// 打印栈元素
func (q *Queue) Print() {
    if q.IsEmpty() {
        fmt.Println("queue is empty")
    }

    p := q.Head.Next
    iNode := 1
    for p != nil {
        fmt.Printf("iNode == %#v,Data == %#v\n", iNode, p.Data)
        iNode++
        p = p.Next
    }

    return
}

// 向栈内添加元素
func (q *Queue) Append(e Element) {
    node := &Node{Data: e, Next: nil}
    // 如果为空
    if q.IsEmpty() {
        q.Head.Next = node
        q.Tail.Next = node
        q.Length++

        return
    }

    // 让最后一个节点的 Next 指向 新的节点
    q.Tail.Next.Next = node
    // 尾节点指向 新的节点
    q.Tail.Next = node
    q.Length++

    return
}

// 删除元素，出队列
func (q *Queue) Delete() {
    if q.IsEmpty() {
        fmt.Println("queue is empty")

        return
    }

    if q.Len() == 1 {
        q.Head.Next = nil
        q.Tail.Next = nil
        q.Length--

        return
    }

    q.Head.Next = q.Head.Next.Next
    q.Length--

    return
}

// 清空队列
func (q *Queue) Clear() {
    if q.IsEmpty() {
        fmt.Println("queue is empty")

        return
    }

    q.Head.Next = nil
    q.Tail.Next = nil
    q.Length = 0

    return
}

func main() {
    q := Create()

    q.Append(1)
    q.Append(1)
    q.Append(1)
    q.Append(1)
    q.Append(1)

    q.Delete()
    q.Clear()
    q.Print()
    fmt.Println(q.Len())
}