• GO语言-数据结构-栈


    目录

    1.栈的顺序存储实现

    1.1结构体定义

    1.2 初始化栈

    1.3入栈

    1.4出栈

    1.5完整代码

    1.6拓展-一个数组实现两个栈

    2.栈的链式存储实现

    2.1链栈的结构体定义

    2.2链栈的初始化

    2.3链栈的入栈

    2.4链栈的出栈

    2.5链栈实现的完整代码


    栈(stack),是具有一定操作约束的线性表。其只能在一端(栈顶,Top)做插入、删除操作。

    • 插入数据:入栈(Push)
    • 删除数据:出栈(Pop)
    • 先入后出:Last In First Out(LIFO)

    栈的抽象数据类型描述

    数据对象集:一个有0或多个元素的线性表。

    操作集:

    1. 生成空栈,其最大长度为MaxSize
    2. 判断栈是否已满
    3. 判断栈是否为空
    4. 将元素压入栈
    5. 将栈顶元素返回并删除

    1.栈的顺序存储实现

    栈的顺序存储结构体,通常由一个数组一个记录栈顶元素位置的变量组成。

    1.1结构体定义

    1. type Stack struct {
    2. MaxSize int
    3. Top int
    4. arr [10]int
    5. }

    1.2 初始化栈

    1. func initStack() (stack *Stack) {
    2. stack = &Stack{
    3. MaxSize: 10,
    4. Top: -1,
    5. arr: [10]int{},
    6. }
    7. return stack
    8. }

    1.3入栈

    1. func (s *Stack) push(v int) error {
    2. //判断栈是否满
    3. if s.MaxSize-1 == s.Top {
    4. return errors.New("栈已满,无法插入数据")
    5. }
    6. s.Top++ //栈顶+1
    7. s.arr[s.Top] = v //入栈
    8. return nil
    9. }

    1.4出栈

    1. func (s *Stack) pop() (int, error) {
    2. //判断栈是否为空
    3. if s.Top == -1 {
    4. return 0, errors.New("error: 栈为空")
    5. }
    6. v := s.arr[s.Top] //出栈
    7. s.Top-- //栈顶-1
    8. return v, nil
    9. }

    1.5完整代码

    1. package main
    2. import (
    3. "errors"
    4. "fmt"
    5. )
    6. type Stack struct {
    7. MaxSize int
    8. Top int
    9. arr [10]int
    10. }
    11. func main() {
    12. //初始化一个栈
    13. stack1 := initStack()
    14. //验证空栈pop报错
    15. fmt.Println("---空栈pop报错---")
    16. _, err := stack1.pop()
    17. if err != nil {
    18. fmt.Println(err)
    19. }
    20. //入栈
    21. fmt.Println("---栈满push报错---")
    22. for i := 1; 1 <= 20; i++ {
    23. err := stack1.push(i)
    24. if err != nil {
    25. fmt.Println(err)
    26. break
    27. }
    28. }
    29. //出栈
    30. v, _ := stack1.pop()
    31. fmt.Println("---pop出栈---:", v)
    32. }
    33. func initStack() (stack *Stack) {
    34. stack = &Stack{
    35. MaxSize: 10,
    36. Top: -1,
    37. arr: [10]int{},
    38. }
    39. return stack
    40. }
    41. func (s *Stack) push(v int) error {
    42. //判断栈是否满
    43. if s.MaxSize-1 == s.Top {
    44. return errors.New("栈已满,无法插入数据")
    45. }
    46. s.Top++ //栈顶+1
    47. s.arr[s.Top] = v //入栈
    48. return nil
    49. }
    50. func (s *Stack) pop() (int, error) {
    51. //判断栈是否为空
    52. if s.Top == -1 {
    53. return 0, errors.New("error: 栈为空")
    54. }
    55. v := s.arr[s.Top] //出栈
    56. s.Top-- //栈顶-1
    57. return v, nil
    58. }

      

    1.6拓展-一个数组实现两个栈

    使用一个数组实现两个堆栈,要求最大地利用数组空间。使数组只要有空间,入栈操作就可以成功。

    1. package main
    2. import (
    3. "errors"
    4. "fmt"
    5. )
    6. type Stack struct {
    7. Top1 int
    8. Top2 int
    9. arr [10]int
    10. }
    11. func main() {
    12. //初始化一个栈
    13. stack1 := initStack()
    14. fmt.Println(stack1.arr)
    15. //验证空栈pop报错
    16. fmt.Println("---空栈pop报错---")
    17. _, err := stack1.pop(1)
    18. if err != nil {
    19. fmt.Println(err)
    20. }
    21. _, err = stack1.pop(2)
    22. if err != nil {
    23. fmt.Println(err)
    24. }
    25. //入栈
    26. fmt.Println("---栈满push报错---")
    27. for i := 1; i <= 5; i++ {
    28. err := stack1.push(i, 1)
    29. if err != nil {
    30. fmt.Println(err)
    31. break
    32. }
    33. }
    34. for i := 1; i <= 6; i++ {
    35. err := stack1.push(i, 2)
    36. if err != nil {
    37. fmt.Println(err)
    38. break
    39. }
    40. }
    41. fmt.Println(stack1.arr)
    42. //出栈
    43. v, _ := stack1.pop(1)
    44. fmt.Println("---pop出栈---:", v)
    45. v, _ = stack1.pop(2)
    46. fmt.Println("---pop出栈---:", v)
    47. }
    48. func initStack() (stack *Stack) {
    49. stack = &Stack{
    50. Top1: -1,
    51. Top2: 10,
    52. arr: [10]int{},
    53. }
    54. return stack
    55. }
    56. //通过tag区分插入哪个队列
    57. func (s *Stack) push(v int, tag int) error {
    58. //判断栈是否满
    59. if s.Top2-s.Top1 == 1 {
    60. return errors.New("栈已满,无法插入数据")
    61. }
    62. if tag == 1 {
    63. s.Top1++ //栈A,栈顶+1
    64. s.arr[s.Top1] = v //入栈
    65. } else if tag == 2 {
    66. s.Top2-- //栈B,栈顶-1
    67. s.arr[s.Top2] = v //入栈
    68. } else {
    69. return errors.New("tag参数不合法, 需要传入1或2")
    70. }
    71. return nil
    72. }
    73. func (s *Stack) pop(tag int) (int, error) {
    74. var v int
    75. //判断栈是否为空
    76. if tag == 1 {
    77. if s.Top1 == -1 {
    78. return 0, errors.New("error: 栈A为空")
    79. }
    80. v = s.arr[s.Top1] //出栈
    81. s.Top1-- //栈A,栈顶-1
    82. } else if tag == 2 {
    83. if s.Top2 == 10 {
    84. return 0, errors.New("error: 栈B为空")
    85. }
    86. v = s.arr[s.Top2] //出栈
    87. s.Top2++ //栈B,栈顶+1
    88. }
    89. return v, nil
    90. }

    2.栈的链式存储实现

    链栈

    2.1链栈的结构体定义

    1. type LinkStack struct {
    2. data int
    3. next *LinkStack
    4. }

    2.2链栈的初始化

    1. func initLinkStack() (linkStack *LinkStack) {
    2. //初始化链栈,新建链栈头节点
    3. linkStack = &LinkStack{
    4. data: -1,
    5. next: nil,
    6. }
    7. return linkStack
    8. }

    2.3链栈的入栈

    1. func (s *LinkStack) push(v int) {
    2. //链栈可先不考虑栈满,因为目前没有对栈做限制
    3. pushNode := &LinkStack{
    4. data: v,
    5. next: nil,
    6. }
    7. pushNode.next = s.next //入栈节点的next指向头节点的next节点
    8. s.next = pushNode //头节点指向入栈节点
    9. }

    2.4链栈的出栈

    1. func (s *LinkStack) pop() (int, error) {
    2. var v int
    3. //判断栈是否为空
    4. if s.next == nil {
    5. return 0, errors.New("error: 栈为空")
    6. }
    7. tmpTop := s.next
    8. v = tmpTop.data //出栈,获取节点的元素值
    9. s.next = tmpTop.next //头节点指向原栈顶节点的下一个节点
    10. tmpTop.next = nil //原栈顶节点指向nil
    11. return v, nil
    12. }

    2.5链栈实现的完整代码

    1. package main
    2. import (
    3. "errors"
    4. "fmt"
    5. )
    6. type LinkStack struct {
    7. data int
    8. next *LinkStack
    9. }
    10. func main() {
    11. //初始化一个链栈
    12. fmt.Println("---初始化链栈---")
    13. linkStack1 := initLinkStack()
    14. //入栈
    15. fmt.Println("---入栈---")
    16. for i := 1; i <= 5; i++ {
    17. linkStack1.push(i)
    18. fmt.Printf("第%v次出栈, 值为:%v\n", i, i)
    19. }
    20. //出栈
    21. fmt.Println("---出栈---")
    22. for i := 1; i <= 6; i++ {
    23. v, err := linkStack1.pop()
    24. if err != nil {
    25. fmt.Println(err)
    26. break
    27. }
    28. fmt.Printf("第%v次出栈, 值为:%v\n", i, v)
    29. }
    30. }
    31. func initLinkStack() (linkStack *LinkStack) {
    32. //初始化链栈,新建链栈头节点
    33. linkStack = &LinkStack{
    34. data: -1,
    35. next: nil,
    36. }
    37. return linkStack
    38. }
    39. func (s *LinkStack) push(v int) {
    40. //链栈可先不考虑栈满,因为目前没有对栈做限制
    41. pushNode := &LinkStack{
    42. data: v,
    43. next: nil,
    44. }
    45. pushNode.next = s.next //入栈节点的next指向头节点的next节点
    46. s.next = pushNode //头节点指向入栈节点
    47. }
    48. func (s *LinkStack) pop() (int, error) {
    49. var v int
    50. //判断栈是否为空
    51. if s.next == nil {
    52. return 0, errors.New("error: 栈为空")
    53. }
    54. tmpTop := s.next
    55. v = tmpTop.data //出栈,获取节点的元素值
    56. s.next = tmpTop.next //头节点指向原栈顶节点的下一个节点
    57. tmpTop.next = nil //原栈顶节点指向nil
    58. return v, nil
    59. }

     

  • 相关阅读:
    和鲸ModelWhale与中科可控X系列异构加速服务器完成适配认证,搭载海光芯片,构筑AI算力底座
    【接口测试】Jmeter接口实战-Dubbo接口+造10W数据测试(详细)
    ClickHouse快速入门
    Visual Studio (VS2017)提交代码到Git服务器流程(GitCode)
    DiffuSEEG:一种基于stable diffusion 的SEEG数据补全方法
    详解二叉搜索树【C++实现】
    使用 NumPy 来模拟随机游走(Random Walk)
    Java流程控制09:练习题:打印三角形
    Android四大组件之BroadcastReceiver(四)
    07-mysql-SQL优化
  • 原文地址:https://blog.csdn.net/qq522044637/article/details/125856114