数据结构-栈

栈（stack）是一种遵循先入后出逻辑的线性数据结构

基于链表的栈

package stack

type arrayStack struct {
	data []int
}

/* 初始化栈 */
func newArrayStack() *arrayStack {
	return &arrayStack{
		// 设置栈的长度为 0，容量为 16
		data: make([]int, 0, 16),
	}
}

/* 栈的长度 */
func (s *arrayStack) size() int {
	return len(s.data)
}

/* 栈是否为空 */
func (s *arrayStack) isEmpty() bool {
	return s.size() == 0
}

/* 入栈 */
func (s *arrayStack) push(value int) {
	s.data = append(s.data, value)
}

/* 出栈 */
func (s *arrayStack) pop() any {
	val := s.peek()
	s.data = s.data[:len(s.data)-1]
	return val
}
func (s *arrayStack) peek() any {
	if s.isEmpty() {
		return nil
	}
	val := s.data[len(s.data)-1]
	return val
}

/* 获取 toSlice 用于打印 */
func (s *arrayStack) toSlice() []int {
	return s.data
}

基于数组的栈

package stack

import "container/list"

/* 基于链表实现的栈 */
type linkedListStack struct {
	// 使用内置包 list 来实现栈
	data *list.List
}

/* 初始化栈 */
func newLinkedListStack() *linkedListStack {
	return &linkedListStack{
		data: list.New(),
	}
}

/* 入栈 */
func (s *linkedListStack) push(value int) {
	s.data.PushBack(value)
}

/* 判断栈是否为空 */
func (s *linkedListStack) isEmpty() bool {
	return s.data.Len() == 0
}

/* 出栈 */
func (s *linkedListStack) pop() any {
	if s.isEmpty() {
		return nil
	}
	e := s.data.Back()
	s.data.Remove(e)
	return e.Value
}
func (s *linkedListStack) peek() any {
	if s.isEmpty() {
		return nil
	}
	return s.data.Back().Value
}
func (s *linkedListStack) len() any {
	return s.data.Len()
}

/* 获取 List 用于打印 */
func (s *linkedListStack) toList() *list.List {
	return s.data
}

俩种对比

  1. 时间复杂度：
    • 基于数组，有缓存本地性，但是超出数组容量，触发扩容
    • 基于链表，入栈，需要查找指针节点
  2. 空间复杂度：
    • 基于数组，会有空间浪费
    • 由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大

Ref