栈的实现（数组和链表）

GitHub：github.com/bllon/Data-structure-an...

数组实现

package main

/**
    数组实现栈
 */

import "fmt"

const maxLen = 5

type Stack struct {
    data [maxLen]interface{}
    index int
}

// NewStack 初始化一个栈
func NewStack() Stack {
    return Stack{
        data: [maxLen]interface{}{},
        index: -1,
    }
}

// Push 入栈
func (s *Stack) Push(el interface{}) error {
    if s.Len() == maxLen {
        return fmt.Errorf("stack full")
    }
    s.index++
    s.data[s.index] = el
    return nil
}

// Pop 出栈
func (s *Stack) Pop() (interface{}, error) {
    if s.IsEmpty() {
        return nil, fmt.Errorf("stack empty")
    } else {
        res := s.data[s.index]
        s.index--
        return res, nil
    }
}

// IsEmpty 判断栈是否为空
func (s *Stack) IsEmpty() bool {
    return s.index == -1
}

// Top 获取栈顶
func (s *Stack) Top() interface{} {
    return s.data[s.index]
}

// Len 获取栈长
func (s *Stack) Len() int {
    return s.index + 1
}

// Display 打印栈中元素
func (s *Stack) Display() {
    if s.IsEmpty() {
        fmt.Println("stack is empty")
    } else {
        for i:=0; i<s.Len(); i++ {
            fmt.Println(s.data[i])
        }
    }
}

func main() {
    stack := NewStack()
    fmt.Println("stack len is ", stack.Len())
    stack.Display()
    _, err := stack.Pop()
    fmt.Println(err)

    stack.Push(123)
    stack.Push("哈哈哈")
    stack.Push(3.14)
    stack.Push(struct {}{})
    err = stack.Push(4)
    fmt.Println(err)
    err = stack.Push(5)
    fmt.Println(err)

    stack.Display()
    fmt.Println("stack len is ", stack.Len())

    //el, _ := stack.Pop()
    //fmt.Println("stack pop el is ", el)
    //el, _ = stack.Pop()
    //fmt.Println("stack pop el is ", el)
    //stack.Display()
    //fmt.Println("stack len is ", stack.Len())
}

链表实现

package main

/**
    链表实现栈
*/

import "fmt"

const maxLen = 5

type Stack struct {
    head *StackNode
    len int
}
type StackNode struct {
    next *StackNode
    data interface{}
}

// NewStack 初始化一个栈
func NewStack() Stack {
    return Stack{
        head: nil,
        len: 0,
    }
}

// Push 入栈
func (s *Stack) Push(el interface{}) error {
    if s.Len() == maxLen {
        return fmt.Errorf("stack full")
    }
    if s.head == nil {
        s.head = &StackNode{
            next: nil,
            data: el,
        }
    } else {
        node := &StackNode{
            next: s.head,
            data: el,
        }
        s.head = node
    }
    s.len++
    return nil
}

// Pop 出栈
func (s *Stack) Pop() (interface{}, error) {
    if s.IsEmpty() {
        return nil, fmt.Errorf("stack empty")
    } else {
        res := s.head.data
        s.head = s.head.next
        return res, nil
    }
}

// IsEmpty 判断栈是否为空
func (s *Stack) IsEmpty() bool {
    return s.len == 0
}

// Top 获取栈顶
func (s *Stack) Top() interface{} {
    return s.head.data
}

// Len 获取栈长
func (s *Stack) Len() int {
    return s.len
}

// Display 打印栈中元素
func (s *Stack) Display() {
    if s.IsEmpty() {
        fmt.Println("stack is empty")
    } else {
        p := s.head
        for p != nil {
            fmt.Println(p.data)
            p = p.next
        }
    }
}

func main() {
    stack := NewStack()
    fmt.Println("stack len is ", stack.Len())
    stack.Display()
    _, err := stack.Pop()
    fmt.Println(err)

    stack.Push(123)
    stack.Push("哈哈哈")
    stack.Push(3.14)
    stack.Push(struct {}{})
    err = stack.Push(4)
    fmt.Println(err)
    err = stack.Push(5)
    fmt.Println(err)

    stack.Display()
    fmt.Println("stack len is ", stack.Len())

    //el, _ := stack.Pop()
    //fmt.Println("stack pop el is ", el)
    //el, _ = stack.Pop()
    //fmt.Println("stack pop el is ", el)
    //stack.Display()
    //fmt.Println("stack len is ", stack.Len())
}

本作品采用《CC 协议》，转载必须注明作者和本文链接