运维开发网

7. 队列(2)

运维开发网 https://www.qedev.com 2020-02-22 15:21 出处:51CTO 作者:听丶飞鸟说
上面用单链表实现队列,这里用数组实现队列:需要两个指针:head和tailhead=0,tail=0 两个指针默认是0,都指向数组的首部PUSH操作:每当push的时候,只要将head当前指向的位置赋新值,使head前移就可以如图,实现数组的push操作:push 0 的时候,将head当前指向的赋为0,将head前移push 1 的时候,将head当前指向的赋为1,将head前移...POP操作

上面用单链表实现队列,这里用数组实现队列:

需要两个指针:head和tail

head=0,tail=0 两个指针默认是0,都指向数组的首部

7. 队列(2)

PUSH操作:

每当push的时候,只要将head当前指向的位置赋新值,使head前移就可以

7. 队列(2)

如图,实现数组的push操作:

push 0 的时候,将head当前指向的赋为0,将head前移

push 1 的时候,将head当前指向的赋为1,将head前移

...

POP操作:

队列是先进先出的,应该0先出来

7. 队列(2)

如上图:

pop操作也是从首部开始,

先pop( )将tail的值拿出来,return 0,将tail前移;

再pop( )将tail的值拿出来,return 1,将tail前移。

以上,通过这两个数组指针的前移操作,实现数组的队列,但是必须要保证Queue的长度,即 len(Queue) <= array_size;

如果队列已经到头了,只要回来就行了,重新赋值,如下图:

7. 队列(2)

只要用一个取模(余)操作,比上数组的size,就能让队列重新回来赋值。

公式:h % array_size

将用到之前构建的数组Array()的类,到数组队列中去:

代码如下:

class ArrayQueue(object):
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.array = Array(maxsize)     #底层实现是Array类
        self.head = 0
        self.tail = 0                   #需要两个指针节点,标记头和尾的位置

    def push(self, value):
        if len(self) >= self.maxsize:
            raise Exception('Queue Full')
        self.array[self.head % self.maxsize] = value
        self.head += 1                  #前移头指针

    def pop(self):
        value = self.array[self.tail % self.maxsize]
        self.tail += 1
        return value


def test_array_queue():
    import pytest           #引入pytest
    size = 5                #定义szie=5
    q = ArrayQueue(size)    #定义长度为size的队列
    for i in range(size):   #循环从0到4的中间数据调用
        q.push(i)
    with pytest.raises(Exception) as excinfo: #判断异常是否生效,当队列满了就会出现异常
        q.push(size)
    assert 'Queue Full' in str(excinfo.value)

    assert len(q) == size   #断言当前q队列的长度等于size的值,一被push满
    assert q.pop() == 0     #先进先出,第一个出来的是0
    assert q.pop() == 1      
    q.push(5)               #再push一个5进入队列
    assert len(q) == 4      
    assert q.pop() == 2
    assert q.pop() == 3
    assert q.pop() == 4
    assert q.pop() == 5
    assert len(q) == 0

编写test.sh文件,之前安装了when-changed

#!/bin/bash
when-changed -v -r -1 -S ./ "py.test -s $1"

#test.sh   array_queue.py

0

上一篇:

:下一篇

精彩评论

暂无评论...
验证码 换一张
取 消