阅读 162

数据结构之队列——输出杨辉三角形

定义

队列是一种操作受限的线性表,只允许在一端进行插入,另一端进行删除。插入的一端称为队尾,删除的一端称为队头,由于这样的限制,所以队列具有先进先出的特性,因此队列也是一种先进先出的线性表。

顺序存储

队列的顺序存储结构,除了存储的数组,还需要一个队尾指针(rear),和队头指针(front),初始化队列的时候,rear和front都指向同一个下标0,这shi队为空。

  • 当一个元素入队,队尾指针+1
  • 当一个元素出队,队头指针+1
  • 在非空队列中,队头指针始终指向对头元素,而队尾指针始终指向队尾元素的下一个位置

在这种情况下,会出现假溢出现象,因为入队和出队操作中,头,尾指针都只增加,不减少,导致被删除的元素空间永远无法重新利用。即尽管队列中的元素个数远远小于数组的大小,但由于尾指针已经超出数组的上界,导致不能进行入队操作,这种现象称为假溢出

数组大小为4,队列操作时,头、尾指针变化过程如下图

循环队列

为了克服假溢出,可以怎么改进呢?很自然的就想到,把新的元素放到空余的空间里,即又回到数组下标0位置处,这样看上去就像一个首尾相接的圆环,这种队列称为循环队列

循环队列的出队和入队,仍然是头,尾指针加一,只不过当头,尾指针到达数组上界时,加1操作,又回到了下界0处。

// i 代表头,尾指针
if i+1 == maxSize {
    i = 0
} else {
    i++
}
复制代码

上述的这种操作,可以使用求模运算简化,即i = (i+1) % maxSize,这样就能充分利用数组上的所有空间,除非数组空间被占满,否则不会造成溢出。 来看下循环队列,头尾指针的变化过程。

从中会发现一个问题,当front == rear的时候,有可能是队空,也可能是队满。为什么会出现这个问题呢?

我们以队列最大容量为4,来分析这个问题:

  • 首先,是以front,rear的相对位置来判断队列的状态,那么front,rear的相对位置有:0,1,2,3四种情况
  • 实际上,队列里的状态有:0(空队列),1个元素,2个元素,3个元素,4个元素(队满)五种情况
  • so,要用4种情况来区分5种情况,很显然,不合实际

怎么解决呢?一般都两种方案:

1、使用额外的标志位tag,当入队的时候,把tag设置成1,当出队的时候,把tag设置成0,那么当front==rear时,就可以通过tag的值来判断是空队,还是满队

2、少用一个空间,即数组最大容量为4,但我们只用3个容量,这样判断空队列仍然是front==rear,而判断队列是否满,则就变成(rear+1)%maxSize == front,则为满。(下面的实例代码,以此方案实现)即如下图

当然,也可以使用链式存储的方式来构建队列,如果使用链式,就不存在容量的问题,这样也就不需要判断队满。

主要操作

结构描述

type data interface{}

type Queue struct {
	list    []data
	front   int // 头指针
	rear    int // 尾指针
	maxSize int // 最大容量
}

func New(maxSize int) *Queue {
	q := &Queue{
		list:    make([]data, maxSize+1),
		front:   0,
		rear:    0,
		maxSize: maxSize + 1, // 空余一个容量不使用
	}
	return q
}
复制代码

判满

func (q *Queue) IsFull() bool {
	return (q.rear + 1) % q.maxSize == q.front
}
复制代码

判空

func (q *Queue) IsEmpty() bool {
	return q.front == q.rear
}
复制代码

入队

判断队是否已经满,满就报错,否则入队

func (q *Queue) Enqueue(value data) (bool, error) {
	if q.IsFull() {
		return false, errors.New("队已满")
	}
	q.list[q.rear] = value
	q.rear = (q.rear + 1) % q.maxSize
	return true, nil
}
复制代码

出队

队为空,则报错,否则出队

func (q *Queue) Dequeue() (data, error) {
	if q.IsEmpty() {
		return nil, errors.New("队为空")
	}
	value := q.list[q.front]
	q.list[q.front] = nil
	q.front = (q.front + 1) % q.maxSize
	return value, nil
}
复制代码

获取队头的值

func (q *Queue) GetHead() (data, error) {
	if q.IsEmpty() {
		return nil, errors.New("队为空")
	}
	return q.list[q.front], nil
}
复制代码

应用:输出杨辉三角形

杨辉三角,是二项式系数在三角形中的一种几何排列,如下图

它有两个比较显著的特点:

  • 每行最两端的值为1
  • 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角,即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,即 C(n+1,i)=C(n,i)+C(n,i-1)。

基于以上的性质,使用程序输入杨辉三角的时候,一种想法就是,利用两个数组,在输出当前行的时候,就计算下一行的值,放到另一个数组里,两个数组交替使用。

第二种方案,我们可以利用队列来输出,在空间上可以减少一个数组,在使用队列输出的杨辉三角的时候,有一个小技巧,就是在每行的两端添加两个0,即成如下的形式

  0 1 0
 0 1 1 0
0 1 2 1 0 
复制代码

在这个前提下,算法思路(n代表行数):

1、初始化一个队列,将第一列 0 1 0 依次入队;

2、此时每一行的元素个数为n + 2,依次出队并输出该行的每一个元素,0出队但不输出;

3、在元素出队的同时,计算下一行对应位置的数值,即出队元素 + 新的队头元素,并把计算得到的值入队

4、当该行的每一个元素都输出完了,队列里也就计算好了下一行的元素,此时再把0入队,这个0即是这一行结束的0,也是下一行开始的0

5、重复2,3,4直到n结束。

我们以 n = 4为例,看看队列里元素的变化:

const maxSize = 1000

func printYangHui(n int) {
	q := Queue.New(maxSize)
	q.Enqueue(0)
	q.Enqueue(1)
	q.Enqueue(0)
	for i := 1; i <= n; i++ {
		formatPrint(n-i) // 格式化输出
		for j := 1; j < i+2; j++ {
			// 第i行,在队列中有i + 2个数字,包括头尾两个0,
			//    0 1 0
			//   0 1 1 0
			//  0 1 2 1 0
			s, _ := q.Dequeue()
			if s != 0 {
				fmt.Printf(" %d", s)
			}
			t, _ := q.GetHead()
			q.Enqueue(s.(int) + t.(int)) // 下一行中的数字就是其左右肩之和
		}
		q.Enqueue(0) // 再把每行的0入队
		fmt.Println()
	}
}

printYangHui(4) // 结果如下图
复制代码

总结

以上的应用只是队列的一个小应用,理论上数据流符合先进先出的规则,都可以考虑使用队列解决问题。比如打印机的打印调度,先进的内容,会被先打印出来,等等。

Thanks!

关注下面的标签,发现更多相似文章
评论