数据结构之队列

队列（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)