环形队列

#-*- coding=utf-8 -*-

# 环形队列实现
class CircleQueue:
    # 队列头
    queueHead = 0
    # 队列尾
    queueTail = 0
    # 队列容量
    queueCacity = 0
    # 队列当前长度
    queueLength = 0
    # 队列容器
    queue = []

    def __init__(self, capacity):
        self.queueCacity = capacity
        self.queue = [0] * capacity

    # 入列
    def enqueue(self, obj):
        if(self.isFull()):
            raise RuntimeError("Queue is Full")

        self.queue[self.queueTail] = obj
        self.queueTail += 1
        # 为了让队列头一直在环形队列中进行变化, 因此进行取余操作,
        # 当队列头达到最大容量时,再增长就回到初始队列头的位置
        self.queueTail = self.queueTail % self.queueCacity
        self.queueLength += 1

        return self.queueLength

    # 出列
    def dequeue(self):
        if(self.isEmpoty()):
            raise RuntimeError("Queue is Empoty")
        obj = self.queue[self.queueHead]
        self.queueHead += 1
        self.queueHead = self.queueHead % self.queueCacity
        self.queueLength -= 1
        return obj

    # 判断队列是否为空
    def isEmpoty(self):
        return self.queueLength == 0

    # 判断队列是否已满
    def isFull(self):
        return self.queueLength == self.queueCacity


# 测试
circleQueue = CircleQueue(5)

# 入列5个元素
assert circleQueue.enqueue(1) == 1
assert circleQueue.enqueue(2) == 2
assert circleQueue.enqueue(3) == 3
assert circleQueue.enqueue(4) == 4
assert circleQueue.enqueue(5) == 5

# 现在队列的长度为5, 且队列尾已经和队列头重合了
assert circleQueue.queueLength == 5
assert circleQueue.queueTail == 0
assert circleQueue.queueHead == 0

assert circleQueue.dequeue() == 1
assert circleQueue.dequeue() == 2
assert circleQueue.dequeue() == 3
assert circleQueue.dequeue() == 4
assert circleQueue.dequeue() == 5

assert circleQueue.queueTail == 0
assert circleQueue.queueHead == 0

# 再入列一个数据,当前长度为1,且队列头为0,队列尾为1
assert circleQueue.enqueue(6) == 1

assert circleQueue.queueTail == 1
assert circleQueue.queueHead == 0

环形队列的关键是能让头索引和尾索引能够在整个环形队列中自己循环