队列(Queue)是一个数据集合,仅允许在列表的一段进行插入,另一端进行删除。进行插入的一段称为队尾(rear),插入动作称为进队或者入队。进行删除的一段称为队头(front),删除动作称为出队。

队列性质:先进先出(First-in, First-out)

环形队列

1)当队尾指针 rear=size+1 时,再前进一个位置就自动到0.

2)队首指针前进1:front = (front+1) % size

3)队尾指针前进1:rear = (rear+1) % size

4)队空条件:rear == front

5)队满条件:(rear+1) % size = front

代码示例

class Queue():
    def __init__(self, size):
        self.size = size + 1
        self.queue = [None] * self.size
        self.front = 0
        self.rear = 0
        
    def push(self, elem):
        if not self.is_fulled():
            self.queue[self.rear] = elem
            self.rear = (self.rear + 1) % self.size
        else:
            raise IndexError('queue is fulled.')

    def pop(self):
        if not self.is_empty():
            elem = self.queue[self.front]
            self.front = (self.front+1) % self.size
            return elem
        else:
            raise IndexError('queue is empty.')

    def is_empty(self):
        return self.front == self.rear

    def is_fulled(self):
        return (self.rear + 1) % self.size == self.front

q = Queue(4)
q.push(1)
q.push(2)
q.push(3)
q.push(4)
print(q.queue)
print(q.pop())
q.push(5)
print(q.queue)
q.push(6)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/303