队列

队列

队列介绍

队列是一个有序列表，可以用数组或是链表来实现。

遵循先入先出的原则，即先存入队列的数据，要先取出，后存入的要后取出。

数组模拟队列

队列本身是有序列表，因为队列的输出，输入是分别从前后端来处理的，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则随着数据输入而改变。

// 使用结构体来管理队列
type Queue struct{
	maxSize int
	array [5]int  // 数组=>模拟队列
	front int   // 表示指向队列首部
	rear int   // 表示指向队列尾部
}

// 添加数据到队列
func (q *Queue)AddQueue(val int)(err error){
	// 先判断队列是否已满
	if q.rear == q.maxSize - 1 {
		return errors.New("queue full")
	}
	q.rear ++  // 后移
	q.array[q.rear] = val
	return
}

// 从队列中取出数据
func (q *Queue)GetQueue()(val int, err error){
	// 先判断队列是否为空
	if q.rear == q.front{
		// 表明队列为空
		return -1, errors.New("queue empty")
	}

	q.front ++
	val = q.array[q.front]
	return val, err
}

// 找到队首，然后遍历到队尾
func (q *Queue)ShowQueue(){
	// 先判断队列是否为空
	if q.front == q.rear{
		fmt.Println("queue empty")
		return
	}

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

func main() {
	// 先创建一个队列
	queue := &Queue{
		maxSize: 5,
		front: -1,
		rear: -1,
	}

	var key string
	var val int
	for{
		fmt.Println("1.输入add表示添加数据到队列")
		fmt.Println("2.输入get表示获取队列数据")
		fmt.Println("3.输入show表示显示队列")
		fmt.Println("4.输入exit退出")

		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("输入你要入队的数字")
			fmt.Scanln(&val)
			if err := queue.AddQueue(val); err != nil {
				fmt.Println(err.Error())
			}else{
				fmt.Println("加入队列成功")
			}
		case "get":
			if val, err := queue.GetQueue(); err != nil {
				fmt.Println(err.Error())
			}else{
				fmt.Println("从队列中取出的数据为:",val)
			}
		case "show":
			queue.ShowQueue()
		case "exit":
			os.Exit(0)
		}
	}
}

实现环形队列

// 使用一个结构体管理环形队列
type CircleQueue struct{
	maxSize int
	array [5]int
	head int  // 指向队列队首
	tail int  // 指向队尾
}

// 判断环形队列是否为满
func (c *CircleQueue)IsFull()bool{
	// 尾索引的下一个为头索引时表示队列满
	return (c.tail + 1) % c.maxSize == c.head
}

// 判断环形队列为空
func (c *CircleQueue)IsEmpty()bool{
	return c.tail == c.head
}

// 环形队列有多少个元素
func (c *CircleQueue)Size()int{
	return (c.tail + c.maxSize - c.head) % c.maxSize
}


// 入队列
func (c *CircleQueue)Push(val int)(err error){
	if c.IsFull(){
		return errors.New("queue full")
	}
	c.array[c.tail] = val
	c.tail = (c.tail + 1) % c.maxSize
	return
}

// 出队列
func (c *CircleQueue)Pop()(val int, err error){
	if c.IsFull(){
		return 0, errors.New("queue empty")
	}
	val = c.array[c.head]
	c.head = (c.head + 1) % c.maxSize
	return
}

func (c *CircleQueue)ShowQueue(){
	// 取出当前队列有多少个元素
	size := c.Size();
	if size == 0 {
		fmt.Println("Circle Queue Empty")
	}

	// 设计一个辅助变量，指向head
	tempHead := c.head
	for i := 0; i < size; i ++ {
		fmt.Printf("add[%d]=%d	",tempHead,c.array[tempHead])
		tempHead = (tempHead + 1) % c.maxSize
	}
	fmt.Println()
}



func main() {
	// 初始化一个环形队列
	queue := &CircleQueue{
		maxSize: 5,
		head: 0,
		tail: 0,
	}
	
	var key string
	var val int
	for{
		fmt.Println("输入add表示添加数据到队列")
		fmt.Println("输入get表示从队列中获取数据")
		fmt.Println("输入show表示显示队列")
		fmt.Println("输入exit表示退出")
		
		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("输入你要入队列的数")
			fmt.Scanln(&val)
			if err := queue.Push(val); err != nil{
				fmt.Println(err.Error())
			}else{
				fmt.Println("加入队列成功")
			}
		case "get":
			if val, err := queue.Pop(); err != nil {
				fmt.Println(err.Error())
			}else{
				fmt.Println("从队列中取出的数为：",val)
			}
		case "show":
			queue.ShowQueue()
		case "exit":
			os.Exit(0)
		}
	}
}