栈

在上一部分中，我们用Go实现了最常用的数据结构-数组，并实现了数组的添加元素、删除元素、数组遍历、数组排序和数组查找等功能。

在数组中我们可以实现任意位置的添加或删除元素，但是在某些场景中，需要我们对数据的添加或删除进行进一步的限制，于是就有了栈和队列。本章将使用Go来实现栈和栈的一些基本功能。

栈是一种运算受限的线性表，对栈中数据进行操作的时候需要遵循后进先出（LIFO）原则。在栈中对元素进行入栈或出栈操作的一端叫作栈顶，另一端则为栈底。

本章中将基于Golang切片和链表两种实现方法来实现栈。

栈定义

首先定义栈接口，其中包含以下方法：

• Push(e ...Element)：添加若干元素到栈顶
• Pop() Element：弹出一个栈顶元素
• Peek() Element：返回栈顶元素，不弹出
• Empty() bool： 返回张是否为空
• Clear()：清空栈内所有元素
• Size() int：返回栈的大小

代码如下

type Element interface { } type Interface interface { // 添加若干元素到栈顶 Push(e ...Element) // 弹出栈顶元素 Pop() Element // 只返回不弹出栈顶元素 Peek() Element // 栈是否为空 Empty() bool // 清空栈元素 Clear() // 返回栈的大小 Size() int } 

向栈顶添加元素

1. 数组切片实现

// 向栈顶添加元素 func (s *ArrayStack) Push(e ...Element) { *s = append(*s, e...) } 

2. 链表实现

// 向栈顶添加元素 func (s *LinkedStack) Push(e ...Element) { for _, v := range e { n := s.Head.Next s.Head.Next = &node{ Value: v, Next: n, } s.size++ } } 

元素出栈

1. 数组切片实现

// 弹出栈顶元素 func (s *ArrayStack) Pop() Element { if s.Empty() { return nil } ln := len(*s) // 获取栈顶元素 val := (*s)[ln-1] // 弹出栈顶元素 *s = (*s)[:ln-1] return val } 

2. 链表实现

// 弹出栈顶元素 func (s *LinkedStack) Pop() Element { if s.Empty() { return nil } first := s.Head.Next s.Head.Next = first.Next s.size-- return first.Value } 

查看栈顶元素

1. 数组切片实现

// 查看栈顶元素 func (s *ArrayStack) Peek() Element { if s.Empty() { return nil } return (*s)[len(*s)-1] } 

2. 链表实现

// 查看栈顶元素 func (s *LinkedStack) Peek() Element { if s.Empty() { return nil } return s.Head.Next.Value } 

查看栈大小

1. 数组切片实现

// 返回栈大小 func (s *ArrayStack) Size() int { return len(*s) } 

2. 链表实现

// 返回栈大小 // 由于使用了一个计数器，直接返回即可，时间复杂度O(1) func (s *LinkedStack) Size() int { return s.size } 

检查栈是否为空

1. 数组切片实现

// 栈是否为空 func (s *ArrayStack) Empty() bool { return s.Size() == 0 } 

2. 链表实现

// 栈是否为空 func (s *LinkedStack) Empty() bool { return s.Head.Next == nil } 

清空栈

1. 数组切片实现

// 清空栈 func (s *ArrayStack) Clear() { *s = ArrayStack{} } 

2. 链表实现

// 清空栈 func (s *LinkedStack) Clear() { s.Head.Next = nil } 

完整实现代码

package main import "fmt" type Element interface { } type Interface interface { // 添加若干元素到栈顶 Push(e ...Element) // 弹出栈顶元素 Pop() Element // 只返回不弹出栈顶元素 Peek() Element // 栈是否为空 Empty() bool // 清空栈元素 Clear() // 返回栈的大小 Size() int } type ArrayStack []Element // 向栈顶添加元素 func (s *ArrayStack) Push(e ...Element) { *s = append(*s, e...) } // 弹出栈顶元素 func (s *ArrayStack) Pop() Element { if s.Empty() { return nil } ln := len(*s) // 获取栈顶元素 val := (*s)[ln-1] // 弹出栈顶元素 *s = (*s)[:ln-1] return val } // 查看栈顶元素 func (s *ArrayStack) Peek() Element { if s.Empty() { return nil } return (*s)[len(*s)-1] } // 栈是否为空 func (s *ArrayStack) Empty() bool { return s.Size() == 0 } // 清空栈 func (s *ArrayStack) Clear() { *s = ArrayStack{} } // 返回栈大小 func (s *ArrayStack) Size() int { return len(*s) } // 基于Slice实现构造栈 func NewArrayStack() Interface { return &ArrayStack{} } // 链表实现栈节点定义 type node struct { Value Element Next *node } // 链表实现栈 type LinkedStack struct { Head *node size int } // 向栈顶添加元素 func (s *LinkedStack) Push(e ...Element) { for _, v := range e { n := s.Head.Next s.Head.Next = &node{ Value: v, Next: n, } s.size++ } } // 弹出栈顶元素 func (s *LinkedStack) Pop() Element { if s.Empty() { return nil } first := s.Head.Next s.Head.Next = first.Next s.size-- return first.Value } // 查看栈顶元素 func (s *LinkedStack) Peek() Element { if s.Empty() { return nil } return s.Head.Next.Value } // 栈是否为空 func (s *LinkedStack) Empty() bool { return s.Head.Next == nil } // 清空栈 func (s *LinkedStack) Clear() { s.Head.Next = nil } // 返回栈大小 // 由于使用了一个计数器，直接返回即可，时间复杂度O(1) func (s *LinkedStack) Size() int { return s.size } // 链表实现栈构造 func NewLinkedStack() Interface { return &LinkedStack{ Head: &node{}, } } func main() { //s := NewStack() s := NewLinkedStack() fmt.Println("Empty", s.Empty()) s.Push(1, 2, 3, 4, 5, 6, 7, 8, 9) fmt.Println("Push 1,2,3,4,5") fmt.Println("Size:", s.Size()) fmt.Println("Peek:", s.Peek()) fmt.Println("Pop:", s.Pop(), s.Pop(), s.Pop()) s.Clear() fmt.Println("Clear Empty:", s.Empty()) } 

运行结果

Empty true Push 1,2,3,4,5 Size: 9 Peek: 9 Pop: 9 8 7 Clear Empty: true Process finished with exit code 0