一、问题介绍

第一部分介绍栈的基本概念,以及使用Go语言实现基于linked-list的下压堆栈。

二、关于栈的描述

简单的说,栈是一种(LIFO)*先进后出*的数据结构。虽然简单,但是在实际开发中却用处巨大,下面我们首先列出对于栈我们可以操作的基本API:

  • push(Item item)
  • pop() Item
  • isEmpty() bool
  • size() int

基本的操作接口有了,因为比较简单,就不多介绍了,接下来就直接上代码(本篇基于链表实现):

package main

import (
    "fmt"
)

type Node struct {
    Data interface{}
    Next *Node
}

type Stack struct {
    First *Node
    Num   int
}

func (s *Stack) Push(data interface{}) {
    oldFirst := s.First
    d := new(Node)
    d.Data = data
    s.First = d
    d.Next = oldFirst
    s.Num++
}

func (s *Stack) Pop() interface{} {
    first := s.First
    s.First = first.Next
    s.Num--
    return first.Data
}

func (s *Stack) IsEmpty() bool {
    return s.First == nil
}

func (s *Stack) Size() int {
    return s.Num
}

func main() {
    var s *Stack = new(Stack)
    fmt.Println(s.IsEmpty())
    fmt.Println(s.Size())
    s.Push("a")
    fmt.Println(s.Size())
    s.Push("b")
    fmt.Println(s.Size())
    s.Push("c")
    s.Push(10000)
    fmt.Println(s.Pop())
    fmt.Println(s.IsEmpty())
    fmt.Println(s.Pop())
    fmt.Println(s.Size())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Size())
    fmt.Println(s.IsEmpty())
    fmt.Println(s.Pop())

}

上述实现中主要用到了两个结构,一个是Node struct,一个是Stack struct,其中Node表示链表中的一个节点,而Stack则是栈的定义。基于链表的栈引用着指向first第一个节点的指针,因此我们可以看到Stack结构的成员包括一个First的Node类型的指针,除此之外还有一个Num表示节点数目。下面主要介绍Push操作和Pop操作:

  • Push操作只需要创建新节点,然后将新节点指向Stack的第一个节点,新节点的Next指向之前的第一个节点。

  • Pop操作则更简单,只需要将Stack的第一个节点的下一个节点指向Stack的第一个节点。并返回之前的第一个节点需要的数据。

时间复杂度

对于push和pop操作,时间复杂度都为O(1)

总结

介绍了栈以及通过Go语言实现了基于链表的栈,下篇将继续介绍基于数组实现的栈。

##文档信息