使用Golang实现循环数组的LIFO操作

使用Golang实现循环数组的LIFO操作 循环数组应被视为缓冲区吗？根据概念，FIFO是正确的处理方式，但我们是否仍能在其上执行LIFO操作？

2 回复

我之前没有使用过环形数组，但当我看到LIFO和FIFO时，我觉得两者都不正确。在环形结构中，没有第一个或最后一个。让我们看看其他人怎么说。

更多关于使用Golang实现循环数组的LIFO操作的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


循环数组本质上是一个固定大小的环形缓冲区，通常用于实现FIFO（队列）操作，但通过调整索引管理逻辑，同样可以实现LIFO（栈）操作。关键在于维护一个指向栈顶的索引，并处理数组边界的循环。

以下是一个使用循环数组实现LIFO操作的示例：

package main

import "fmt"

type CircularStack struct {
    data   []int
    top    int // 指向栈顶元素
    size   int // 当前栈中元素数量
    maxLen int // 数组最大容量
}

func NewCircularStack(capacity int) *CircularStack {
    return &CircularStack{
        data:   make([]int, capacity),
        top:    -1,
        size:   0,
        maxLen: capacity,
    }
}

// Push 将元素压入栈顶
func (cs *CircularStack) Push(val int) bool {
    if cs.size == cs.maxLen {
        return false // 栈已满
    }
    cs.top = (cs.top + 1) % cs.maxLen
    cs.data[cs.top] = val
    cs.size++
    return true
}

// Pop 从栈顶弹出元素
func (cs *CircularStack) Pop() (int, bool) {
    if cs.size == 0 {
        return 0, false // 栈为空
    }
    val := cs.data[cs.top]
    cs.top = (cs.top - 1 + cs.maxLen) % cs.maxLen
    cs.size--
    return val, true
}

// Peek 查看栈顶元素
func (cs *CircularStack) Peek() (int, bool) {
    if cs.size == 0 {
        return 0, false
    }
    return cs.data[cs.top], true
}

func main() {
    stack := NewCircularStack(3)
    
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println(stack.Push(4)) // false，栈已满
    
    val, _ := stack.Pop()
    fmt.Println(val) // 3
    
    stack.Push(4)
    val, _ = stack.Peek()
    fmt.Println(val) // 4
}

在这个实现中：

  • top 索引始终指向栈顶元素，初始值为 -1 表示栈为空。
  • Push 操作先将 top 向前移动（考虑循环），然后存储值。
  • Pop 操作先获取栈顶值，然后将 top 向后移动（考虑循环）。
  • 通过 size 变量可以准确判断栈的空/满状态，避免与 top 索引的歧义。

循环数组实现LIFO的优势在于内存使用固定，但需要注意栈满的处理。这种结构适用于需要固定大小缓冲区的栈场景。

回到顶部