数据结构第二讲——栈

本节内容较上节较为简单

一、定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

百度百科

二、解释

你可以把栈想象成一个书堆。

当你想从书堆里拿起随便一本书读的时候，拿哪一本？当然是那书堆顶部的那本书。

当你想把这本书放回去的时候，放在哪里最方便？当然是书堆顶部。

只不过栈强制你从顶部拿书/取书而已。

我们将放书的动作叫做push，取书的动作叫做pop。

书堆也有最大承载度，超过这个最大承载度的时候，我们将这种状态称为堆栈溢出（stack overflow）。

堆栈溢出通常是由于你的程序使用了超过栈内存（根据电脑配置是1M~8M之间）极限。

三、代码

同上一讲我们先来写伪代码

结构 栈 {
    属性1：元素列表
}
​
方法 push(元素) {
    元素列表.新增(元素)
}
​
方法 pop() -> 栈顶元素 {
    如果 堆栈 为空 {
        报错(堆栈为空)
    }
    变量 tail = 元素列表末尾的值
    删除元素列表末尾元素
    返回 tail
}

根据伪代码写出真实码：

var ErrStackEmpty = errors.New("stack is empty")
​
type Stack struct {
    Elements []int // 元素列表
}
​
// 判断堆栈是否为空
func (s Stack) IsEmpty() bool {
    return s.Size() == 0
}
​
// 返回堆栈大小
func (s Stack) Size() int {
    return len(s.Elements)
}
​
func (s *Stack) Push(data int) {
    s.Elements = append(s.Elements, data)
}
​
func (s *Stack) Pop() int {
    elements := s.Elements
    // 如果堆栈为空
    if s.IsEmpty() {
        // 报错(堆栈为空)
        panic(ErrStackEmpty)
    }
    // 删除元素列表末尾元素
    s.Elements = s.Elements[0 : len(s.Elements)-1]
    // 返回堆栈原始的末尾元素
    return elements[len(elements)-1]
}
​
func main() {
    s := Stack{Elements: []int{1, 2, 3}}
    fmt.Println(s)
}

我们再形象化输出：

func (s Stack) String() string {
    str := ""
    for i := range s.Elements {
        str += fmt.Sprintf("|\t%d\t|\n", s.Elements[len(s.Elements)-i-1])
    }
    str += "+--------+"
    return str
}

输出（可能画得不太好）：

|   3   |
|   2   |
|   1   |
+--------+

点此在线运行以上代码

8/25 14:20 置顶一下