实现常用数据结构(队列与栈)

栈

定义

栈(Stack) 是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端
进行插入和删除操作

基础操作

• 初始化
• 判断是否为空
• 进栈
• 出栈
• 输出栈的大小

存储结构

• 顺序结构
• 链式结构

顺序实现

由于可以使用 golang 自带的切片.

package Stack

import (
 "fmt"
 "sync"
)

type Stack struct {
 list  []interface{}
 mutex sync.Mutex
}

// 初始化一个栈
func InitStack() *Stack {
 return &Stack{}
}

// 进栈
func (s *Stack) Push(value interface{}) {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 s.list = append(s.list, value)
}

// 出栈
func (s *Stack) Pop() interface{} {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 value := s.list[len(s.list)-1]
 s.list = s.list[:len(s.list)-1]
 return value
}

// 判断是否为空
func (s *Stack) IsEmpty() bool {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 return len(s.list) == 0
}

// 输出栈的大小
func (s *Stack) Size() int {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 return len(s.list)
}

// 打印所有的元素
func (s *Stack) Print() {
 for i := s.Size() - 1; i >= 0; i-- {
  fmt.Print(s.list[i], " ")
 }
 fmt.Println()
}

链式实现

使用单链表实现栈, 因此需要创建两个结构体

package StackLink

import (
 "errors"
 "fmt"
 "sync"
)

type Node struct {
 data interface{}
 next *Node
}

type StackLink struct {
 top    *Node
 length int
 mutex  sync.Mutex
}

// 初始化一个栈
func InitStack() *StackLink {
 return &StackLink{top: &Node{data: "stack", next: nil}, length: 0}
}

// 进栈
func (s *StackLink) Push(value interface{}) {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 node := &Node{data: value, next: s.top.next}
 s.top.next = node
 s.length++
}

// 出栈
func (s *StackLink) Pop() interface{} {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 if s.top.next == nil {
  return errors.New("异常！栈为空，无法推出元素")
 }
 value := s.top.next.data
 s.top = s.top.next
 s.length--
 return value
}

// 判断是否为空
func (s *StackLink) IsEmpty() bool {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 return s.length == 0
}

// 输出栈的大小
func (s *StackLink) Size() int {
 s.mutex.Lock()
 defer s.mutex.Unlock()
 return s.length
}

// 打印所有的元素
func (s *StackLink) Print() {
 cur := s.top
 for cur.next != nil {
  fmt.Print(cur.next.data, " ")
  cur = cur.next
 }
 fmt.Println()
}

以下是测试的例子以及输出:

func main() {
 s := Stack.InitStack()
 s.Push(5)
 s.Print()
 s.Push(3)
 s.Push(2)
 s.Print()
 fmt.Println(s.Size())
 fmt.Println(s.IsEmpty())
 fmt.Println(s.Pop())
}

// 5
// 2 3 5
// 3
// false
// 2

队列

定义

队列(Queue) 简称队，也是一种操作受限的线性表， 只允许在表的一端进行插入， 而在表的另一端进行删除。
向队列中插入元素称为入队或进队;删除元素称为出队或离队。这和我们日常生活中的排队是一致的， 最早排队的
也是最早离队的，其操作的特性是先进先出 (First In First Out, FIFO)

基础操作

• 初始化
• 插入
• 推出
• 判断是否为空
• 返回队列大小

存储结构

• 顺序结构
• 链式结构

顺序实现

由于可以使用 golang 自带的切片来模拟.

package Queue

import (
 "fmt"
 "sync"
)

type Queue struct {
 queue []interface{}
 mutex sync.Mutex
}

// 初始化表
func InitQueue() *Queue {
 return &Queue{}
}

// 插入
func (q *Queue) Push(value interface{}) {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 q.queue = append(q.queue, value)
}

// 推出
func (q *Queue) Pop() interface{} {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 value := q.queue[0]
 q.queue = q.queue[1:]
 return value
}

// 判断是否为空
func (q *Queue) IsEmpty() bool {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 return len(q.queue) == 0
}

// 返回队列大小
func (q *Queue) Size() int {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 return len(q.queue)
}

// 打印所有的元素
func (q *Queue) Print() {
 for _, x := range q.queue {
  fmt.Print(x, " ")
 }
 fmt.Println()
}

链式实现

使用单链表实现队列, 因此需要创建两个结构体

package QueueLink

import (
 "errors"
 "fmt"
 "sync"
)

type Node struct {
 data interface{}
 next *Node
}

type QueueLink struct {
 head   *Node
 tail   *Node
 length int
 mutex  sync.Mutex
}

// 初始化表
func InitQueueLink() *QueueLink {
 node := &Node{data: "queue", next: nil}
 return &QueueLink{head: node, tail: node, length: 0}
}

// 插入
func (q *QueueLink) Push(value interface{}) {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 node := &Node{data: value, next: nil}
 q.tail.next = node
 q.tail = node
 q.length++
}

// 推出
func (q *QueueLink) Pop() interface{} {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 if q.head.next == nil {
  return errors.New("异常！队列为空，无法推出元素")
 }
 value := q.head.next.data
 q.head = q.head.next
 q.length--
 return value
}

// 判断是否为空
func (q *QueueLink) IsEmpty() bool {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 return q.length == 0
}

// 返回队列大小
func (q *QueueLink) Size() int {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 return q.length
}

// 打印所有的元素
func (q *QueueLink) Print() {
 cur := q.head
 for cur.next != nil {
  fmt.Print(cur.next.data, " ")
  cur = cur.next
 }
 fmt.Println()
}

以下是测试的例子以及输出:

func main() {
 q := Queue.InitQueue()
 q.Push(1)
 q.Push(3)
 q.Push(6)
 q.Print()
 fmt.Println(q.Pop())
 fmt.Println(q.Pop())
 fmt.Println(q.IsEmpty())
 fmt.Println(q.Size())
}

// 1 3 6
// 1
// 3
// false
// 1