线性表之-队列

ByWhat'sUs

线性表之-队列

和栈一样，队列也是一种特殊的线性表结构，只不过队列是在一端插入，另一端删除，就跟我们平常排队一样的道理，从队尾入队，在队头出去，所以队列的特性是先入先出（FIFO），允许插入的一端叫队尾，允许删除的一端叫队头。

和栈一样，队列也可以通过数组和链表实现，通过数组实现的叫顺序队列，通过链表实现的叫做链式队列，栈只需要一个栈顶指针就可以了，因为只允许在栈顶插入删除，但是队列需要两个指针，一个指向队头，一个指向队尾。

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("空队列!")
        return
    }
    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)
}