Golang 数据结构之【4.5共享栈】

图片来源于《大话数据结构》

图片来源于《大话数据结构》

两栈共享空间的结构的golang代码如下:

package stack

import (
    "fmt"
    "errors"
    )

//共享栈

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

type DoubleStack struct {
    data [MaxDoubleSize]SElemType
    top1 int    //栈1栈顶指针
    top2 int    //栈2栈顶指针
}

// 初始化一个空栈
func (d *DoubleStack) InitStack ()  {
    d.top1 = -1
    d.top2 = MaxDoubleSize
}

// 把d置为空栈
func (d *DoubleStack) ClearStack()  {
    d.top1 = -1
    d.top2 = MaxDoubleSize
}

// 若栈l为空栈，则返回true 否则返回false
func (d *DoubleStack) IsEmpty() bool {
    if d.top1 == -1 && d.top2 ==MaxDoubleSize {
        return true
    } else {
        return false
    }
}

// 返回s的元素个数，即栈的长度
func (d *DoubleStack) Length() int {
    return (d.top1 + 1) + (MaxDoubleSize-1-d.top2)
}


// 插入元素e为新的栈顶元素，栈满返回error
func (d *DoubleStack) Push(e SElemType, stackNum int) error {
    if d.top1 + 1 == d.top2 {
        return errors.New("stack is full")
    }

    // 栈1有元素进栈
    if stackNum == 1 {
        d.top1++
        d.data[d.top1] = e
    } else if stackNum ==2 {  // 栈2有元素进栈
        d.top2--
        d.data[d.top2] = e
    }

    return nil
}

// 若栈不空，则删除d的栈顶元素  用e返回其值,否则返回error
func (d *DoubleStack) Pop(stackNum int) (e SElemType,err error) {
    if stackNum == 1 {
        if d.top1 == -1 {
            return 0, errors.New("stack is empty")  //栈1为空，已溢出
        }
        e = d.data[d.top1]
        d.top1--
    } else if stackNum == 2 {
        if d.top2 == MaxDoubleSize {
            return 0, errors.New("stack is empty") //栈2为空，已溢出
        }
        e = d.data[d.top2]
        d.top2++
    }
    return
}

//遍历栈
func (d *DoubleStack) Traverse() {
    for i:=0; i <= d.top1  ; i++ {
        fmt.Println(d.data[i])
    }
    for i:=d.top2; i < MaxDoubleSize  ; i++ {
        fmt.Println(d.data[i])
    }
}

func TestDoubleStack()  {
    var s DoubleStack
    s.InitStack()
    for j:=1;j <= 5 ; j++ {
        s.Push(SElemType(j),1)
    }
    for j:=MaxDoubleSize;j >= MaxDoubleSize-2 ; j-- {
        s.Push(SElemType(j),1)
    }
    fmt.Println("栈中的元素为：")
    s.Traverse()
    e, _ := s.Pop(1)
    fmt.Println("弹出的元素为：", e)
    fmt.Println("栈是否为空：", s.IsEmpty())
    fmt.Println("栈的长度：", s.Length())
    s.ClearStack()
    fmt.Println("栈是否为空：", s.IsEmpty())
}