Golang实现数据结构Stack(堆栈)的示例详解

2023-05-15 17:05:34 示例 数据结构 堆栈

前言

始于此篇，为了学习 golang 基础，采用了使用 Golang 实现各种数据结构，以此来和 Golang 交朋友，今天的主题就是 把Stack介绍给Golang认识

源码：Stack

介绍Stack

在计算机科学中，stack（栈）是一种基本的数据结构，它是一种线性结构,具有后进先出（Last In First Out）的特点。

上述是通过对 ChatGPT 提问：数据结构stack。所得到的答案，我们这里拿出这句话的关键词：线性结构,后进先出。了解之后它的特性之后，应该如何实现呢，它应该包含哪些操作才叫stack呢？

通过ChatGPT的回答，我们可以知道我们需要实现的stack包含以下方法：

  • Push
  • Pop
  • Peek
  • Len
  • Cap
  • Clear

那就开始吧！

Stack

在 Golang 中，使用 struct结构体可以模拟出栈的结构，分别有存储元素的空间，栈的长度，栈的容量

type Element interface{}

type Stack struct {
	elements []Element
	top   int // 栈顶指针
	cap      int // 容量
}

Push

作用：Push 方法就是往stack的存储区域压入新的元素

// Push
func (stack *Stack) Push(element Element) (err error) {
	// top == cap时，栈满
	if stack.top >= stack.cap {
		return errors.New("the stack is full")
	}
	stack.elements[stack.top] = element
	stack.top++
	return nil
}

Pop

作用：Pop 方法是取出栈顶元素，并且在存储区域内删除

// Pop
func (stack *Stack) Pop() (ele Element, err error){
	// top == 0时，栈空
	if stack.top <= 0 {
		return nil, errors.New("the stack is empty")
	}
	ele = stack.elements[stack.top]
	// 在栈中清除当前元素
	stack.elements = append(stack.elements, stack.elements[:stack.top], stack.elements[stack.top+1:])
	stack.top--
	return ele, nil
}

Peek

作用：Peek 方法就是返回栈顶的值，但是不删除存储区域的元素

// Peek
func (stack *Stack) Peek() (ele Element, err error){
	if stack.top <= 0 {
		return nil, errors.New("the stack is empty")
	}
	ele = stack.elements[stack.top]
	return ele, nil
}

Len & Cap & Clear

  • Len：返回栈的存储的元素个数
  • Cap：当前栈的容量
  • Clear：将栈清空
// Len
func (stack *Stack) Len() int{
	return stack.top
}

// Cap
func (stack *Stack) Cap() int{
	return stack.cap
}

// Clear
func (stack *Stack) Clear() {
	if stack.top <= 0 {
		return
	}
	// 重新分配一个空切片
	stack.elements = stack.elements[:0]
	stack.top = 0
}

为了方便使用，还可以提供一个创建栈的方法：NewStack

NewStack

// 初始化栈
func NewStack(cap int) *Stack {
	elements := make([]Element, cap)
	return &Stack{
		elements: elements,
		top:   0,
		cap:      cap,
	}
}

使用

package main

import "fmt"

func main() {
	stack := NewStack(5)
	for i := 0; i < 4; i++ {
		var ele Element = i
		stack.Push(ele)
	}

	element, _ := stack.Pop()
	fmt.Println(element)

	peekEle, _ := stack.Peek()
	fmt.Println(peekEle)

	fmt.Println(stack.Len())
	fmt.Println(stack.Cap())

	stack.Clear()
}

以上就是Golang实现数据结构Stack(堆栈)的示例详解的详细内容，更多关于Golang数据结构Stack的资料请关注其它相关文章！

相关文章