Golang 实现栈数据结构

在Golang中，栈是一种线性数据结构，遵循后进先出（LIFO）原则，即最后入栈的元素将首先出栈。我们将使用两种方法来使用整数切片和结构体来实现栈数据结构。让我们通过不同的示例来理解这个概念。

方法1：使用整数切片

在这种方法中，Go使用两个函数Push和Pop来分别添加和删除栈顶的值，并使用整数切片来存储栈中的值。Push函数将一个整数添加到输入的切片末尾。Pop函数从切片的末尾取出值并返回。IsEmpty方法通过检查切片的长度来确定栈是否为空。Push和Pop函数在主函数中用于向栈中添加和删除值，IsEmpty函数用于确定栈是否为空。

步骤

• 步骤1 - 创建一个main包，并在程序中声明fmt（格式化包）包，其中main生成可执行代码，fmt帮助格式化输入和输出。

• 步骤2 - 创建一个名为Stack的整数切片类型。

• 步骤3 - 使用Push方法将一个值添加到栈顶。

• 步骤4 - Stack和一个整数v是输入。

• 步骤5 - 将栈和v作为结果添加到栈顶。

• 步骤6 - 在下一步中，实现Pop方法以删除并返回栈顶的值。

• 步骤7 - 栈顶的值和带有栈顶值的栈被删除作为输出。

• 步骤8 - 实现IsEmpty函数来确定栈是否为空。

• 步骤9 - 输出将是一个布尔值，指示栈是否为空。

• 步骤10 - 在主函数中创建一个Stack类型实例，使用Push方法添加一些值，并使用Pop方法删除一些值。最后，使用IsEmpty函数查看栈是否为空。

示例

在这个示例中，我们将使用整数切片来实现栈数据结构。让我们看看代码。

package main
import "fmt"

type Stack []int   //stack

// Push adds a value to the top of the stack.
func (st *Stack) Push(v int) {
   *st = append(*st, v)
}

// Pop removes and returns the top value from the stack.
func (st *Stack) Pop() int {
   if st.IsEmpty() {
      return 0
   }
   top := (*st)[len(*st)-1]
   *st = (*st)[:len(*st)-1]
   return top
}

func (st *Stack) IsEmpty() bool {
   return len(*st) == 0
}

func main() {
   st := Stack{}
   st.Push(1)
   st.Push(2)
   fmt.Println("The value popped from the stack is given as:")
   fmt.Println(st.Pop())
   fmt.Println(st.Pop())
   fmt.Println("Is the stack empty?")
   fmt.Println(st.IsEmpty())
}

输出

The value popped from the stack is given as:
2
1
Is the stack empty?
true

方法2：使用结构体

在这种方法中，堆栈的值存储在一个结构体中，并且堆栈顶部值的索引由一个top变量跟踪。Push方法在增加top变量之后将新值添加到values切片的末尾。Pop方法将减小top变量，获取当前顶部索引处的值并返回。如果top变量等于-1，表示堆栈上没有值，则IsEmpty方法返回true。让我们通过代码和算法来理解。

步骤

• 第1步 - 创建一个主包并在程序中声明fmt（格式化包）包，其中main用于生成可执行代码，fmt用于格式化输入和输出。

• 第2步 - 创建一个包含values和top两个字段的栈结构。这里，top是一个整数，用于跟踪堆栈中顶部值的索引，values是一个整数的切片。

• 第3步 - 接下来，创建一个名为NewStack的函数，该函数返回一个具有top值为-1和空值切片的Stack结构的新实例。

• 第4步 - 然后，使用Push方法将一个值推送到堆栈的顶部。

• 第5步 - 输入将是一个Stack结构实例和一个整数值。

• 第6步 - 输出将是堆栈，其中最近的值将出现在顶部。

• 第7步 - 接下来，实现一个Pop方法，将堆栈的顶部值弹出并返回。

• 第8步 - 下一个情况，输入将是Stack结构的一个实例。

• 第9步 - 输出将是堆栈的最高值，并且该值将被移除。

• 第10步 - 实现一个返回真的IsEmpty方法，以确定堆栈是否为空。

• 第11步 - 输出将是一个布尔值，指示堆栈是否为空。

• 第12步 - 在主函数中使用NewStack函数创建一个Stack类型实例，然后使用Push和Pop方法添加和删除值。最后，使用IsEmpty函数查看堆栈是否为空。

• 第13步 - 使用fmt.Println()方法执行打印语句，其中ln表示换行。

示例

在这个示例中，我们将使用stack结构来实现堆栈数据结构。让我们通过代码来理解。

package main
import "fmt"

type Stack struct { //stack
   values []int 
   top    int
}

func NewStack() *Stack {
   return & Stack{
      values: make([]int, 0),
      top:    -1,
   }
}

// Push adds a value to the top of the stack.
func (st *Stack) Push(value int) {
   st.top++
   st.values = append(st.values, value)
}

// Pop removes and returns the top value from the stack.
func (st *Stack) Pop() int {
   if st.IsEmpty() {
      return 0
   }
   value := st.values[st.top]
   st.top--
   return value
}

func (st *Stack) IsEmpty() bool {
   return st.top == -1
}

func main() {
   st := NewStack()
   st.Push(1)
   st.Push(2)
   fmt.Println("The value popped from the stack is given as:")
   fmt.Println(st.Pop())
   fmt.Println(st.Pop())
   fmt.Println("Is the stack empty?")
   fmt.Println(st.IsEmpty())
}

输出

The value popped from the stack is given as:
2
1
Is the stack empty?
true

结论

我们执行了使用两种方法实现栈数据结构的程序。第一种方法我们使用整数切片，第二种方法我们使用栈结构。