Go语言教程之边写边学：数据结构与算法：LIFO堆栈和FIFO队列

堆栈是一个有序列表，其中所有插入和删除都在一端(称为顶部)进行。队列是一个有序列表，其中所有插入都发生在一端(后部)，而所有删除都发生在另一端(前部)。堆栈有时称为后进先出 (LIFO) 列表，队列称为先进先出 (FIFO) 列表。

package main
 
import (
    "fmt"
)
 
type Node struct {
    Value int
}
 
func (n *Node) String() string {
    return fmt.Sprint(n.Value)
}
 
// 创建stack
func NewStack() *Stack {
    return &Stack{}
}
 
// Stack结构type Stack struct {
    nodes []*Node
    count int
}
 
// 压入stack
func (s *Stack) Push(n *Node) {
    s.nodes = append(s.nodes[:s.count], n)
    s.count++
}
 
// 弹出stack
func (s *Stack) Pop() *Node {
    if s.count == 0 {
        return nil
    }
    s.count--
    return s.nodes[s.count]
}
 
// 创建queue
func NewQueue(size int) *Queue {
    return &Queue{
        nodes: make([]*Node, size),
        size:  size,
    }
}
 
// Queue结构type Queue struct {
    nodes []*Node
    size  int
    head  int
    tail  int
    count int
}
 
// queue的压入func (q *Queue) Push(n *Node) {
    if q.head == q.tail && q.count > 0 {
        nodes := make([]*Node, len(q.nodes)+q.size)
        copy(nodes, q.nodes[q.head:])
        copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head])
        q.head = 0
        q.tail = len(q.nodes)
        q.nodes = nodes
    }
    q.nodes[q.tail] = n
    q.tail = (q.tail + 1) % len(q.nodes)
    q.count++
}
 
// queue的弹出func (q *Queue) Pop() *Node {
    if q.count == 0 {
        return nil
    }
    node := q.nodes[q.head]
    q.head = (q.head + 1) % len(q.nodes)
    q.count--
    return node
}
 
func main() {
    s := NewStack()
    s.Push(&Node{3})
    s.Push(&Node{5})
    s.Push(&Node{7})
    s.Push(&Node{9})
    fmt.Println(s.Pop(), s.Pop(), s.Pop(), s.Pop())
 
    q := NewQueue(1)
    q.Push(&Node{2})
    q.Push(&Node{4})
    q.Push(&Node{6})
    q.Push(&Node{8})
    fmt.Println(q.Pop(), q.Pop(), q.Pop(), q.Pop())
}

© 本文著作权归作者所有。转载请联系授权，禁止商用。

🔗 系列文章

1. Go语言教程之边写边学：Go语言介绍