队列(queue)

  • 队列是一个有序列表 可以用数组或链表来实现
  • 遵循先入先出的原则 即：先存入队列的数据 要先取出 后存入的要后取出

数组模拟队列实现

队列本身是有序列表，若使用数组的结构来存储队列的数据则 需要申明三个变量maxSize(最大容量)front(队首)rear(队尾)

type Queue struct {
	maxSize int
	array   [5]int
	front   int
	rear    int
}

func (q *Queue) addQueue(val int) error {
	if q.rear == (q.maxSize - 1) {
		return errors.New("queue full")
	}
	q.rear++
	q.array[q.rear] = val
	return nil
}

func (q *Queue) showQueue() {
	for i := q.front + 1; i <= q.rear; i++ {
		fmt.Printf("array[%d]=%d", i, q.array[i])
		fmt.Println()
	}
}

func (q *Queue) getQueue() (int, error) {
	if q.front == q.rear {
		return 0, errors.New("queue is null")
	}
	q.front++
	return q.array[q.front], nil
}

func main() {
	que := Queue{
		maxSize: 5,
		front:   -1,
		rear:    -1,
	}
	for {
		fmt.Println("1.add 添加队列")
		fmt.Println("2.show显示队列")
		fmt.Println("3.get 取队列")
		fmt.Println("4.exit 退出")
		var key string
		var val int
		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("请输入你要添加的数据")
			fmt.Scanln(&val)
			err := que.addQueue(val)
			if err != nil {
				fmt.Println(err)
			}
		case "show":
			que.showQueue()
		case "get":
			fmt.Println(que.getQueue())
		case "exit":
			os.Exit(0)
		}
	}
}
  • 上面代码实现了基本队列结构 但是没有有效地利用数组空间
  • 如何使用数组 实现一个环形队列

数组模拟环形队列

链表

链表是有序的列表，但是它在内存中存储如下 img.png

单链表

示意图： img.png **说明：**一般来说，为了比较好的对单链表进行增删改查，我们都会给它设置一个头节点，头节点的作用主要是用来标识链表头，本身这个节点不存放数据 t