«

Golang如何实现数据结构Stack

时间:2024-6-16 06:33     作者:韩俊     分类: Go语言


本文小编为大家详细介绍“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

热门推荐