132 lines
2.6 KiB
Markdown
132 lines
2.6 KiB
Markdown
---
|
||
title: 用go实现队列
|
||
tags: 数据结构
|
||
categories: 数据结构
|
||
date: 2022-01-09 16:13:09
|
||
---
|
||
|
||
# 队列的定义
|
||
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构，与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出。队列有两种存储方式，分别是顺序队和链队，今天实现的是链队。
|
||
|
||
# 结构的定义
|
||
队列需要两个指针定位对头和队尾的位置，所以定义方式如下所示。
|
||
```go
|
||
// 代表每一个节点
|
||
type node struct {
|
||
data interface{}
|
||
next *node
|
||
}
|
||
|
||
type queue struct {
|
||
// 头节点
|
||
head *node
|
||
|
||
// 队尾节点
|
||
rear *node
|
||
|
||
size int
|
||
|
||
sync.Mutex
|
||
}
|
||
```
|
||
|
||
# 队列的相关操作
|
||
|
||
## 初始化队列
|
||
|
||
```go
|
||
func newQueue() *queue {
|
||
q := new(queue)
|
||
q.head = nil
|
||
q.rear = nil
|
||
q.size = 0
|
||
return q
|
||
}
|
||
```
|
||
创建一个心得队列对象，同时将头指针和尾指针全部置为nil
|
||
|
||
## 入队
|
||
|
||
```go
|
||
// Put 尾插法
|
||
func (q *queue) Put(element interface{}) {
|
||
n := new(node)
|
||
n.data = element
|
||
q.Lock()
|
||
defer q.Unlock()
|
||
|
||
if q.rear == nil {
|
||
q.head = n
|
||
q.rear = n
|
||
}else {
|
||
q.rear.next = n
|
||
q.rear = n
|
||
}
|
||
q.size ++
|
||
}
|
||
|
||
// PutHead 头插法，在队列头部插入一个元素
|
||
func (q *queue) PutHead(element interface{}) {
|
||
n := new(node)
|
||
n.data = element
|
||
q.Lock()
|
||
defer q.Unlock()
|
||
if q.head == nil {
|
||
q.head = n
|
||
q.rear = n
|
||
}else {
|
||
n.next = q.head
|
||
q.head = n
|
||
}
|
||
q.size ++
|
||
}
|
||
```
|
||
入队分为两种方式，分别是头插法和尾插法，默认采用尾插法。
|
||
|
||
尾插法入队，首先创建一个节点对象，判断队列此时是否为空，若为空则将头指针和尾指针都指向该节点，否则将尾指针的节点的指针域指向新创建的节点，然后将队列的尾指针指向该节点。
|
||
|
||
## 出队
|
||
```go
|
||
// Get 获取并删除队列头部的元素
|
||
func (q *queue) Get() interface{} {
|
||
if q.head == nil {
|
||
return nil
|
||
}
|
||
n := q.head
|
||
q.Lock()
|
||
defer q.Unlock()
|
||
// 代表队列中仅一个元素
|
||
if n.next == nil {
|
||
q.head = nil
|
||
q.rear = nil
|
||
|
||
}else {
|
||
q.head = n.next
|
||
}
|
||
q.size--
|
||
return n.data
|
||
}
|
||
```
|
||
|
||
出队默认从对头取出元素，首先判断队列是否存在元素，若不存在则返回nil，若存在，则将头节点赋值，然后判断队列中是否只存在一个元素，若只存在一个元素则将头尾节点都置为nil，否则将头节点置为该节点的下一个节点。
|
||
|
||
## 测试
|
||
```go
|
||
|
||
func main() {
|
||
q := newQueue()
|
||
q.Put(1)
|
||
q.Put(2)
|
||
fmt.Println(q.Get())
|
||
fmt.Println(q.Get())
|
||
fmt.Println("队列中剩余元素个数",q.size)
|
||
}
|
||
|
||
// 1
|
||
// 2
|
||
// 队列中剩余元素个数 0
|
||
|
||
|
||
```
|
||
|
||
## 个人博客<https://vtsqr.xyz> |