为什么 尾-首 还要+1?

jike_0227968 Python 数据结构初识 最后由 极客学院-媛儿 于2015年07月30日回复

  • 5 回答
  • 2.3k 浏览

 def Full(qu):

        if qu.tail-qu.head+1==qu.size:

            return True

        else:

            return False

  • nylqd 2015年06月20日 回答 #2楼
  • 应该是不要 1的,最开始(size=0,head=-1,tail=-1),添加一个元素(size=0,head=-1,tail=0),添加两个元素(size=2,head=-1,tail=1 )就是tail-head就好了,视频中讲述的是顺序队列,其中tail应该是指向队尾元素的后一个位置的,而不是最后一个元素,所以应该不要 1

    可以参见动画演示

  • 3 评论
  • weibo_jh5dgc94 2015年07月27日 回答 #3楼
  • 他应该写错了,不需要 1的,因为头尾赋值初始值都是-1,如果相减等于零就是队列为空的,要不然两个语句就矛盾了!

  • 0 评论
  • 韦玮 2015年07月30日 回答 #4楼
  • nylqd的理解正确。此时不需要加一。但是请各位学员看一下后面的分析,否者理解不会深入,大家想一下,如果这里硬要加一,那么原程序怎么改,才不会出错。大家想想这个问题,如果想出了,就算真正理解了。

    我先提供点思路:

    原程序之所以加1是因为考虑到,tail-head加1==size的时候,队尾指针恰好指在最后一个元素。但是没考虑到,队尾指针虽指在这里,但此时最后一个空间仍然是还可以放一个元素的,所以此时如果最后一个空间还没填满就判断队满不合适。故而从数学上来说,tail-head的值就恰好是填完这个最后空间后tail指针所在位置,但是tail指针现在从逻辑上是不存在的,因为每次入队操作后,tail指针都会自动加一,而最多最多,tail指针只能指到长度的最后,再加一就不知道去哪了,所以这里就出现了矛盾。矛盾点1:tail-head加1==size的时候,此时tail指针已经指到最后了,再入队,tail指针去哪呢?也就是说,要在head-tail==size的时候才判断队满,此时队尾指针根本就不知在哪了,逻辑上不存在。2.此时tail-head加1==size的时候,队尾指针已在最后,但是此时确实还能容纳一个元素,此时就判断队满,也不合适,因为我最后一个元素还没进呢。问:到底什么时候判断队满才合适?大家先考虑,如果这里硬要加一,原程序怎么修改,才能正确,想清楚这个问题,我们自然能够想明白什么时候判断队满才合适。我下面给出改后程序,但是大家先别看,先自己想想。

    以下是修改后的程序:

    #队列的实现

    class Queue():

        def __init__(qu,size):

            qu.queue=[];

            qu.size=size;

            qu.head=-1;

            qu.tail=-1;

        def Empty(qu):

            if qu.head==qu.tail:

                return True

            else:

                return False

        def Full(qu):

            if qu.tail-qu.head 1==qu.size:

                return True

            else:

                return False

        def enQueue(qu,content):

            if qu.Full():

                qu.queue.append(content)

                print "此元素已进入队列,但接下来Queue is Full!"

            else:

                qu.queue.append(content)

                qu.tail=qu.tail 1

        def outQueue(qu):

            if qu.Empty():

                print "Queue is Empty!"

            else:

                qu.head=qu.head 1

    大家注意观察一下,我们此时只改了一个地方,我们将入队操作部分

    def enQueue(qu,content):

            if qu.Full():

                print "Queue is Full!"

    改成了

    def enQueue(qu,content):

            if qu.Full():

                qu.queue.append(content)

                print "此元素已进入队列,但接下来Queue is Full!"

    为什么呢?

    我们仍然保留了加1来判断队满,因为加1的时候确实就是队满的临界条件。但是虽然现在队尾指针指向了最后,但此时仍可以容纳一个元素,故而我们此时再进一个元素:qu.queue.append(content),进了这个元素之后,接下来我们的队就满了,故而接下直接输出  print "此元素已进入队列,但接下来Queue is Full!"。至此,完美解决。

    也就是说,确实是在qu.tail-qu.head 1==qu.size:的时候队满,但是此时虽队尾指针指向最后位置,此位置仍能容纳一个元素,故而我们先把这个元素放进去,再说接下来队满。

  • 3 评论