Go数据结构栈Stack和队列Queue的简单实现

一、栈 Stack 和队列 Queue

栈和队列跟链表一样都属于线性表，它们都是一组“数据元素”按照一定的顺序依次排列的结构。

栈和队列在删除和访问数据时有如下特点：

栈：先进后出，先进队的数据最后才出来。
队列：先进先出，先进队的数据先出来。

我们可以用不同的数据结构 数组（Array） 或者 链表（Linked List） 来实现 栈（stack）和 队列 (queue)。

下面会展示栈的简单实现代码，首先我们约定一个栈的基本结构：

// Stack 栈
type Stack interface {
    Push(s string)         //入栈
    Pop() (string, error)  //出栈
    Peek() (string, error) //获取栈顶元素,不做数据删除
}

二、数组栈 `ArrayStack`

数组栈的存储形式如下图所示：

ArrayStack存储形式

考虑到栈的长度不是固定的，我们使用Go的slice切片来做底层:

// ArrayStack 数组栈
type ArrayStack struct {
	array   []string   //切片作为底层
	maxSize int        //栈大小
	lock    sync.Mutex //并发安全锁
}

下面我们实现3个操作。

2.1 入栈 `Push`

// Push 入栈
func (stack *ArrayStack) Push(s string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	//插入数据到栈顶
	stack.array = append(stack.array, s)
	stack.maxSize++
}

2.2 出栈 `Pop`

// Pop 出栈
func (stack *ArrayStack) Pop() (string, error) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	if stack.maxSize == 0 {
		return "", errors.New("empty")
	}
	s := stack.array[stack.maxSize-1]

    // 切片收缩
    //stack.array = stack.array[0 : stack.maxSize-1]

    //这里使用copy函数，copy函数会丢弃原切片中较短最后一个元素
	destArray := make([]string, stack.maxSize-1, stack.maxSize-1)
	copy(destArray, stack.array)
	stack.array = destArray

	//循环
	//newArray := make([]string, stack.maxSize-1, stack.maxSize-1)
	//for i := 0; i < stack.maxSize-1; i++ {
	//	newArray[i] = stack.array[i]
	//}
	//stack.array = newArray
	
	// 栈中元素数量-1
	stack.maxSize--
	return s, nil
}

入栈和出栈操作都加上了互斥锁。

当栈大小 maxSize=0 时为空栈，此时出栈会有empty error抛出，但不影响栈的继续运行。

栈顶元素取出后，可以有三种方式缩容：

切片偏移量向前移动 stack.array[0 : stack.maxSize-1] ，此时，切片被缩容
使用内置的copy函数来建一个新的切片
循环赋值一个新的切片

Benchmark测试三种方式差别很小。

2.3 获取栈顶元素 `Peek`

// Peek 获取栈顶元素
func (stack *ArrayStack) Peek() (string, error) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	if stack.maxSize == 0 {
		return "", errors.New("empty")
	}
	return stack.array[stack.maxSize-1], nil
}

考虑到 maxSize在出栈和入栈中都有联动，需要加锁保证并发安全。

三、链表栈 `LinkStack`

链表栈的存储形式如下图所示：

LinkStack存储形式

定义结构如下：

// LinkStack 单链表栈
type LinkStack struct {
	root *LinkNode  //栈顶
	size int        //栈深
	lock sync.Mutex //并发锁
}

type LinkNode struct {
	value string
	Next  *LinkNode
}

LinkStack结构持有栈顶元素root及栈的大小size。

3.1 入栈 `Push`

// Push 入栈
func (stack *LinkStack) Push(s string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	lastNode := stack.root
	node := new(LinkNode)
	node.value = s
	node.Next = lastNode
	stack.root = node
	stack.size++
}

3.2 出栈 `Pop`

// Pop 出栈
func (stack *LinkStack) Pop() (string, error) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	if stack.root == nil {
		return "", errors.New("empty")
	}
	s := stack.root.value
	nextNode := stack.root.Next
	stack.root = nextNode
	stack.size--
	return s, nil
}

链表栈的操作主要是栈顶元素的变更。

3.3 获取栈顶元素 `Peek`

// Peek 获取栈顶元素
func (stack *LinkStack) Peek() (string, error) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	if stack.size == 0 {
		return "", errors.New("empty")
	}
	s := stack.root.value

	return s, nil
}

四、测试代码

stack_test.go

package stack

import (
	"math/rand"
	"sync"
	"testing"
)

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const stringLen = 16

const stackSize = 1000

func RandStringBytes(n int) string {
	l := len(letterBytes)
	b := make([]byte, n)
	for i := range b {
		b[i] = letterBytes[rand.Intn(l)]
	}
	return string(b)
}

// test stack Push by interface
func testStackPush(t *testing.T, stack Stack) {
	for i := 0; i < stackSize; i++ {
		s := RandStringBytes(stringLen)
		stack.Push(s)
		p, err := stack.Peek()
		if err != nil || p != s {
			t.Errorf("push:%s != peek: %s", s, p)
		}
	}
}

// test stack Pop by interface
func testStackPop(t *testing.T, stack Stack) {
	var storage [stackSize]string
	for i := 0; i < stackSize; i++ {
		s := RandStringBytes(stringLen)
		storage[i] = s
		stack.Push(s)
		p, err := stack.Peek()
		if err != nil || p != s {
			t.Errorf("push:%s, peek: %s", s, p)
		}
	}

	for i := 0; i < stackSize; i++ {
		p, err := stack.Pop()
		if err != nil {
			s := storage[stackSize-1-i]
			if p != s {
				t.Errorf("storage:%s != pop: %s", s, p)
			}
		}
	}
}

// test stack On Goroutines by interface
func testStackOnGoroutine(t *testing.T, stack Stack) {
	wg := sync.WaitGroup{}
	for i := 0; i < stackSize; i++ {
		s := RandStringBytes(stringLen)
		wg.Add(1)
		go func() {
			stack.Push(s)
		}()
	}

	go func() {
		for {
			_, err := stack.Pop()
			if err == nil {
				wg.Done()
			}
		}
	}()

	wg.Wait()
}

func TestArrayStackPush(t *testing.T) {
	stack := new(ArrayStack)
	testStackPush(t, stack)
}

func TestArrayStackPop(t *testing.T) {
	stack := new(ArrayStack)
	testStackPop(t, stack)
}

func TestArrayStackOnGoroutine(t *testing.T) {
	stack := new(ArrayStack)
	testStackOnGoroutine(t, stack)
}

func TestLinkStackPush(t *testing.T) {
	stack := new(LinkStack)
	testStackPush(t, stack)
}

func TestLinkStackPop(t *testing.T) {
	stack := new(LinkStack)
	testStackPop(t, stack)
}

func TestLinkStackOnGoroutine(t *testing.T) {
	stack := new(LinkStack)
	testStackOnGoroutine(t, stack)
}

执行：

cd stack
go test -v

输出：

=== RUN   TestArrayStackPush
--- PASS: TestArrayStackPush (0.00s)
=== RUN   TestArrayStackPop         
--- PASS: TestArrayStackPop (0.01s) 
=== RUN   TestArrayStackOnGoroutine
--- PASS: TestArrayStackOnGoroutine (0.00s)
=== RUN   TestLinkStackPush
--- PASS: TestLinkStackPush (0.00s)
=== RUN   TestLinkStackPop
--- PASS: TestLinkStackPop (0.00s)
=== RUN   TestLinkStackOnGoroutine
--- PASS: TestLinkStackOnGoroutine (0.00s)
PASS
ok      github.com/leolu9527/algorithm/stack    0.208s

4.1 Benchmark

benchmark_test.go

package stack

import (
	"fmt"
	"math/rand"
	"testing"
)

// Benchmark for ArrayStack
func BenchmarkArrayStackParallel(b *testing.B) {
	var stack = new(ArrayStack)
	b.RunParallel(func(pb *testing.PB) {
		s := RandStringBytes(16)
		for pb.Next() {
			x := rand.Intn(1)
			if x == 0 {
				stack.Push(s)
			} else {
				_, err := stack.Pop()
				if err != nil {
					fmt.Println(err)
				}
			}
		}
	})
}

// Benchmark for LinkStack
func BenchmarkLinkStackParallel(b *testing.B) {
	var stack = new(LinkStack)
	b.RunParallel(func(pb *testing.PB) {
		s := RandStringBytes(16)
		for pb.Next() {
			x := rand.Intn(1)
			if x == 0 {
				stack.Push(s)
			} else {
				_, err := stack.Pop()
				if err != nil {
					fmt.Println(err)
				}
			}
		}
	})
}

执行：

cd stack
go test -benchmem -bench . -run=none

输出：

goos: windows
goarch: amd64
pkg: github.com/leolu9527/algorithm/stack
cpu: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
BenchmarkArrayStackParallel-8            8448782               138.2 ns/op            97 B/op          0 allocs/op
BenchmarkLinkStackParallel-8             8633092               129.8 ns/op            24 B/op          1 allocs/op
PASS
ok      github.com/leolu9527/algorithm/stack    2.841s

附录

代码：https://github.com/leolu9527/go-algorithms/tree/main/stack

Last modified on 2022-05-13

一、栈 Stack 和队列 Queue

二、数组栈 ArrayStack

2.1 入栈 Push

2.2 出栈 Pop

2.3 获取栈顶元素 Peek

三、链表栈 LinkStack

3.1 入栈 Push

3.2 出栈 Pop

3.3 获取栈顶元素 Peek