数据结构基础 入门——队列

用 Go 来实现链表、栈、队列、散列表、树、二叉树、堆、图

概念

队列是一种特殊的线性表结构,队列是在一端插入,另一端删除,就跟我们平常排队一样的道理,从队尾入队,在队头出去,所以队列的特性是先入先出(FIFO),允许插入的一端叫队尾,允许删除的一端叫队头。

栈只需要一个栈顶指针,因为只允许在栈顶插入删除,但是队列需要两个指针,一个指向队头,一个指向队尾。
对列分顺序对列(数组实现)和 链式对列(链表实现)

应用场景

消息队列 (redis,rabbitmq,kafaka)

链式对列

package main

import "fmt"

// 定义链表节点
type Node struct {
    Value int
    Next  *Node
}

//初始化对列
var size = 0
var queue = new(Node)

//入队(从队头插入)
func Push(t *Node, v int) bool {
    if queue == nil {
        queue = &Node{v, nil}
        size++
        return true
    }

    t = &Node{v, nil}
    t.Next = queue
    queue = t
    size++

    return true
}

//出队(从队尾删除)
func Pop(t *Node) (int, bool) {
    if size == 0 {
        return 0, false
    }

    if size == 1 {
        queue = nil
        size--
        return t.Value, true
    }

    //从迭代对列,直到队尾
    temp := t
    for (t.Next) != nil {
        temp = t
        t = t.Next
    }

    v := (temp.Next).Value
    temp.Next = nil

    size--
    return v, true

}

//遍历对列所有节点
func traverse(t *Node) {
    if size == 0 {
        fmt.Println("空对列!")
    }
    for t != nil {
        fmt.Printf("%d ->", t.Value)
        t = t.Next
    }
    fmt.Println()
}

func main() {
    queue = nil
    //入队
    Push(queue, 10)
    fmt.Println("Size:", size)
    //遍历
    traverse(queue)

    //出队
    v, b := Pop(queue)
    if b {
        fmt.Println("Pop:", v)
    }
    fmt.Println("Size:", size)

    //批量入队
    for i := 0; i < 5; i++ {
        Push(queue, i)
    }
    //再次遍历
    traverse(queue)
    fmt.Println("Size:", size)

    //出队
    v, b = Pop(queue)
    if b {
        fmt.Println("Pop:", v)
    }
    fmt.Println("Size:", size)

    // 再次出队
    v, b = Pop(queue)
    if b {
        fmt.Println("Pop:", v)
    }
    fmt.Println("Size:", size)
    // 再次遍历
    traverse(queue)

}

go run xxx.go

Size: 1
10 -> 
Pop: 10
Size: 0
4 -> 3 -> 2 -> 1 -> 0 -> 
Size: 5
Pop: 0
Size: 4
Pop: 1
Size: 3
4 -> 3 -> 2 ->

参考链接:
geekr.dev/posts/go-data-structure-...

本作品采用《CC 协议》,转载必须注明作者和本文链接
滴水穿石,石破天惊----晓疯子
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!