golang算法练习：基于array的队列实现

比眉伴天荒 2021-12-03 14:55 277阅读 0赞

### 需求 ###

队列，很常用的FIFO(先入先出)数据模型，下面尝试使用golang的array数据结构来实现队列模型  
**备注：需求和运行输出结果均已在代码中注释**

#### 简单队列 ####

代码：

package main
    
    import (
    	"fmt"
    )
    
    type SingleQueue struct {
    	Cap  int    `json:cap`  // 容量
    	Arr  [5]int `json:arr`  // 成员数组
    	Head int    `json:head` // index编号
    	Tail int    `json:tail` // index编号
    }
    
    func (singleQueue *SingleQueue) append(i int) {
    	// 队尾加入
    	if singleQueue.isFull() {
    		fmt.Println("Queue is already full")
    		return
    	}
    	if singleQueue.Head == -1 {
    		// 第一次加入元素时
    		singleQueue.Head = 0
    		singleQueue.Tail = 0
    		singleQueue.Arr[singleQueue.Tail] = i
    	} else {
    		singleQueue.Tail += 1
    		singleQueue.Arr[singleQueue.Tail] = i
    	}
    	fmt.Printf("Append %d ok!\n", i)
    }
    
    func (singleQueue *SingleQueue) isFull() (isFull bool) {
    	if singleQueue.Tail == (singleQueue.Cap - 1) {
    		return true
    	}
    	return
    }
    
    func (singleQueue *SingleQueue) getQueLength() (length int) {
    	// 获取singleQueue当前元素数量
    	return singleQueue.Tail - singleQueue.Head + 1
    }
    
    func (singleQueue *SingleQueue) isEmpty() (isEmpty bool) {
    	// 队列是否为空
    	if singleQueue.Tail == singleQueue.Head {
    		return true
    	}
    	return
    }
    
    func (singleQueue *SingleQueue) pop() (elem int) {
    	// 队首弹出
    	if singleQueue.isEmpty() {
    		fmt.Println("Queue is already empty")
    		return
    	}
    
    	elem = singleQueue.Arr[singleQueue.Head]
    	singleQueue.Head += 1
    	fmt.Printf("Pop %d ok!\n", elem)
    	return
    }
    
    func (singleQueue *SingleQueue) list() {
    	// 列出singleQueue当前所有的元素
    	fmt.Println("Here are all elements in this queue:")
    	for i := singleQueue.Head; i <= singleQueue.Tail; i++ {
    		fmt.Printf("index[%d],value=%d\n", i, singleQueue.Arr[i])
    	}
    }
    
    func main() {
    	var s = SingleQueue{
    		Cap:  5,
    		Head: -1,
    		Tail: -1,
    	}
    	s.append(1)
    	s.append(2)
    	s.append(3)
    	s.append(4)
    	s.append(5)
    	s.append(6) // Queue is already full
    	s.list()
    	fmt.Println(s.getQueLength()) // 5
    	s.pop()                       // Pop 1 ok!
    	fmt.Println(s.getQueLength()) // 4
    	s.append(6)                   // Queue is already full
    	/*
    		分析:单向队列，队首弹出后，腾出了空间，却无法给新的元素加入使用，因为容量评估无法感知head的偏移，因此，实用性很低，改进呢？改为可循环队列
    	*/
    
    }

**问题**  
array容量是有限的，这个队列存在空间浪费的问题，拥有空闲空间却无法再插入元素。怎么解决? 对代码简单改造,实现为循环队列即可，在关键位置进行取模运算。

### 循环队列 ###

代码:

package main
    
    import (
    	"fmt"
    )
    
    type CircleQueue struct {
    	Cap  int    `json:cap`  // 容量
    	Arr  [5]int `json:arr`  // 成员数组
    	Head int    `json:head` // index编号
    	Tail int    `json:tail` // index编号
    }
    
    func (circleQueue *CircleQueue) append(i int) {
    	// 队尾加入
    	if circleQueue.isFull() {
    		fmt.Println("Queue is already full")
    		return
    	}
    	if circleQueue.Head == -1 {
    		// 第一次加入元素时
    		circleQueue.Head = 0
    		circleQueue.Tail = 0
    		circleQueue.Arr[circleQueue.Tail] = i
    	} else {
    		circleQueue.Tail = (circleQueue.Tail + 1) % circleQueue.Cap
    		circleQueue.Arr[circleQueue.Tail] = i
    	}
    	fmt.Printf("Append %d ok!\n", i)
    }
    
    func (circleQueue *CircleQueue) isFull() (isFull bool) {
    	if (circleQueue.Tail+1)%circleQueue.Cap == circleQueue.Head {
    		// 环形队列，尾部下一个是首部，则说明空间已用完，因为是环形的，所以需要取模后再比较
    		return true
    	}
    	return
    }
    
    func (circleQueue *CircleQueue) getQueLength() (length int) {
    	// 获取circleQueue当前元素数量
    	length = ((circleQueue.Tail + circleQueue.Cap - circleQueue.Head) % circleQueue.Cap) + 1
    	return
    }
    
    func (circleQueue *CircleQueue) isEmpty() (isEmpty bool) {
    	// 队列是否为空
    	if circleQueue.Tail == circleQueue.Head {
    		return true
    	}
    	return
    }
    
    func (circleQueue *CircleQueue) pop() (elem int) {
    	// 队首弹出
    	if circleQueue.isEmpty() {
    		fmt.Println("Queue is already empty")
    		return
    	}
    
    	circleQueue.Head = (circleQueue.Head + 1) % circleQueue.Cap
    	elem = circleQueue.Arr[circleQueue.Head]
    	fmt.Printf("Pop %d ok!\n", elem)
    	return
    }
    
    func (circleQueue *CircleQueue) list() {
    	// 列出circleQueue当前所有的元素
    	//fmt.Println(circleQueue.Head)
    	fmt.Println("Here are all elements in this queue:")
    	for i := 0; i < circleQueue.getQueLength(); i++ {
    		index := (i + circleQueue.Head) % circleQueue.Cap
    		fmt.Printf("index[%d],value=%d\n", index, circleQueue.Arr[index])
    	}
    }
    
    func main() {
    	var c = CircleQueue{
    		Cap:  5,
    		Head: -1,
    		Tail: -1,
    	}
    	c.append(1)
    	c.append(2)
    	c.append(3)
    	c.append(4)
    	c.append(5)
    	c.append(6) // Queue is already full
    	c.list()
    	fmt.Println(c.getQueLength()) // 5
    	c.pop()                       // Pop 1 ok!
    	fmt.Println(c.getQueLength()) // 4
    	c.append(6)                   // Append 6 ok!
    	c.list()                      // 6加入了队尾
    	/*
    		分析:环形队列，弹出后的空间可循环复利用，符合实际使用价值
    	*/
    
    }

**问题**  
循环队列更满足实际使用需求，但毕竟array容量有限，一次申请太大的容量也很浪费资源，怎么解决这个问题？答曰：链表，动态加减元素，独立的内存空间，不需要一次性申请大量内存。  
链表实现参考下篇