Circular Queue

题目描述

Implement a circular queue using simple array.

解题方法

维护两个变量，记录queue的开头和结尾，分别用作dequeue和enqueue

• head
• tail

如何判断queue是否为空呢，仅用head和tail判断是不行的，因为这样空queue和 full queue的状态是一样的，所以再加一个变量num_elements

当queue满了的时候，我们需要resize the array, 一般是double the size，而这时候 circular queue里的elements就应该reorder, head和tail的位置也应该reset。

reorder的规则就是将head reset到0的位置，相当于重新从头排列，这里我们可以根据 现在head的位置对array的elements进行shift。

python rotate

python的deque有rotate的method, 而如果一定要用array,我们可以自己implement一个 rotate()

Solution

def rotate(l, n):
    return l[-n:] + l[:-n]

class Queue(object):

    def __init__(self, size):
        self.queue = [None] * size
        self.size = size
        self.head = 0
        self.tail = 0
        self.num_elements = 0

    def enqueue(self, val):
        if self.num_elements == self.size: # full, need resize
            # 先rotate & reset
            rotate(self.queue, -head) # rotate to the left
            self.head = 0
            self.tail = self.num_elements
            self.queue += [None] * self.size
            self.size *= 2
        self.queue[self.tail] = val
        self.tail = (self.tail + 1) % self..size
        self.num_elements += 1

    def dequeue(self):
        if self.num_elements != 0:
            result = self.queue[head]
            self.head = (self.head + 1) % self.size
            self.num_elements -= 1
            return result
        else:
            raise

Reference