Go 数组模拟环形队列

叁歲伎倆 2023-10-08 18:49 42阅读 0赞

#### 阅读目录 ####

*  数组模拟环形队列

## 数组模拟环形队列 ##

分析思路：  
1、什么时候表示队列满（tail+1）%maxSize = hed。  
2、tail == head 表示空。  
3、初始化时，tail = 0 head = 0。  
4、怎么统计该队列有多少元素（tail + maxSize - head）% maxSize。

package main
    
    import (
    	"errors"
    	"fmt"
    	"os"
    )
    
    // 使用一个结构体管理环形队列
    type CircleQueue struct {
        
    	maxSize int    //4
    	array   [5]int // 数组
    	head    int    // 指向队列队首
    	tail    int    // 指向队尾
    }
    
    // 入队列 AddQueue(push) GetQueue(pop)
    // 入队列
    func (this *CircleQueue) Push(val int) (err error) {
        
    	if this.IsFull() {
        
    		return errors.New("queue full")
    	}
    	// 把值给尾部,分析出 this.tail 在队列尾部，但是包含最后的元素
    	this.array[this.tail] = val
    	this.tail = (this.tail + 1) % this.maxSize
    	return
    }
    
    // 出队列
    func (this *CircleQueue) Pop() (val int, err error) {
        
    	if this.IsEmpty() {
        
    		return 0, errors.New("queue empty")
    	}
    	// 取出head是指向队首，并且含队首元素
    	val = this.array[this.head]
    	this.head = (this.head + 1) % this.maxSize
    	return
    }
    
    // 队列显示
    func (this *CircleQueue) ListQueue() {
        
    	// 取出当前队列有多少个元素
    	size := this.Size()
    	if size == 0 {
        
    		fmt.Println("队列为空")
    	}
    
    	// 设置一个辅助变量，指向head
    	tempHead := this.head
    	for i := 0; i < size; i++ {
        
    		fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])
    		tempHead = (tempHead + 1) % this.maxSize
    	}
    	fmt.Println()
    }
    
    // 判断环形队列为空
    func (this *CircleQueue) IsFull() bool {
        
    	return (this.tail+1)%this.maxSize == this.head
    }
    
    // 判断环形队列是否为空
    func (this *CircleQueue) IsEmpty() bool {
        
    	return this.tail == this.head
    }
    
    // 取出环形队列有多少个元素
    func (this *CircleQueue) Size() int {
        
    	// 这是一个关键点
    	return (this.tail + this.maxSize - this.head) % this.maxSize
    }
    
    func main() {
        
    
    	// 初始化一个环形队列
    	queue := &CircleQueue{
        
    		maxSize: 5,
    		head:    0,
    		tail:    0,
    	}
    
    	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)
    			err := queue.Push(val)
    			if err != nil {
        
    				fmt.Println(err.Error())
    			} else {
        
    				fmt.Println("加入队列OK")
    			}
    		case "get":
    			fmt.Println("get")
    			val, err := queue.Pop()
    			if err != nil {
        
    				fmt.Println(err.Error())
    			} else {
        
    				fmt.Println("从队列取出了一个数=", val)
    			}
    		case "show":
    			queue.ListQueue()
    		case "exit":
    			os.Exit(0)
    		}
    
    	}
    }

PS E:\TEXT\test_go\one> go run .\main.go
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    队列为空
    
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    1
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[0]=1
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    2
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[0]=1        arr[1]=2
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    3
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    4
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[0]=1        arr[1]=2        arr[2]=3        arr[3]=4
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    
    arr[0]=1        arr[1]=2        arr[2]=3        arr[3]=4
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    5
    queue full
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[0]=1        arr[1]=2        arr[2]=3        arr[3]=4
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    从队列取出了一个数= 1
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[1]=2        arr[2]=3        arr[3]=4
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    5
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[1]=2        arr[2]=3        arr[3]=4        arr[4]=5
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    6
    queue full
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    从队列取出了一个数= 2
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    从队列取出了一个数= 3
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    从队列取出了一个数= 4
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    从队列取出了一个数= 5
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    queue empty
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    get
    get
    queue empty
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    add
    输入你要入队列数
    10
    加入队列OK
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列
    show
    arr[0]=10
    1、输入add 表示添加数据到队列
    2、输入get 表示添加数据到队列
    3、输入show 表示添加数据到队列
    4、输入exit 表示添加数据到队列