数据结构和算法-02

队列

简介

队列是一个有序列表，可以使用数组或者链表来表示
队列遵循先入先出的原则，即先放入的数据会先被取出

数组模拟队列

模拟一个非环形队列

简单理一下思路，通过一个数组，存放指定的数据类型。每次取出时，取出指针向后移动一次，每次放入数据，放入指针向后移动。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


package main

import (
	"errors"
	"fmt"
)

const (
	maxsize int = 4
	front   int = 0
	backend int = 0
)

type Queue struct {
	// 声明一个 数组 的最大范围
	Maxsize int
	// 声明取出数据时的指针
	Front int
	// 声明放入数据时的指针
	Backend int
	// 声明数组
	Arr [maxsize]int
}

func NewQueue() *Queue {
	var arr [maxsize]int
	return &Queue{
		Maxsize: maxsize,
		Front:   front,
		Backend: backend,
		Arr:     arr,
	}
}

// 添加数据到队列中，首先要判断数组中存放的数据是否已满。
func (q *Queue) AddQueue(val int) error {
	if q.Backend == q.Maxsize-1 {
		return errors.New("data full")
	}
	q.Arr[q.Backend] = val
	q.Backend++
	return nil
}

// 查看队列，从取出的指针开始遍历到放入数据的指针
func (q *Queue) ListQueue() error {
	if q.Front == q.Backend {
		return errors.New("empty queue")
	}
	for start := q.Front; start < q.Backend; start++ {
		fmt.Printf("%v ", q.Arr[start])
	}
	fmt.Println()
	return nil
}

// 获取队列中的值，同时，取值指针加1
func (q *Queue) GetQueue() (int, error) {
	if q.Front == q.Backend {
		return q.Front, errors.New("empty queue")
	}
	val := q.Arr[q.Front]
	q.Front++
	return val, nil
}

func main() {
	q := NewQueue()
	q.AddQueue(5)
	q.AddQueue(30)

	q.ListQueue()
	q.GetQueue()
	q.ListQueue()
}

模拟一个环形队列

将数组当成一个环形队列来看待，能够极大的复用数组，节省空间的开支。

思路

front 下标，先取值后自增，因此 front 下标所指是没有值的
backend 下标，先存值后自增，因此 backend 下标所指是没有值的
当 front 和 backend相等时，只有以下几种可能性
- 1. 没有任何值，可以继续存储
- 1. backend 连续存储数组最大值后，重置下标后，两个值相等
- 1. backend 连续存储一定数值，且下标重置后，重新追上 front 下标所指，backend 和 front 两值相等。
通过加入 count 的方式来实时统计数组中数据的数量。

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114


package main

import (
	"errors"
	"fmt"
)

const (
	maxsize int = 4
	front   int = 0
	backend int = 0
	count   int = 0
)

type Queue struct {
	// 声明一个 数组 的最大范围
	Maxsize int
	// 声明取出数据时的指针
	Front int
	// 声明放入数据时的指针
	Backend int
	// 声明数组
	Arr [maxsize]int
	// 统计队列中数据量
	Count int
}

func NewQueue() *Queue {
	var arr [maxsize]int
	return &Queue{
		Maxsize: maxsize,
		Front:   front,
		Backend: backend,
		Arr:     arr,
		Count:   count,
	}
}

func (q *Queue) Judge() error {
	// count 值为0，说明数组中没有数据
	if q.Count == 0 {
		return nil
	}

	// count 值为数组最大值，说明数组值已经满了
	if q.Count == q.Maxsize {
		return errors.New("Full")
	}

	// count 在0和数组最大范围值之间，说明数组未满，可以存值
	return nil
}

func (q *Queue) Add(val int) {
	err := q.Judge()
	if err != nil {
		fmt.Println("data full")
		return
	}
	q.Arr[q.Backend] = val
	q.Backend++
	if q.Backend == q.Maxsize {
		q.Backend = backend
	}
	q.Count++
}

func (q *Queue) Get() {
	if q.Count == 0 {
		fmt.Println("no data to get")
		return
	}
	res := q.Arr[q.Front]
	fmt.Printf("index: %v, result: %v", q.Front, res)
	q.Front++
	if q.Front == q.Maxsize {
		q.Front = front
	}
	q.Count--
	fmt.Println()
}

func (q *Queue) List() {
	if q.Count == 0 {
		fmt.Println("no data to list")
		return
	} else {
		for _, v := range q.Arr {
			fmt.Printf("%v ", v)
		}
		fmt.Println()
		fmt.Printf("current data: %v\n", q.Count)
	}
}

func main() {
	q := NewQueue()
	q.Add(10)
	q.Add(20)
	q.Add(30)
	q.Add(40)
	q.Add(50)
	q.Get()
	q.List()

	q.Add(50)
	q.List()
	q.Get()
	q.Get()
	q.Get()

	q.Add(60)
	q.List()
}