数据结构：Go 双向链表实现栈原理

代码

package main

import "fmt"

/*
   双向链表实现栈
*/
type Element interface{}

type Node struct {
    Data Element
    Next *Node
    Pre  *Node
}

type Stack struct {
    size int
    Top  *Node
}

// 新建一个栈
func Create() *Stack {
    return &Stack{size: 0, Top: new(Node)}
}

// 获取当前栈的大小
func (s *Stack) Len() int {
    return s.size
}

// 判断是否为空栈，true 为空， false 为非空
func (s *Stack) IsEmpty() bool {
    if s.Len() != 0 {
        return false
    }

    return true
}

// 入栈
func (s *Stack) Push(e Element) {
    node := &Node{Data: e, Next: nil, Pre: nil}
    p := s.Top

    // 如果链表为空
    if s.IsEmpty() {
        p.Pre = node
        node.Next = p

        s.size++
        return
    }

    // top节点的前一个节点的Next 指向新加入的节点。
    p.Pre.Next = node

    // 新加入节点指向 top 节点的前一个节点。
    node.Pre = p.Pre

    // 新加入节点的 Next 指向 Top 节点。
    node.Next = p

    // top 节点的 Pre 指向新加入的节点
    p.Pre = node

    s.size++

    return
}

// 将栈顶元素弹出栈，并返回被弹出的元素
func (s *Stack) Pop() (e Element) {
    if s.IsEmpty() {
        fmt.Println("stack is empty")
    }

    // 获取栈顶指针
    p := s.Top

    // 被弹出的元素，一定是 倒数第一个元素
    e = p.Pre.Data

    // 如果只有一个节点, 将 Top 节点的 Pre 指向 nil, 前一个节点的 Next 指向 nil
    if p.Pre.Pre == nil {

        p.Pre.Next = nil
        p.Pre = nil

        s.size--
        return
    }

    // 将 top 节点的 前一个节点 的前一个节点。也就是倒入第二个节点的 Next 指向 top 节点。
    // 将 top 节点的 Pre 指向 倒数第二个节点。

    p.Pre.Pre.Next = p
    p.Pre = p.Pre.Pre

    s.size--
    return
}

// 本着 先入后出的原则，我们从栈顶开始遍历 栈
func (s *Stack) Print() {
    if s.IsEmpty() {
        fmt.Println("stack is empty")
        return
    }

    p := s.Top.Pre
    iNode := s.Len()
    for p != nil {
        fmt.Printf("iNode == %d, data == %#v\n", iNode, p.Data)
        iNode--
        p = p.Pre
    }

    return
}

// 清空栈
func (s *Stack) Clear() {
    if s.IsEmpty() {
        fmt.Println("stack is empty")
    }

    s.Top.Pre = nil
    s.size = 0

    return
}

func main() {
    s := Create()
    s.Push(1)
    s.Push(2)
    s.Push(3)
    s.Push(4)

    s.Clear()
    s.Print()
}