美文网首页
Golang数据结构 - 3 - 队列

Golang数据结构 - 3 - 队列

作者: vouv | 来源:发表于2019-06-19 23:04 被阅读0次
  ______      __    __   _______  __    __   _______ 
 /  __  \    |  |  |  | |   ____||  |  |  | |   ____|
|  |  |  |   |  |  |  | |  |__   |  |  |  | |  |__   
|  |  |  |   |  |  |  | |   __|  |  |  |  | |   __|  
|  `--'  '--.|  `--'  | |  |____ |  `--'  | |  |____ 
 \_____\_____\\______/  |_______| \______/  |_______|

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

队列与栈非常相似，但是元素的出入原则与栈不同，在栈中元素是以后进先出（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 - 队列

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

  • 数据结构——Golang实现队列

    转载请注明出处: 数据结构——Golang实现队列 1. 介绍 队列是一种特殊的线性表，特殊之处在于它只允许在表的...

  • GO语言实现 一 栈和队列

    线性表中，栈和队列是非常重要的两种数据结构，本文将就这两种数据结构进行 golang语言实现 一.栈的实现 我们需...

  • 6-Python 数据结构初识

    课程概要：1、Python 数据结构概述2、Python 常见数据结构——栈3、Python 常见数据结构——队列...

  • 队列

    2018年10月31日 队列是一种先进先出(FIFO)的数据结构 1，队列的链表实现 2，队列的数组实现 3，队列...

  • 手撸golang 基本数据结构与算法 队列

    手撸golang 基本数据结构与算法 队列 缘起 最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)本系...

  • Java数据类型

    Java数据结构中常用的数据结构包含如下8种： 1:数组（Array） 2:栈（Stack） 3:队列（Queue...

  • 看图说话数据结构之二项队列(优先队列)——原理解析

    数据结构之二叉堆(优先队列)——原理解析，数据结构之二叉堆(优先队列)——java实现，数据结构之左式堆(优先队列...

  • 数据结构：八大数据结构分类

    数据结构分类 1、数组 2、栈 3、队列 4、链表 5、树 6、散列表 7、堆 8、图 数据结构分类 数据结构是指...

  • 数据结构导读目录

    数据结构(1)-常见数据结构数据结构(2)-栈和队列和Hash表数据结构(3)-树和二叉树的遍历数据结构(4)-二...

网友评论

      本文标题：Golang数据结构 - 3 - 队列

      本文链接：https://www.haomeiwen.com/subject/kzmcqctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Golang数据结构 - 3 - 队列|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！