循环队列 基本概念「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

循环队列是 队列的一种特殊形式。首先介绍队列，然后引申出循环队列。
队列又称为“先进先出”(FIFO)线性表
限定插入操作只能在队尾进行，而删除操作只能在队首进行
队列也可以采用顺序存储结构或链表结构来实现，分别称为顺序队列和链队列

队列的顺序表示—顺序队列

用一组连续的存储单元依次存放从队首到队尾的元素，附设两个指针head和tail分别指向队首元素和队尾元素的位置，
(有的地方用front 和 rear 表示)

当head = tail = 0时表示空队列

当插入新元素到队尾时，tail加1

当删除队首元素时，head加1，上图如果把C也删掉，那么就 head = tail 了

tail 始终指向队列元素的下一个位置

对应的操作：
队空：head=tail
求队长：tail – head
入队：新元素按 tail 指示位置加入，再将队尾指针加1 ，即 tail = tail + 1
出队：将head指示的元素取出，再将队头指针加1，即head = head + 1

下面引入循环队列

入队，tail指针变化：
tail＝ （tail＋1）％maxsize

出队，head指针变化：
head＝（ head ＋1）％maxsize

删除数据C，队列为空

依次插入数据D,E,F,G,H,I,J,K
队列满：head = tail

队满和队空时，均有head=tail
因此，只凭head=tail 还无法区分是满还是空。

如何判定队列满还是空？

方法1：
用一个计数变量来记载队列中的元素个数
初始化队列时c=0;
当入队时，计数变量＋1（ c=c+1 ）
当出队时，计数变量－1 （c=c-1）
当计数变量＝maxsize时，队满
当计数变量＝0时，队空

方法2：
牺牲一个元素空间，来区别队空或队满。
入队前，先判Q.rear+1是否等于Q.front，
若是则为队满。
而当Q.front=Q.rear时，为队空。
上图中：当数据J入队后，就认为队已满，
而当数据K再要入队时，就拒绝入队。

当队列已经满了，如果允许覆盖之前的数据：

队列已经满了之后，
继续插入数据L,M,N，
之前的数据D,E,F被覆盖
此时，队列已经满了，
最新的数据是：G,H,I，J，K,L,M,N

在程序中，取队列的数据的时候，如果检测到 队列满了，
此时，需要一次性取出队列中的数据，一次性取出数据的时候，不用管head指针，直接按照tail指针指向的位置开始取数据，直到循环取到tail-1位置停止。最终取出的数据的个数是 队列的长度 maxsize
取出之后，可以对队列指针 head 和tail初始化为 0，需要将队列满整个标志设置为False.

当应该用场景如下的时候：
1. 数据是一条一条的进入队列的
2. 队列中的数据是一次性读取的
一次性读取出队列中的所有数据的方式：
因为允许覆盖，有两种情况：
当队列满了之后，
需要根据tail,从tail所在位置的数据，绕一圈到tail-1位置所在的数据，都按照顺序取出来，这些数据是按照顺序，最新的数据。
当队列没有满的时候，
队列中所有的数据是 Head 到 tail之间的所有数据。

参考代码：

# -*- coding:utf-8 -*-

class CircleQueue:

    def __init__(self,maxSize):
        self.head = 0
        self.tail = 0
        self.cnt  = 0
        self.list =[0]*maxSize
        self.size = maxSize

    def is_full(self):
        return self.cnt == self.size

    def is_empty(self):
        return 0 == self.cnt

    def initqueue(self):

        self.head = 0
        self.tail = 0
        self.cnt = 0

    def enqueue(self,element):

        if self.is_full():
            #print 'data: %s' % element, 'pos:%d' % self.tail, 'cnt :%d' % self.cnt
            self.list[self.tail] = element
            self.tail = (self.tail + 1) % self.size

        else:
            #print 'data: %s' % element, 'pos:%d' % self.tail, 'cnt :%d' % self.cnt
            self.list[self.tail] = element
            self.cnt += 1
            self.tail = (self.tail + 1) % self.size

    ''' def dequeue(self): var_list = [] if self.is_empty(): raise Exception('queue is empty') if self.is_full(): raise Exception('queue is empty') var_list.append(self.list[self.head]) self.cnt -= 1 self.head = (self.head + 1) % self.size return var_list '''

    def deClearAllQueue(self):

        var_list =[]

        if self.is_full():

            for i in range(self.tail,self.size):
                var_list.append(self.list[i])

            for i in range(0,self.tail):
                var_list.append(self.list[i])

        else:
            index = self.head

            while True:
                if self.head == self.tail:
                    break

                var_list.append(self.list[self.head])
                self.head = (self.head +1)%self.size


        self.head = 0
        self.tail = 0
        self.cnt = 0

        return var_list




queue = CircleQueue(7)


for i in range(5):
    queue.enqueue(str(i))

var = queue.deClearAllQueue()

print var