Golang数据结构 - 2 - 栈

栈

在 上一部分 中，我们用 Go 实现了最常用的数据结构-数组，并实现了数组的添加元素、删除元素、数组遍历、数组 排序 和数组查找等功能。

在数组中我们可以实现任意位置的添加或删除元素，但是在某些场景中，需要我们对数据的添加或删除进行进一步的限制，于是就有了栈和队列。本章将使用Go来实现栈和栈的一些基本功能。

栈是一种运算受限的线性表，对栈中数据进行操作的时候需要遵循后进先出（LIFO）原则。在栈中对元素进行入栈或出栈操作的一端叫作 栈顶 ，另一端则为 栈底 。

本章中将基于Golang切片和链表两种实现方法来实现栈。

栈定义

首先定义栈接口，其中包含以下方法：

• Push(e ...Element)：添加若干元素到栈顶
• Pop() Element：弹出一个栈顶元素
• Peek() Element：返回栈顶元素，不弹出
• Empty() bool： 返回张是否为空
• Clear()：清空栈内所有元素
• Size() int：返回栈的大小

代码如下

type Element interface {
}

type Interface interface {
    // 添加若干元素到栈顶
    Push(e ...Element)

    // 弹出栈顶元素
    Pop() Element

    // 只返回不弹出栈顶元素
    Peek() Element

    // 栈是否为空
    Empty() bool

    // 清空栈元素
    Clear()

    // 返回栈的大小
    Size() int
}

向栈顶添加元素

1. 数组切片实现

// 向栈顶添加元素
func (s *ArrayStack) Push(e ...Element) {
   *s = append(*s, e...)
}

2. 链表实现

// 向栈顶添加元素
func (s *LinkedStack) Push(e ...Element) {
    for _, v := range e {
        n := s.Head.Next
        s.Head.Next = &node{
            Value: v,
            Next:  n,
        }
        s.size++
    }
}

元素出栈

1. 数组切片实现

// 弹出栈顶元素
func (s *ArrayStack) Pop() Element {
    if s.Empty() {
        return nil
    }
    ln := len(*s)
    // 获取栈顶元素
    val := (*s)[ln-1]

    // 弹出栈顶元素
    *s = (*s)[:ln-1]
    return val
}

2. 链表实现

// 弹出栈顶元素
func (s *LinkedStack) Pop() Element {
    if s.Empty() {
        return nil
    }
    first := s.Head.Next
    s.Head.Next = first.Next
    s.size--
    return first.Value
}

查看栈顶元素

1. 数组切片实现

// 查看栈顶元素
func (s *ArrayStack) Peek() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[len(*s)-1]
}

2. 链表实现

// 查看栈顶元素
func (s *LinkedStack) Peek() Element {
    if s.Empty() {
        return nil
    }
    return s.Head.Next.Value
}

查看栈大小

1. 数组切片实现

// 返回栈大小
func (s *ArrayStack) Size() int {
    return len(*s)
}

2. 链表实现

// 返回栈大小
// 由于使用了一个计数器，直接返回即可，时间复杂度O(1)
func (s *LinkedStack) Size() int {
    return s.size
}

检查栈是否为空

1. 数组切片实现

// 栈是否为空
func (s *ArrayStack) Empty() bool {
    return s.Size() == 0
}

2. 链表实现

// 栈是否为空
func (s *LinkedStack) Empty() bool {
    return s.Head.Next == nil
}

清空栈

1. 数组切片实现

// 清空栈
func (s *ArrayStack) Clear() {
    *s = ArrayStack{}
}

2. 链表实现

// 清空栈
func (s *LinkedStack) Clear() {
    s.Head.Next = nil
}

完整实现代码

package main

import "fmt"

type Element interface {
}

type Interface interface {
    // 添加若干元素到栈顶
    Push(e ...Element)

    // 弹出栈顶元素
    Pop() Element

    // 只返回不弹出栈顶元素
    Peek() Element

    // 栈是否为空
    Empty() bool

    // 清空栈元素
    Clear()

    // 返回栈的大小
    Size() int
}

type ArrayStack []Element

// 向栈顶添加元素
func (s *ArrayStack) Push(e ...Element) {
    *s = append(*s, e...)
}

// 弹出栈顶元素
func (s *ArrayStack) Pop() Element {
    if s.Empty() {
        return nil
    }
    ln := len(*s)
    // 获取栈顶元素
    val := (*s)[ln-1]

    // 弹出栈顶元素
    *s = (*s)[:ln-1]
    return val
}

// 查看栈顶元素
func (s *ArrayStack) Peek() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[len(*s)-1]
}

// 栈是否为空
func (s *ArrayStack) Empty() bool {
    return s.Size() == 0
}

// 清空栈
func (s *ArrayStack) Clear() {
    *s = ArrayStack{}
}

// 返回栈大小
func (s *ArrayStack) Size() int {
    return len(*s)
}

// 基于Slice实现构造栈
func NewArrayStack() Interface {
    return &ArrayStack{}
}

// 链表实现栈节点定义
type node struct {
    Value Element
    Next  *node
}

// 链表实现栈
type LinkedStack struct {
    Head *node
    size int
}

// 向栈顶添加元素
func (s *LinkedStack) Push(e ...Element) {
    for _, v := range e {
        n := s.Head.Next
        s.Head.Next = &node{
            Value: v,
            Next:  n,
        }
        s.size++
    }
}

// 弹出栈顶元素
func (s *LinkedStack) Pop() Element {
    if s.Empty() {
        return nil
    }
    first := s.Head.Next
    s.Head.Next = first.Next
    s.size--
    return first.Value
}

// 查看栈顶元素
func (s *LinkedStack) Peek() Element {
    if s.Empty() {
        return nil
    }
    return s.Head.Next.Value
}

// 栈是否为空
func (s *LinkedStack) Empty() bool {
    return s.Head.Next == nil
}

// 清空栈
func (s *LinkedStack) Clear() {
    s.Head.Next = nil
}

// 返回栈大小
// 由于使用了一个计数器，直接返回即可，时间复杂度O(1)
func (s *LinkedStack) Size() int {
    return s.size
}

// 链表实现栈构造
func NewLinkedStack() Interface {
    return &LinkedStack{
        Head: &node{},
    }
}

func main() {
    //s := NewStack()
    s := NewLinkedStack()
    fmt.Println("Empty", s.Empty())

    s.Push(1, 2, 3, 4, 5, 6, 7, 8, 9)
    fmt.Println("Push 1,2,3,4,5")
    fmt.Println("Size:", s.Size())

    fmt.Println("Peek:", s.Peek())

    fmt.Println("Pop:", s.Pop(), s.Pop(), s.Pop())
    s.Clear()
    fmt.Println("Clear Empty:", s.Empty())

}

运行结果

Empty true
Push 1,2,3,4,5
Size: 9
Peek: 9
Pop: 9 8 7
Clear Empty: true

Process finished with exit code 0