_______.___________. ___ ______ __ ___
/ | | / \ / || |/ /
| (----`---| |----` / ^ \ | ,----'| ' /
\ \ | | / /_\ \ | | | <
.----) | | | / _____ \ | `----.| . \
|_______/ |__| /__/ \__\ \______||__|\__\
在上一章中，我们用Go实现了最常用的数据结构-数组，并实现了数组的添加元素、删除元素、数组遍历、数组排序和数组查找等功能。
在数组中我们可以实现任意位置的添加或删除元素，但是在某些场景中，需要我们对数据的添加或删除进行进一步的限制，于是就有了栈和队列。本章将使用Go来实现栈和栈的一些基本功能。
栈是一种运算受限的线性表，对栈中数据进行操作的时候需要遵循后进先出（LIFO）原则。在栈中对元素进行入栈或出栈操作的一端叫作
栈顶，另一端则为栈底。
本章中将基于Golang数组切片和链表两种实现方法来实现栈以及栈的基本操作。
栈定义
首先定义栈接口，其中包含以下方法：
- Push(e ...Element)：添加若干元素到栈顶
- Pop() Element：弹出一个栈顶元素
- Peek() Element：返回栈顶元素，不弹出
- Empty() bool： 返回张是否为空
- Clear()：清空栈内所有元素
- Size() int：返回栈的大小
代码如下
type Element interface {
}
type Stack interface {
// 添加若干元素到栈顶
Push(e ...Element)
// 弹出栈顶元素
Pop() Element
// 只返回不弹出栈顶元素
Peek() Element
// 栈是否为空
Empty() bool
// 清空栈元素
Clear()
// 返回栈的大小
Size() int
}
向栈顶添加元素
- 数组切片实现
// 向栈顶添加元素
func (s *ArrayStack) Push(e ...Element) {
*s = append(*s, e...)
}
- 链表实现
// 向栈顶添加元素
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 *ArrayStack) Pop() Element {
if s.Empty() {
return nil
}
ln := len(*s)
// 获取栈顶元素
val := (*s)[ln-1]
// 弹出栈顶元素
*s = (*s)[:ln-1]
return val
}
- 链表实现
// 弹出栈顶元素
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 *ArrayStack) Peek() Element {
if s.Empty() {
return nil
}
return (*s)[len(*s)-1]
}
- 链表实现
// 查看栈顶元素
func (s *LinkedStack) Peek() Element {
if s.Empty() {
return nil
}
return s.Head.Next.Value
}
查看栈大小
- 数组切片实现
// 返回栈大小
func (s *ArrayStack) Size() int {
return len(*s)
}
- 链表实现
// 返回栈大小
// 由于使用了一个计数器，直接返回即可，时间复杂度O(1)
func (s *LinkedStack) Size() int {
return s.size
}
检查栈是否为空
- 数组切片实现
// 栈是否为空
func (s *ArrayStack) Empty() bool {
return s.Size() == 0
}
- 链表实现
// 栈是否为空
func (s *LinkedStack) Empty() bool {
return s.Head.Next == nil
}
清空栈
- 数组切片实现
// 清空栈
func (s *ArrayStack) Clear() {
*s = ArrayStack{}
}
- 链表实现
// 清空栈
func (s *LinkedStack) Clear() {
s.Head.Next = nil
}
完整实现代码
package main
import "fmt"
type Element interface {
}
type Stack 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() Stack {
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() Stack {
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
网友评论