Go语言实现栈Stack数据结构：原理、方法与代码详解

栈的核心特性与方法

栈（Stack）是受限的线性表，仅允许在表尾进行插入和删除操作。理解其后进先出的特性后，我们需要实现以下基础方法：

• Push：将元素压入栈顶。
• Pop：弹出并移除栈顶元素。
• Peek：返回栈顶元素但不移除。
• Len/Cap：获取当前元素数量与总容量。
• Clear：清空栈内容。

定义栈结构体

在 Go 语言中，我们可以使用 struct 来封装数据。为了方便支持任意类型，我们定义一个空的接口 Element interface{} 作为存储元素的类型，并在栈结构中维护底层切片、栈顶指针和容量。

type Element interface{}

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

实现核心操作方法

第1步：Push（入栈）

目的：向栈中添加新元素。入口为调用该方法的实例对象。
动作：检查容量是否已满，若未满则将元素存入当前位置并移动指针。

// Push 往stack的存储区域压入新的元素
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
}

第2步：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
}

第3步：Peek（查看栈顶）

目的：预览栈顶元素而不改变栈的状态。
动作：仅判断是否为空并返回当前 top 位置的元素。

// 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：直接返回 top 值即为当前元素个数。
• 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的资料请关注本站其它相关文章！