Golang程序 实现堆栈数据结构

在Golang中，堆栈是一个线性数据结构，它的工作原理是后进先出（LIFO），这意味着最后推入堆栈的元素将先被弹出。我们将使用两种方法来实现堆栈数据结构，即使用整数片和结构。让我们看看不同的例子来理解这个概念。

方法1：使用整数Slice

在这里，在这个方法中，Go采用了两个函数，Push和Pop，分别从堆栈的顶部添加和移除数值，并采用整数片来存储堆栈中的数值。Push函数将一个整数添加到输入的片断末尾。Pop函数从片断的末端取值并返回。通过检查片断的长度，IsEmpty方法确定堆栈是否为空。在主函数中，Push和Pop函数被用来从堆栈中添加和删除值，IsEmpty函数被用来确定堆栈是否为空。

算法

• 第1步 – 创建一个包main，并在程序中声明fmt(格式包)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步 – 做一个整数片，称为堆栈类型。

• 第 3步 – 然后，为了向堆栈顶部添加一个值，使用Push方法。

• 第 4步 – 堆栈和一个整数v是输入。

• 第5步 – 带有v的堆栈作为结果被添加到顶部

• 第 6步 – 在下一步，从堆栈中移除并返回顶部的值，实现Pop方法。

• 第7步 – 栈的顶层值和具有顶层值的栈作为输出被删除。

• 第8步 – 为了确定堆栈是否为空，实现IsEmpty函数。

• 第 9步 – 输出将是一个布尔值，表明堆栈是否为空。

• 第 10步 – 创建一个Stack类型的实例，使用Push方法添加一些值，并在main函数中使用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方法在增加顶层变量后将一个新的值添加到值片的末尾。Pop方法递减顶层变量，获得当前顶层索引的值，并将其返回。如果顶层变量等于-1，表明堆栈上没有值，IsEmpty方法返回真。让我们来看看这个代码和算法。

算法

• 第1步 – 创建一个包main，并在程序中声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步 – 建立一个堆栈结构，其两个字段为value和top。这里，top是一个整数，用来跟踪堆栈中最高值的索引，而values是一个整数片断。

• 第3步– 在下一步中，创建一个名为NewStack的函数，返回一个新的堆栈结构实例，该实例的top值为-1，value为空片。

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

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

• 第6步– 输出将是堆栈的顶部有最新的值。

• 第 7步 – 然后，实现一个Pop方法，从堆栈中取出顶部的值并返回。

• 第 8步– 在下一个案例中，Stack结构的一个实例将作为输入。

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

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

• 第 11步 – 输出将是一个布尔值，表明堆栈是否为空。

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

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

例子

在这个例子中，我们将使用堆栈结构来实现堆栈数据结构。让我们看一下代码。

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

总结

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