Golang数据结构 - 3 - 队列

栏目: Go · 发布时间: 5年前

内容简介：在队列与栈非常相似，但是元素的出入原则与栈不同，在栈中元素是以后进先出（LIFO）的原则进行的，而在队列中元素以先进先出（FIFO）的原则进行。队列与栈类似，是一种特殊的线性表，它只允许在表的前端进行插入操作，也只允许在表的后端进行弹出操作。进行插入操作的一端称为队尾，而进行删除操作的一端则称为队头。

队列

在 上一章 中我们学习了栈以及栈的基本操作，并使用数组切片和链表来实现了两种不同的栈操作方式，接下来我们将学习并实现队列。

队列与栈非常相似，但是元素的出入原则与栈不同，在栈中元素是以后进先出（LIFO）的原则进行的，而在队列中元素以先进先出（FIFO）的原则进行。

队列与栈类似，是一种特殊的线性表，它只允许在表的前端进行插入操作，也只允许在表的后端进行弹出操作。进行插入操作的一端称为队尾，而进行删除操作的一端则称为队头。

本章将基于 Go 数组切片、链表来实现队列的基本操作，同时实现双端队列，最终探讨循环队列的特性以及应用。

队列定义

首先对队列定义如下基本操作接口：

  • Enqueue(e ...Element)：添加若干元素入队
  • Dequeue() Element：队首元素出队
  • Peek() Element：获取队首元素，不出队
  • Empty() bool：队列是否为空
  • Size() int：返回队队列大小
  • Clear()：清空队列

代码如下

type Element interface{}

type Queue interface {
    // 入队
    Enqueue(e ...Element)
    // 出队
    Dequeue() Element

    // 获取队首元素，不出队
    Peek() Element

    // 队列是否为空你
    Empty() bool

    // 返回队列大小
    Size() int
    
    // 清空队列
    Clear()
}

向队列添加元素

  1. 数组切片实现
// 入队操作
func (s *ArrayQueue) Enqueue(e ...Element) {
    *s = append(*s, e...)
}
  1. 链表实现
func (s *LinkedQueue) Enqueue(e ...Element) {
    for _, v := range e {
        s.Tail.Next = &node{
            Value: v,
            Next:  nil,
        }
        s.Tail = s.Tail.Next
        s.size++
    }
}

从队列移除元素

  1. 数组切片实现
// 出队
func (s *ArrayQueue) Dequeue() Element {
    if s.Empty() {
        return nil
    }
    first := (*s)[0]

    // 出队操作
    *s = (*s)[1:]
    return first
}
  1. 链表实现
func (s *LinkedQueue) Dequeue() Element {
    if s.Empty() {
        return nil
    }
    first := s.Head.Next.Value

    // 出队
    s.Head = s.Head.Next
    s.size--
    return first
}

查看队列头元素

  1. 数组切片实现
// 获取队首元素，不出队
func (s *ArrayQueue) Peek() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[0]
}
  1. 链表实现
func (s *LinkedQueue) Peek() Element {
    if s.Empty() {
        return nil
    }
    return s.Head.Next.Value
}

获取队列长度

  1. 数组切片实现
// 返回队列大小
func (s *ArrayQueue) Size() int {
    return len(*s)
}
  1. 链表实现
func (s *LinkedQueue) Size() int {
    return s.size
}

检查队列是否为空

  1. 数组切片实现
// 队列是否为空
func (s *ArrayQueue) Empty() bool {
    return s.Size() == 0
}
  1. 链表实现
func (s *LinkedQueue) Empty() bool {
    return s.Head == s.Tail
}

清空队列

  1. 数组切片实现
// 清空队列
func (s *ArrayQueue) Clear() {
    *s = ArrayQueue{}
}
  1. 链表实现
func (s *LinkedQueue) Clear() {
    s.Head.Next = nil
    s.Tail = s.Head
    s.size = 0
}

双端队列

双端队列也是在现实中非常常用的一种数据结构，它允许我们在队列的两端进行添加和删除操作。

在本章中双端队列的实现主要有以下接口:

  • AddFront(e ...Element)：向队首添加元素
  • AddBack(e ...Element)：向队尾添加元素
  • RemoveFront() Element：移除队首元素
  • RemoveBack() Element：移除队尾元素
  • PeekFront() Element：查看队首元素，不出队
  • PeekBack() Element：查看队尾元素，不出队
  • Size() int：获取队列长度
  • Empty() bool：判断队列是否为空

向队首添加元素

func (s *ArrayDeque) AddFront(e ...Element) {
    ln := len(e)
    rev := make([]Element, ln)
    for i, v := range e {
        rev[ln-i-1] = v
    }
    *s = append(rev, *s...)
}

向队尾添加元素

func (s *ArrayDeque) AddBack(e ...Element) {
    *s = append(*s, e...)
}

移除队首元素

func (s *ArrayDeque) RemoveFront() Element {
    if s.Empty() {
        return nil
    }
    v := (*s)[0]

    // 出队
    *s = (*s)[1:]
    return v

}

移除队尾元素

func (s *ArrayDeque) RemoveBack() Element {
    if s.Empty() {
        return nil
    }
    ln := len(*s)
    v := (*s)[ln-1]

    // 出队
    *s = (*s)[:ln-1]
    return v
}

查看队首元素

func (s *ArrayDeque) PeekFront() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[0]
}

查看队尾元素

func (s *ArrayDeque) PeekBack() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[len(*s)-1]
}

获取队列长度

func (s *ArrayDeque) Size() int {
    return len(*s)
}

队列是否为空

func (s *ArrayDeque) Empty() bool {
    return s.Size() == 0
}

完整实现代码

队列

package main

import "fmt"

type Element interface{}

type Queue interface {
    // 入队
    Enqueue(e ...Element)
    // 出队
    Dequeue() Element

    // 获取队首元素，不出队
    Peek() Element

    // 队列是否为空你
    Empty() bool

    // 返回队列大小
    Size() int

    // 清空队列
    Clear()
}

// 使用数组切片实现的队列
type ArrayQueue []Element

// 入队操作
func (s *ArrayQueue) Enqueue(e ...Element) {
    *s = append(*s, e...)
}

// 出队
func (s *ArrayQueue) Dequeue() Element {
    if s.Empty() {
        return nil
    }
    first := (*s)[0]

    // 出队操作
    *s = (*s)[1:]
    return first
}

// 获取队首元素，不出队
func (s *ArrayQueue) Peek() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[0]
}

// 队列是否为空
func (s *ArrayQueue) Empty() bool {
    return s.Size() == 0
}

// 返回队列大小
func (s *ArrayQueue) Size() int {
    return len(*s)
}

// 清空队列
func (s *ArrayQueue) Clear() {
    *s = ArrayQueue{}
}

func NewArrayQueue() Queue {
    return &ArrayQueue{}
}

type node struct {
    Value Element
    Next  *node
}

// 使用链表实现的队列
// 这里使用带有头尾节点的链表
type LinkedQueue struct {
    Head *node
    Tail *node
    size int
}

func (s *LinkedQueue) Enqueue(e ...Element) {
    for _, v := range e {
        s.Tail.Next = &node{
            Value: v,
            Next:  nil,
        }
        s.Tail = s.Tail.Next
        s.size++
    }
}

func (s *LinkedQueue) Dequeue() Element {
    if s.Empty() {
        return nil
    }
    first := s.Head.Next.Value

    // 出队
    s.Head = s.Head.Next
    s.size--
    return first
}

func (s *LinkedQueue) Peek() Element {
    if s.Empty() {
        return nil
    }
    return s.Head.Next.Value
}

func (s *LinkedQueue) Empty() bool {
    return s.Head == s.Tail
}

func (s *LinkedQueue) Size() int {
    return s.size
}

func (s *LinkedQueue) Clear() {
    s.Head.Next = nil
    s.Tail = s.Head
    s.size = 0
}

func NewLinkedQueue() Queue {
    head := &node{}
    return &LinkedQueue{
        Head: head,
        Tail: head,
        size: 0,
    }
}

func main() {
    q := NewArrayQueue()
    //q := NewLinkedQueue()

    fmt.Println("Empty:", q.Empty())
    fmt.Println("Size:", q.Size())

    q.Enqueue(1, 2, 3, 4, 5, 6)
    fmt.Println("Enqueue 1,2,3,4,5,6")
    fmt.Println("Size:", q.Size())
    fmt.Println("Peek:", q.Peek())

    fmt.Println("Dequeue:", q.Dequeue(), q.Dequeue(), q.Dequeue())
    fmt.Println("Size:", q.Size())
    fmt.Println("Empty:", q.Empty())

    fmt.Println("Dequeue:", q.Dequeue(), q.Dequeue(), q.Dequeue())
    fmt.Println("Size:", q.Size())

    fmt.Println("Empty:", q.Empty())

    fmt.Println("Enqueue:1,2,3")
    q.Enqueue(1, 2, 3)

    fmt.Println("Dequeue:", q.Dequeue(), q.Dequeue())

    fmt.Println("Clear")
    q.Clear()
    fmt.Println("Empty:", q.Empty(), "Size:", q.Size())

}

运行结果

Empty: true
Size: 0
Enqueue 1,2,3,4,5,6
Size: 6
Peek: 1
Dequeue: 1 2 3
Size: 3
Empty: false
Dequeue: 4 5 6
Size: 0
Empty: true
Enqueue:1,2,3
Dequeue: 1 2
Clear
Empty: true Size: 0

Process finished with exit code 0

双端队列

package main

import "fmt"

type Element interface{}

type Deque interface {
    // 向队首添加元素
    AddFront(e ...Element)

    // 向队尾添加元素
    AddBack(e ...Element)

    // 队首元素出队
    RemoveFront() Element

    // 队尾元素出队
    RemoveBack() Element

    // 查看队首元素
    PeekFront() Element

    // 查看队尾元素
    PeekBack() Element

    // 队列长度
    Size() int

    // 队列是否为空
    Empty() bool
}

type ArrayDeque []Element

func (s *ArrayDeque) AddFront(e ...Element) {
    ln := len(e)
    rev := make([]Element, ln)
    for i, v := range e {
        rev[ln-i-1] = v
    }
    *s = append(rev, *s...)
}

func (s *ArrayDeque) AddBack(e ...Element) {
    *s = append(*s, e...)
}

func (s *ArrayDeque) RemoveFront() Element {
    if s.Empty() {
        return nil
    }
    v := (*s)[0]

    // 出队
    *s = (*s)[1:]
    return v

}

func (s *ArrayDeque) RemoveBack() Element {
    if s.Empty() {
        return nil
    }
    ln := len(*s)
    v := (*s)[ln-1]

    // 出队
    *s = (*s)[:ln-1]
    return v
}

func (s *ArrayDeque) PeekFront() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[0]
}

func (s *ArrayDeque) PeekBack() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[len(*s)-1]
}

func (s *ArrayDeque) Size() int {
    return len(*s)
}

func (s *ArrayDeque) Empty() bool {
    return s.Size() == 0
}

func NewArrayDeque() Deque {
    return &ArrayDeque{}
}

func main() {

    dq := NewArrayDeque()

    dq.AddFront(1, 2, 3, 4, 5, 6, 7, 8, 9)
    fmt.Println("AddFront: 1,2,3,4,5,6,7,8,9")

    fmt.Println("RemoveFront:", dq.RemoveFront(), dq.RemoveFront())

    fmt.Println("RemoveBack:", dq.RemoveBack(), dq.RemoveBack())

}

运行结果

AddFront: 1,2,3,4,5,6,7,8,9
RemoveFront: 9 8
RemoveBack: 1 2

Process finished with exit code 0

以上所述就是小编给大家介绍的《Golang数据结构 - 3 - 队列》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
美团机器学习实践

美团机器学习实践

美团算法团队 / 人民邮电出版社 / 2018-8-1 / 79.00元

人工智能技术正以一种超快的速度深刻地改变着我们的生活，引导了第四次工业革命。美团作为国内O2O领域领 先的服务平台，结合自身的业务场景和数据，积极进行了人工智能领域的应用探索。在美团的搜索、推荐、计算广告、风控、图像处理等领域，相关的人工智能技术得到广泛的应用。本书包括通用流程、数据挖掘、搜索和推荐、计算广告、深度学习以及算法工程6大部分内容，全面介绍了美团在多个重要方面对机器学习的应用。 ......一起来看看 《美团机器学习实践》 这本书的介绍吧!

码农工具
CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

MD5 加密
MD5 加密

MD5 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2024 码农网 粤ICP备17054400号-3