栈
栈(stack)是一种遵循先入后出逻辑的线性数据结构。
我们可以把它想象成吃零食的薯片桶，打开薯片桶之后，每次只能拿到最上面的薯片。如图所示，我们把堆叠元素的顶部称为”栈顶“，底部元素称为”栈底“。将把元素添加到栈顶的操作叫做“入栈",删除栈顶元素的操作叫做“出栈”。
栈操作
栈的常用操作
通常情况下，我们可以直接使用编程语言内置的栈类。 然而某些语言可能并不提供专门的栈类，这时我们可以将该语言的“数组”或“链表”当作栈来使用，并在逻辑上忽略栈无关的操作。
栈的常用操作有
- push(), 元素入栈，将元素添加至栈顶，时间复杂度O(1)
- pop(), 元素出栈，将栈顶元素删除，时间复杂度尾O(1)
- peek(),访问栈顶元素，时间复杂度O(1)
var stack []int
// 元素入栈
stack = append(stack, 1)
stack = append(stack,2)
// 元素出栈
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 访问栈顶元素
peek := stack[len(stack)-1]
// 获取栈的长度
size := len(stack)
// 是否为空判断
isEmpty := len(stack) == 0
栈的实现
栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素，然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表.换句话说，我们可以屏蔽数组或链表的部分无关操作，使其对外表现得逻辑符合栈的特性。
1. 基于链表的实现
使用链表实现栈时，我们可以将链表头节点视为栈顶，尾节点视为栈底。因为链表是顺序访问的，头节点是我们最先访问的元素，尾节点是最后访问的元素，这个栈的特性一致。
对于入栈操作，我们只需将元素插入链表头部，这种插入方法成为”头插法“。
对于出栈操作，我们只需将头节点从链表中删除。
package main
import (
"container/list"
"fmt"
)
type Stack struct {
*list.List
}
func NewStack() *Stack {
return &Stack{
List: list.New(),
}
}
// 入栈，将元素添加至栈顶，也就是链表的头节点
func (s *Stack) Push(element interface{}) {
s.List.PushBack(element)
}
// 出栈，将栈顶元素删除，
func (s *Stack) Pop() interface{} {
if s.IsEmpty() {
return nil
}
e := s.List.Back()
s.List.Remove(e)
return e.Value
}
func (s *Stack) Peek() interface{} {
return s.List.Front()
}
func (s *Stack) Size() int {
return s.List.Len()
}
func (s *Stack) IsEmpty() bool {
return s.List.Len() == 0
}
func main() {
var s = NewStack()
s.Push(1)
s.Push(2)
s.Push(3)
fmt.Println(s.Pop(), s.Size())
fmt.Println(s.Pop(), s.Size())
fmt.Println(s.Pop(), s.Size())
}
/* 输出结果
3
3 2
2 1
1 0
*/
1. 基于数组的实现
使用数组实现栈时，我们可以将数组的尾部作为栈顶，入栈和出栈操作均在数组尾部进行。时间复杂度为O(1)
type StackArray struct {
data []interface{}
}
func NewStackArray() *StackArray {
return &StackArray{}
}
func (s *StackArray) Push(element interface{}) {
s.data = append(s.data, element)
}
// 出栈，将栈顶元素删除，
func (s *StackArray) Pop() interface{} {
if s.IsEmpty() {
return nil
}
e := s.data[len(s.data)-1]
s.data = s.data[:len(s.data)-1]
return e
}
func (s *StackArray) Peek() interface{} {
if s.IsEmpty() {
return nil
}
return s.data[len(s.data)-1]
}
func (s *StackArray) Size() int {
return len(s.data)
}
func (s *StackArray) IsEmpty() bool {
return len(s.data) == 0
}
两种实现对比
时间效率
在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。如果入栈时超出数组容量，会触发扩容机制，导致该入栈操作的时间复杂度变为O(n)。
在基于链表的实现中，链表的扩容十分灵活，不会出现扩容导致的效率地下问题。但是入栈操作需要初始化节点对象并修改指针，因此效率相对较低。
综上所述，当入栈与出栈操作的元素是基本数据类型时，我们可以得出以下结论：
- 基于数组的实现的栈在触发扩容机制时效率会降低，但由于扩容时低频操作，因此平均效率更高。
- 基于链表实现的栈可以提供更加稳定的效率表现。
栈的典型应用
程序内存管理
每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息，在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。
网友评论