队列算法

╰+哭是因爲堅強的太久メ 2023-07-10 03:00 10阅读 0赞

*  单向队列：数组内元素key和value绑定，即使元素被取出，也无法在该位置继续存放数据

思路分析  
1、定义结构体存储队列  
2、front初始化-1  
3、rear初始化-1  
4、分别定义AddQueue、GetQueue、GetQueue

Tip：

*  若初始化为0：指针rear先赋值再+1，使得rear比真实数据大1，（第0位先被占用，rear=1）当rear=max时才停止，容易发生index溢出问题
 *  若初始化为-1：指针rear先+1再赋值，rear指针先到达第0位，其后第0位被元素占用

package main
    
    import (
    	"errors"
    	"fmt"
    	"os"
    )
    
    type Queue struct { 
    	Max   int
    	array [5]int
    	front int
    	rear  int
    }
    
    func (q *Queue) AddQueue(val int) (err error) { 
    	if q.rear+1 == q.Max { 
    		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() { 
    	for i := q.front + 1; i <= q.rear; i++ { 
    		fmt.Printf("array[%d]=%d\n", i, q.array[i])
    	}
    }
    func main() { 
    	queue := &Queue{ 
    		Max:   5,
    		array: [5]int{ },
    		front: -1,
    		rear:  -1,
    	}
    	var key string
    	var val int
    	for { 
    		fmt.Printf("1、添加数据请输入add\n")
    		fmt.Printf("2、获取数据请输入get\n")
    		fmt.Printf("3、显示所有数据请输入show\n")
    		fmt.Printf("4、退出请输入exit\n")
    
    		fmt.Scanln(&key)
    		switch key { 
    		case "get":
    			vals, err := queue.GetQueue()
    			if err != nil { 
    				fmt.Printf("获取数据失败\n")
    			} else { 
    				fmt.Printf("获取数据 %d success\n", vals)
    			}
    		case "add":
    			fmt.Printf("输入你要添加的数据\n")
    			fmt.Scanln(&val)
    			err := queue.AddQueue(val)
    			if err != nil { 
    				fmt.Printf("添加数据失败\n")
    			} else { 
    				fmt.Printf("添加数据 %d success\n", val)
    			}
    		case "show":
    			queue.ShowQueue()
    
    		case "exit":
    			os.Exit(0)
    
    		}
    
    	}
    }

输出结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70]

*  环形队列：队头有出去的元素可被补位

缺陷：数组里存储的元素总是比最大元素个数-1

精华：取模%

package main
    
    import (
    	"errors"
    	"fmt"
    	"os"
    )
    
    type Queue struct { 
    	Max   int
    	array [5]int
    	head  int
    	tail  int
    }
    
    func (q *Queue) Push(val int) (err error) { 
    	if q.isFull() { 
    		return errors.New("queue full")
    	}
    	q.array[q.tail] = val
    	q.tail = (q.tail + 1) % q.Max
    	return
    }
    
    func (q *Queue) Pop() (val int, err error) { 
    	if q.isEmpty() { 
    		return -1, errors.New("queue empty")
    	}
    	val = q.array[q.head]
    	q.head = (q.head + 1) % q.Max
    	return val, nil
    }
    
    func (q *Queue) Show() (err error) { 
    	size := q.Size()
    	if size == 0 { 
    		return errors.New("queue empty")
    	}
    	tmp := q.head
    	for i := 0; i < size; i++ { 
    		fmt.Printf("array[%d]=%d\n", tmp, q.array[tmp])
    		tmp = (tmp + 1) % q.Max
    	}
    	return
    }
    
    func (q *Queue) isFull() bool { 
    	return (q.tail+1) % q.Max == q.head
    }
    
    func (q *Queue) isEmpty() bool { 
    	return q.tail == q.head
    }
    
    func (q *Queue) Size() (num int) { 
    	return (q.tail + q.Max - q.head) % q.Max
    }
    
    func main() { 
    	queue := &Queue{ 
    		Max:   5,
    		array: [5]int{ },
    		head:  0,
    		tail:  0,
    	}
    	var key string
    	var val int
    	for { 
    		fmt.Printf("1、添加数据请输入add\n")
    		fmt.Printf("2、获取数据请输入get\n")
    		fmt.Printf("3、显示所有数据请输入show\n")
    		fmt.Printf("4、退出请输入exit\n")
    
    		fmt.Scanln(&key)
    		switch key { 
    		case "get":
    			vals, err := queue.Pop()
    			if err != nil { 
    				fmt.Printf("获取数据失败\n")
    			} else { 
    				fmt.Printf("获取数据 %d success\n", vals)
    			}
    		case "add":
    			fmt.Printf("输入你要添加的数据\n")
    			fmt.Scanln(&val)
    			err := queue.Push(val)
    			if err != nil { 
    				fmt.Printf("添加数据失败\n")
    			} else { 
    				fmt.Printf("添加数据 %d success\n", val)
    			}
    		case "show":
    			queue.Show()
    
    		case "exit":
    			os.Exit(0)
    
    		}
    
    	}
    }

输出结果：最多添加4个  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 1]  
取走一个又输入  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 2]

继续添加可看到最新的6补到了"0"的位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200229164148609.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200229182149926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200229182230299.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020022918233779.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYnpoZW5n,size_16,color_FFFFFF,t_70