【算法笔记】queue的简单实践

李明燮(li_mingxie)

2022-02-14

Page content

今天用go语言简单的写了一下queue的方法。
为了以后方便查看，当做笔记整理了一下~~

1.队列(QUEUE)

维基百科里是这么解释的。

计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。
在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

具体的详解可以参考这篇文章里的Queue部分栈(STACK), 堆(HEAP), 队列(QUEUE) 是什么？

2.数组队列

struct

type Queue struct {
 Front    int
 Rear     int
 Size     int
 Capacity int
 Values   []int
}

入队(Enqueue)

func (q *Queue) Enqueue(item int) {
 if q.IsFull() {
  fmt.Println("queue is full!")
  return
 }

 q.Values[q.Rear] = item
 q.Rear = (q.Rear + 1) % q.Capacity
 q.Size++
}

这里须注明一下

Enqueue方法下面，可以写扩充队列的逻辑：比如队列快满了，Size/Capacity>80% 就扩充队列空间。
下面Dequeue的时候也是如果Size/Capacity < 40%, 可以写缩减空间的逻辑。
(q.Rear + 1) % q.Capacity 部分是为了循环使用空间，使用了循环队列。
如下图：

图片备用地址
queue

出队(Dequeue)

func (q *Queue) Dequeue() int {
 if q.IsEmpty() {
  fmt.Println("queue is empty!")
  return -1
 }
 front := q.Values[q.Front]
 q.Front = (q.Front + 1) % q.Capacity
 return front
}

Peek, IsFull, IsEmpty

func (q *Queue) Peek() int {
 if q.IsEmpty() {
  fmt.Println("queue is empty!")
  return -1
 }

 return q.Values[q.Front]
}

func (q *Queue) IsFull() bool {
 return q.Size == q.Capacity
}

func (q *Queue) IsEmpty() bool {
 return q.Size == 0
}

执行结果

func main() {
 queue := Queue{Capacity: 10}
 queue.Values = make([]int, queue.Capacity)
 queue.Enqueue(11)
 queue.Enqueue(12)
 queue.Enqueue(13)
 fmt.Println("-------- queue.Values  --------")
 fmt.Printf("%+v", queue.Values)
 fmt.Println("")
 fmt.Println("-------- Front, Rear  --------")
 fmt.Printf("Front: %v, Rear: %v", queue.Front, queue.Rear)
 fmt.Println("")
 queue.Enqueue(14)
 fmt.Println("-------- queue.Values  --------")
 fmt.Printf("%+v", queue.Values)
 fmt.Println("")
 fmt.Println("-------- Front, Rear  --------")
 fmt.Printf("Front: %v, Rear: %v", queue.Front, queue.Rear)
 fmt.Println("")
 fmt.Println("-------- queue.IsEmpty  --------")
 fmt.Println(queue.IsEmpty())
 fmt.Println("-------- queue.IsFull  --------")
 fmt.Println(queue.IsFull())
 fmt.Println("-------- queue.Dequeue  --------")
 fmt.Println(queue.Dequeue())
 fmt.Println("-------- Front, Rear  --------")
 fmt.Printf("Front: %v, Rear: %v", queue.Front, queue.Rear)
}

执行结果为：

$ go run main.go
-------- queue.Values  --------
[11 12 13 0 0 0 0 0 0 0]
-------- Front, Rear  --------
Front: 0, Rear: 3
-------- queue.Values  --------
[11 12 13 14 0 0 0 0 0 0]
-------- Front, Rear  --------
Front: 0, Rear: 4
-------- queue.IsEmpty  --------
false
-------- queue.IsFull  --------
false
-------- queue.Dequeue  --------
11
-------- Front, Rear  --------
Front: 1, Rear: 4

2. 链式队列

struct

type ListQueue struct {
 Front *QueueNode
 Rear  *QueueNode
}

type QueueNode struct {
 Value int
 Next  *QueueNode
}

入队(Enqueue)

func (q *ListQueue) Enqueue(val int) {
 newNode := QueueNode{Value: val}
 if q.Rear == nil {
  q.Front = &newNode
  q.Rear = &newNode
  return
 }

 q.Rear.Next = &newNode
 q.Rear = &newNode
}

出队(Dequeue)

func (q *ListQueue) Dequeue() int {
 if q.Front == nil {
  fmt.Println("queue is empty!")
  return -1
 }
 front := q.Front
 q.Front = q.Front.Next
 if q.Front == nil {
  q.Rear = nil
 }

 return front.Value
}

Print

func (node *QueueNode) Print() {
 if node == nil || node.Value == 0 {
  return
 } else {
  fmt.Print(node.Value, " ")
  node.Next.Print()
 }
}

执行结果

func main() {
 listQueue := ListQueue{}
 listQueue.Enqueue(11)
 listQueue.Enqueue(12)
 listQueue.Enqueue(13)
 listQueue.Enqueue(14)

 fmt.Println("-------- listQueue.Values  --------")
 listQueue.Front.Print()
 fmt.Println("")

 fmt.Println("-------- listQueue.Dequeue  --------")
 fmt.Println(listQueue.Dequeue())

 fmt.Println("-------- listQueue.Values  --------")
 listQueue.Front.Print()
}

执行结果为：

$ go run main.go
-------- listQueue.Values  --------
11 12 13 14 
-------- listQueue.Dequeue  --------
11
-------- listQueue.Values  --------
12 13 14

其它

过段时间自己写了，用数组实现环形队列，好痛苦…^^:;
记录一下

package main

import "fmt"

type Queue struct {
 Data    []int
 Front   int
 Tail    int
 Size    int
 MaxSize int
}

func (q *Queue) Push(v int) {
 if q.IsFull() {
  fmt.Println("队列已满，无法添加")
  return
 }
 if q.IsEmpty() {
  q.Front = 0
  q.Tail = 0
  q.Data[0] = v
 } else {
  q.Tail = (q.Tail + 1) % q.MaxSize
  q.Data[q.Tail] = v
 }
 q.Size++
}

func (q *Queue) Peek() int {
 if q.IsEmpty() {
  fmt.Println("队列已空，无法Peek")
  return -1
 }
 result := q.Data[q.Front]
 q.Front = (q.Front + 1) % q.MaxSize
 q.Size--
 return result
}

func (q *Queue) Pop() int {
 if q.IsEmpty() {
  fmt.Println("队列已空，无法Pop")
  return -1
 }
 result := q.Data[q.Tail]
 q.Tail = (q.MaxSize + q.Tail - 1) % q.MaxSize
 q.Size--
 return result
}

func (q *Queue) Get(v int) int {
 if q.IsEmpty() {
  fmt.Println("队列已空，无法Get")
  return -1
 }
 for i, val := range q.Data {
  if val == v {
   return i
  }
 }
 return -1
}

// func (q *Queue) Size() int {
//  return (q.MaxSize - q.Front + q.Tail) % q.MaxSize
// }

func (q *Queue) IsFull() bool {
 if q.Size == q.MaxSize {
  return true
 } else {
  return false
 }
}

func (q *Queue) IsEmpty() bool {
 if q.Size == 0 {
  return true
 } else {
  return false
 }
}

func main() {
 var n int = 5
 q := &Queue{
  Size:    0,
  MaxSize: n,
 }
 q.Data = make([]int, q.MaxSize)

 q.Push(6)
 q.Push(8)
 q.Push(10)
 q.Push(12)
 q.Push(14)
 q.Push(16)
 fmt.Printf("%+v\n", q)

 a := q.Peek()
 fmt.Printf("%+v\n", a)
 fmt.Printf("%+v\n", q)

 q.Peek()
 q.Peek()
 q.Peek()

 q.Push(16)
 q.Push(18)
 q.Push(20)
 q.Push(22)
 fmt.Printf("%+v\n", q)

 d := q.Peek()
 e := q.Pop()
 fmt.Printf("%v, %v\n", d, e)
 fmt.Printf("%+v\n", q)

 c := q.Get(14)
 fmt.Printf("%+v\n", c)
}

欢迎大家的意见和交流

email: li_mingxie@163.com