Golang 数据结构之【4.4顺序栈】

由于 进栈和出栈没有涉及任何循环语句,因此时间复杂度均是 0(1)
golang代码实现如下:

package main

//顺序栈
import (
    "errors"
    "fmt"
)


const MaxSize  = 20 //存储空间初始分配量

type SElemType int // SElemType类型根据实际情况而定,这里假设为int

type SqStack struct {
    data [MaxSize]SElemType //栈的数据容量,用数组实现。如果不确定最大值可以用slice类型,这里我选择用数组。
    top int //栈顶指针
}

// 初始化一个空栈
func (s *SqStack) InitStack ()  {
    s.top = -1
}

// 把s置为空栈
func (s *SqStack) ClearStack()  {
    s.top = -1
}
// 若栈l为空栈,则返回true 否则返回false
func (s *SqStack) IsEmpty() bool {
    if s.top == -1 {
        return true
    } else {
        return false
    }
}


// 返回s的元素个数,即栈的长度
func (s *SqStack) Length() int {
    return s.top + 1
}

// 若栈不空,则用e返回s的栈顶元素,否则返回error
func (s *SqStack) GetTop() (e SElemType,err error) {
    if s.top == -1 {
        return 0, errors.New("stack is empty")
    } else {
        return s.data[s.top], nil
    }
}

// 插入元素e为新的栈顶元素,栈满返回error
func (s *SqStack) Push(e SElemType) error {
    if s.top == MaxSize -1 {
        return errors.New("stack is full")
    }

    s.top++     // 栈顶指针增加一
    s.data[s.top] = e // 将新插入的元素赋值给栈顶空间
    return nil
}

// 若栈不空,则删除s的栈顶元素  用e返回其值,否则返回error
func (s *SqStack) Pop() (e SElemType,err error) {
    if s.top == -1 {
        return 0, errors.New("stack is empty")
    } else {
        e = s.data[s.top]
        s.top--
        return
    }
}

// 遍历栈
func (s *SqStack) Traverse() {
    for i:=0; i <= s.top  ; i++ {
        fmt.Println(s.data[i])
    }
}

func main()  {
    var s SqStack
    s.InitStack()
    for j:=1;j <= 10 ; j++ {
        s.Push(SElemType(j))
    }
    fmt.Println("栈中的元素为:")
    s.Traverse()
    e, _ := s.Pop()
    fmt.Println("弹出的元素为:", e)
    fmt.Println("栈是否为空:", s.IsEmpty())
    fmt.Println("栈的长度:", s.Length())
    elemType, _ := s.GetTop()
    fmt.Println("栈的顶元素:", elemType)
    s.ClearStack()
    fmt.Println("栈是否为空:", s.IsEmpty())
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。