golang 蓝桥杯 开发语言 后端 职场和发展 [Go数据结构与算法]2. 栈与队列的结构与实现

theme: vuepress

highlight: xcode

栈的定义

栈是一种基于线性表实现的数据结构，特性是先进后出。先进入栈的元素后出来。

结构体定义

先定义栈的接口 Stack：

```go // 栈的接口 type Stack[T comparable] interface {

// 判空

IsEmpty() bool

// 返回大小

Size() int

// 压栈

Push(e T)

// 弹栈

Pop() T

// 返回栈顶

Peek() T

} ```

Stack 接口定义了栈有关的操作的方法。

顺序栈

ArrayStack 结构体是基于切片，其实也就是数组实现的栈。

```go package stack

import ( "fmt" "strings" )

// 使用数组实现的栈 type ArrayStack[T comparable] struct { values []T }

func NewArrayStackT comparable *ArrayStack[T] { return &ArrayStack[T]{values: make([]T, 0, 10)} }

func (a *ArrayStack[T]) String() string { if l.head == nil { return "

" } var ans strings.Builder

ans.WriteString("[")

for i, value := range a.values {

if i+1 == len(a.values) {

ans.WriteString(fmt.Sprintf("%v", value))

break

} ans.WriteString(fmt.Sprintf("%v, ", value))

}

ans.WriteString("]")

return ans.String()

}

func (a *ArrayStack[T]) IsEmpty() bool { return len(a.values) == 0 }

func (a *ArrayStack[T]) Size() int { return len(a.values) }

func (a *ArrayStack[T]) Push(e T) { a.values = append(a.values, e) }

func (a *ArrayStack[T]) Pop() T { i := len(a.values) - 1 ans := a.values[i] a.values = a.values[:i] return ans }

func (a *ArrayStack[T]) Peek() T { return a.values[len(a.values)-1] } ```

写一个测试用例：

go func TestArrayStack(t *testing.T) { stack := NewArrayStack[int]() fmt.Printf("stack is empty: %v\n", stack.IsEmpty()) fmt.Println(stack) stack.Push(5) stack.Push(4) stack.Push(3) stack.Push(2) stack.Push(1) fmt.Println(stack) fmt.Printf("stack is empty: %v\n", stack.IsEmpty()) fmt.Printf("stack's peek is: %v\n", stack.Peek()) fmt.Printf("stack's size is: %v\n", stack.Size()) fmt.Println("stack pops:") for !stack.IsEmpty() { fmt.Println(stack.Pop()) } }

结果如下：

链式栈

LinkedStack 结构体是基于链表实现的栈。

```go package stack

import ( "fmt" "strings"

"github.com/code-art/algorithm-go/list"

)

// 链式栈 type LinkedStack[T comparable] struct { head *list.ListNode[T] size int }

func NewLinkedStackT comparable *LinkedStack[T] { return &LinkedStack[T]{} }

func (l *LinkedStack[T]) String() string { var ans strings.Builder for p := l.head; p != nil; p = p.Next { if p.Next == nil { ans.WriteString(fmt.Sprintf("%v", p.Val)) break } ans.WriteString(fmt.Sprintf("%v->", p.Val)) } return ans.String() }

func (l *LinkedStack[T]) IsEmpty() bool { return l.size == 0 }

func (l *LinkedStack[T]) Size() int { return l.size }

// 链式栈入栈操作相当于链表头插入 func (l *LinkedStack[T]) Push(e T) { oldHead := l.head l.head = &list.ListNode[T]{Val: e} l.head.Next = oldHead l.size++ }

func (l *LinkedStack[T]) Pop() T { ans := l.head.Val l.head = l.head.Next l.size-- return ans }

func (l *LinkedStack[T]) Peek() T { return l.head.Val } ```

写一个测试用例：

go func TestLinkedStack(t *testing.T) { stack := NewLinkedStack[int]() fmt.Printf("stack is empty: %v\n", stack.IsEmpty()) fmt.Println(stack) stack.Push(5) stack.Push(4) stack.Push(3) stack.Push(2) stack.Push(1) fmt.Println(stack) fmt.Printf("stack is empty: %v\n", stack.IsEmpty()) fmt.Printf("stack's peek is: %v\n", stack.Peek()) fmt.Printf("stack's size is: %v\n", stack.Size()) fmt.Println("stack pops:") for !stack.IsEmpty() { fmt.Println(stack.Pop()) } }

结果如下：

队列的定义

队列是是一种先入先出的数据结构，先进入的元素先出去。

结构体定义

定义队列的接口 Queue：

```go // 队列的接口 type Queue[T comparable] interface { IsEmpty() bool

Size() int

// 入队

Enqueue(e T)

// 出队

Dequeue() T

// 返回队头

Peek() T

} ```

顺序队列

```go package queue

import ( "fmt" "strings" )

type ArrayQueue[T comparable] struct { values []T }

func NewArrayQueueT comparable *ArrayQueue[T] { return &ArrayQueue[T]{values: make([]T, 0, 10)} }

func (a *ArrayQueue[T]) String() string { var ans strings.Builder ans.WriteString("[") for i, value := range a.values { if i+1 == len(a.values) { ans.WriteString(fmt.Sprintf("%v", value)) break } ans.WriteString(fmt.Sprintf("%v, ", value)) } ans.WriteString("]") return ans.String() }

func (a *ArrayQueue[T]) IsEmpty() bool { return len(a.values) == 0 }

func (a *ArrayQueue[T]) Size() int { return len(a.values) }

func (a *ArrayQueue[T]) Enqueue(e T) { a.values = append(a.values, e) }

func (a *ArrayQueue[T]) Dequeue() T { ans := a.values[0] a.values = a.values[1:] return ans }

func (a *ArrayQueue[T]) Peek() T { return a.values[0] } ```

单元测试：

go func TestArrayQueue(t *testing.T) { queue := NewArrayQueue[int]() fmt.Println("queue is empty: ", queue.IsEmpty()) queue.Enqueue(5) queue.Enqueue(4) queue.Enqueue(3) queue.Enqueue(2) queue.Enqueue(1) fmt.Println(queue) fmt.Println("queue's peek is: ", queue.Peek()) fmt.Println("queue's size is: ", queue.Size()) fmt.Println("queue dequeues:") for !queue.IsEmpty() { fmt.Println(queue.Dequeue()) } }

链式队列

```go package queue

import ( "fmt" "strings"

"github.com/code-art/algorithm-go/list"

)

type LinkedQueue[T comparable] struct { head *list.ListNode[T] tail *list.ListNode[T] size int }

func NewLinkedQueueT comparable *LinkedQueue[T] { return &LinkedQueue[T]{} }

func (l *LinkedQueue[T]) String() string { var ans strings.Builder for p := l.head; p != nil; p = p.Next { if p.Next == nil { ans.WriteString(fmt.Sprintf("%v", p.Val)) break } ans.WriteString(fmt.Sprintf("%v->", p.Val)) } return ans.String() }

func (l *LinkedQueue[T]) IsEmpty() bool { return l.size == 0 }

func (l *LinkedQueue[T]) Size() int { return l.size }

func (l *LinkedQueue[T]) Enqueue(e T) { newNode := &list.ListNode[T]{Val: e} if l.head == nil { l.head = newNode l.tail = newNode } else { l.tail.Next = newNode l.tail = newNode } l.size++ } ```

单元测试：

go func TestLinkedQueue(t *testing.T) { queue := NewLinkedQueue[int]() fmt.Println("queue is empty: ", queue.IsEmpty()) queue.Enqueue(5) queue.Enqueue(4) queue.Enqueue(3) queue.Enqueue(2) queue.Enqueue(1) fmt.Println(queue) fmt.Println("queue's peek is: ", queue.Peek()) fmt.Println("queue's size is: ", queue.Size()) fmt.Println("queue dequeues:") for !queue.IsEmpty() { fmt.Println(queue.Dequeue()) } }

参考源码地址

algorithm-go: algorithm in go (gitee.com)

好文推荐

 您阅读本篇文章共花了：