---
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>