Golang 用于翻转栈

在这篇Golang文章中，我们将使用递归和迭代方法来翻转一个栈。栈是一种遵循后入先出（LIFO）原则的线性数据结构。

步骤

• 第1步 - 首先，我们需要导入fmt和strconv包。

• 第2步 - 创建一个栈结构，其中包含一个项切片来存储栈元素。

• 第3步 - 现在，定义push()、pop()、peek()、isEmpty()和print()函数来执行栈的基本操作。

• 第4步 - push()将项添加到栈的末尾，pop()从栈中移除最后一项。而peek()返回栈中的最后一项，但不删除它。

• 第5步 - isEmpty()如果栈为空则返回true，否则返回false，print()打印栈的元素。

• 第6步 - 现在，创建reverseS()函数来翻转栈。首先，它检查栈是否为空。然后，以相反的方式返回栈的元素。

• 第7步 - 它从栈顶弹出一个项并将其存储在变量temp中。然后，它递归地调用自身来翻转剩余的栈。在栈翻转后，它调用insert()函数将弹出的项插入到翻转后的栈的底部。

• 第8步 - insert()函数在栈的底部插入一个项。如果栈为空，则将项推入栈并返回。

• 第9步 - 如果栈不为空，则从栈顶弹出一个项，并递归调用自身将该项插入到底部。在插入项到底部后，将弹出的项推回到栈中。

• 第10步 - 启动main()函数。在main()函数内部，创建一个栈结构并用一些项初始化栈。

• 第11步 - 打印初始栈元素。

• 第12步 - 现在，调用reverseS()函数并将栈作为参数传递给它。

• 第13步 - 进一步，使用print()函数打印翻转后的栈元素。

示例1

在这个示例中，我们将定义一个reverseS()函数，用递归方法来翻转一个栈。

package main

import (
   "fmt"
   "strconv"
)

type Stack struct {
   items []int
}

func (s *Stack) push(item int) {
   s.items = append(s.items, item)
}

func (s *Stack) pop() int {
   l := len(s.items) - 1
   item := s.items[l]
   s.items = s.items[:l]
   return item
}
func (s *Stack) peek() int {
   return s.items[len(s.items)-1]
}

func (s *Stack) isEmpty() bool {
   return len(s.items) == 0
}

func (s *Stack) print() {
   for _, item := range s.items {
      fmt.Print(strconv.Itoa(item) + " ")
   }
   fmt.Println()
}

func reverseS(s *Stack) {
   if s.isEmpty() {
      return
   }

   temp := s.pop()
   reverseS(s)
   insert(s, temp)
}

func insert(s *Stack, item int) {
   if s.isEmpty() {
      s.push(item)
      return
   }

   temp := s.pop()
   insert(s, item)
   s.push(temp)
}

func main() {
   s := &Stack{}

   s.push(3)
   s.push(6)
   s.push(2)
   s.push(5)
   s.push(8)
   fmt.Println("Initial stack:")
   s.print()

   reverseS(s)

   fmt.Println("Updated Reversed stack:")
   s.print()
}

输出

Initial stack:
3 6 2 5 8 
Updated Reversed stack:
8 5 2 6 3

示例2

在这个示例中，我们将定义一个reverseS()函数，用于使用迭代方法反转栈。

package main

import (
   "fmt"
)

type Stack struct {
   items []int
}

func (s *Stack) push(item int) {
   s.items = append(s.items, item)
}

func (s *Stack) pop() int {
   l := len(s.items) - 1
   item := s.items[l]
   s.items = s.items[:l]
   return item
}

func (s *Stack) peek() int {
   return s.items[len(s.items)-1]
}

func (s *Stack) isEmpty() bool {
   return len(s.items) == 0
}

func (s *Stack) reverseS() {
   if s.isEmpty() {
      return
   }

   stackSize := len(s.items)
   for i := 0; i < stackSize/2; i++ {
      temp := s.items[i]
      s.items[i] = s.items[stackSize-i-1]
      s.items[stackSize-i-1] = temp
   }
}

func (s *Stack) print() {
   for _, item := range s.items {
      fmt.Printf("%d ", item)
   }
   fmt.Println()
}

func main() {
   s := &Stack{}

   s.push(6)
   s.push(3)
   s.push(8)
   s.push(2)
   s.push(9)

   fmt.Println("Initial stack:")
   s.print()

   s.reverseS()
   fmt.Println("Updated Reversed stack:")
   s.print()
}

输出

Initial stack:
6 3 8 2 9 
Updated Reversed stack:
9 2 8 3 6

结论

我们成功编译并执行了一个使用递归和迭代方法来反转栈的Go语言程序，并提供了两个示例。第一个示例中我们使用了递归方法，第二个示例中我们使用了迭代方法。