Golang数据结构 - 3 - 队列

monigo · · 1198 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

队列

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

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

向队列添加元素

数组切片实现

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

链表实现

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 *ArrayQueue) Dequeue() Element {
    if s.Empty() {
        return nil
    }
    first := (*s)[0]

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

链表实现

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 *ArrayQueue) Peek() Element {
    if s.Empty() {
        return nil
    }
    return (*s)[0]
}

链表实现

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

获取队列长度

数组切片实现

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

链表实现

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

检查队列是否为空

数组切片实现

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

链表实现

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

清空队列

数组切片实现

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

链表实现

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

有疑问加站长微信联系（非本文作者）

本文来自：简书

感谢作者：monigo

查看原文：Golang数据结构 - 3 - 队列

入群交流（和以上内容无关）：加入Go大咖交流群，或添加微信：liuxiaoyan-s 备注：入群；或加QQ群：692541889

1198 次点击

加入收藏微博

收入我的专栏

上一篇：藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下

下一篇：golang buildmode

链表

切片

双端

移除

0 回复

添加一条新回复（您需要登录后才能回复没有账号？）

请尽量让自己的回复能够对别人有帮助
支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
图片支持拖拽、截图粘贴等方式上传

关注我

扫码关注领全套学习资料
加入 QQ 群：
- 192706294（已满）
- 731990104（已满）
- 798786647（已满）
- 729884609（已满）
- 977810755（已满）
- 815126783（已满）
- 812540095（已满）
- 1006366459（已满）
- 692541889
加入微信群：liuxiaoyan-s，备注入群
也欢迎加入知识星球 Go粉丝们（免费）

Golang数据结构 - 3 - 队列

队列

队列定义

向队列添加元素

从队列移除元素

查看队列头元素

获取队列长度

检查队列是否为空

清空队列

双端队列

向队首添加元素

向队尾添加元素

移除队首元素

移除队尾元素

查看队首元素

查看队尾元素

获取队列长度

队列是否为空

完整实现代码

队列

双端队列

用户登录

今日阅读排行

一周阅读排行

关注我

给该专栏投稿 写篇新文章

收入到我管理的专栏 新建专栏

队列

队列定义

向队列添加元素

从队列移除元素

查看队列头元素

获取队列长度

检查队列是否为空

清空队列

双端队列

向队首添加元素

向队尾添加元素

移除队首元素

移除队尾元素

查看队首元素

查看队尾元素

获取队列长度

队列是否为空

完整实现代码

队列

双端队列

给该专栏投稿写篇新文章

收入到我管理的专栏新建专栏