Golang数据结构 - 3 - 队列
2019-06-19 本文已影响0人
vouv
______ __ __ _______ __ __ _______
/ __ \ | | | | | ____|| | | | | ____|
| | | | | | | | | |__ | | | | | |__
| | | | | | | | | __| | | | | | __|
| `--' '--.| `--' | | |____ | `--' | | |____
\_____\_____\\______/ |_______| \______/ |_______|
在上一章中我们学习了栈以及栈的基本操作，并使用数组切片和链表来实现了两种不同的栈操作方式，接下来我们将学习并实现队列。
队列与栈非常相似，但是元素的出入原则与栈不同，在栈中元素是以后进先出（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
