Go转型——数据结构初级（四）栈和队列

1.栈和队列

栈和队列是两种常用的线性结构，从数据结构角度来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作实现性别操作的子集，他们是操作受限的线性表，因此也被称为限定的数据结构。但从数据类型角度来看，他们是和线性表大不相同。

栈：是限定仅在表尾进行插入或删除操作的线性表。对于栈来说，表尾一端有特殊含义，称为栈顶，相应的标头段称之为栈底。不含任何元素的栈被称作空栈。

假设S=（a(1),a(2),a(3),.......a(n)），我们称a(1)为栈底元素，a(n)为栈顶元素。进栈顺序应为a(1),a(2),a(3),.......a(n)，退栈的顺序第一个元素应为栈顶元素。换句话说，栈的修改是按照后进先出的原则进行的，因此，栈又称之为后进先出线性表（简称LIFO结构）。

站的抽象数据类型定义如下：

2.栈的表示和实现

和线性表类似，展业有两种存储表示方法。

顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元来依次存储从栈底到栈顶的数据元素，同时还设置指针top指示栈顶元素在顺序栈中的位置，以top=0来表示空栈。还有，由于栈在实际使用中大小不易估算，所以我们初始化设空栈时不应限定栈的最大容量，应该给栈分配一个基本容量，然后在应用过程中，当栈的空间不足时，再逐段扩大。

链栈：操作方式与线性链表类似，不移动元素只更改指针域内容。

3.栈的实际应用

package main



import (
    "log"
    "fmt"
)

type Stack struct {
    size int64 //栈的容量
    top int64 //栈顶
    data []interface{}
}

func MakeStack( size int64)  Stack{

    s :=Stack{}
    s.size=size
    s.data =make([]interface{},size)

    return s
}

//入栈，空间不足，逐段升高

func (s *Stack) Push(e interface{})  bool{


    if  s.IsFull(){
        log.Printf("栈满，无法入栈")
     return false

    }

    s.data[s.top]=e
    fmt.Println(s.top)
    s.top++

    return true
}
//出栈，栈顶降低
func (s *Stack) Pop()  (r interface{},err error){

    if s.IsEmpty() {
        err =fmt.Errorf("栈已空，无法完成出栈")
        log.Printf("栈已空，无法完成出栈")
        return
    }
    s.top--
    r =s.data[s.top]
    return
}




//判断栈是否满
func (s *Stack) IsFull()  bool{

    return s.top==s.size
}

//判断栈是否为空
func (s *Stack) IsEmpty()  bool{

    return s.top==0
}

func (s *Stack) Traverse(fn func(r interface{}),goorto bool)  {


    //go true遍历进栈   false 遍历出栈
    if goorto {
  var i  int64= 0
        for ;i<s.top;i++ {
            fn(s.data[i])

        }


    }else{

        for i:=s.top-1;i>=0;i-- {
            fn(s.data[i])
        }
    }

}


//进栈出栈试验
//求将十进制1348转化为八进制

func TestStack()  {


    var fn_c = func(n int) {

        s :=MakeStack(10)

        for   {
            if n==0 {
                break
            }
            s.Push(n%8)
            n =n/8

        }
        s.Traverse(func(r interface{}) {
            fmt.Print(r)
        },false)


    }

    fn_c(1348)

}


func main() {

    TestStack()

}

这个程序还是有问题，将元素入栈时，会覆盖第一个元素，最后栈中只留下一个2，求大神解答