美文网首页
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 - 队列

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

          延伸阅读

          深度阅读

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

          栏目导航

          热点阅读

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

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

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

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

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

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