Golang编程：反转栈

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

算法

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

• 第2步 − 创建一个包含 item 切片的栈结构来存储栈元素。

• 第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("初始栈:")
   s.print()

   reverseS(s)

   fmt.Println("更新后的反向栈:")
   s.print()
}

输出

初始栈:
3 6 2 5 8 
更新后的反向栈:
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("初始栈:")
   s.print()

   s.reverseS()
   fmt.Println("更新后的翻转栈:")
   s.print()
}

输出

初始栈:
6 3 8 2 9 
更新后的翻转栈:
9 2 8 3 6 

结论

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