GolangNote

Golang笔记

用golang 实现LIFO堆栈和FIFO队列

Permalink

用golang 实现LIFO堆栈和FIFO队列

Go: LIFO堆栈和FIFO队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package main

import (
	"fmt"
)

type Node struct {
	Value int
}

func (n *Node) String() string {
	return fmt.Sprint(n.Value)
}

// NewStack returns a new stack.
func NewStack() *Stack {
	return &Stack{}
}

// Stack is a basic LIFO stack that resizes as needed.
type Stack struct {
	nodes []*Node
	count int
}

// Push adds a node to the stack.
func (s *Stack) Push(n *Node) {
	s.nodes = append(s.nodes[:s.count], n)
	s.count++
}

// Pop removes and returns a node from the stack in last to first order.
func (s *Stack) Pop() *Node {
	if s.count == 0 {
		return nil
	}
	s.count--
	return s.nodes[s.count]
}

// NewQueue returns a new queue with the given initial size.
func NewQueue(size int) *Queue {
	return &Queue{
		nodes: make([]*Node, size),
		size:  size,
	}
}

// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
	nodes []*Node
	size  int
	head  int
	tail  int
	count int
}

// Push adds a node to the 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++
}

// Pop removes and returns a node from the queue in first to last order.
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{1})
	s.Push(&Node{2})
	s.Push(&Node{3})
	fmt.Println(s.Pop(), s.Pop(), s.Pop())

	q := NewQueue(2)
	q.Push(&Node{4})
	q.Push(&Node{5})
	q.Push(&Node{6})
	fmt.Println(q.Pop(), q.Pop(), q.Pop())
}

输出:

plaintext: LIFO堆栈和FIFO队列结果输出
1
2
3 2 1
4 5 6

from https://gist.github.com/moraes/2141121

本文网址: https://golangnote.com/topic/159.html 转摘请注明来源

Related articles

谷歌翻译的 golang 库推荐

Google 的翻译越来越好了,官方的Golang SDK 已经很完美,这里介绍的是几个非官方发布的有特色的库。...

Golang WebAssembly 了解一下

Go 1.11 起开始支持 WebAssembly ,也就是说以后可以使用任何语言作为“前端语言”来进行 Web 开发。...

golang snappy 的使用场合

google 自家的 snappy 压缩优点是非常高的速度和合理的压缩率。压缩率比 gzip 小,CPU 占用小。...

Write a Comment to "用golang 实现LIFO堆栈和FIFO队列"

Submit Comment Login
Based on Golang + fastHTTP + sdb | go1.22.3 Processed in 0ms