循环队列基本知识与代码

循环队列

长度由谁定

• 在栈中，栈底指针保持不变，有元素入栈，栈顶指名增加，有元素出栈，栈顶指针减少。
• 在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。
• 在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的。
• 线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入或删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度。

队列

• 队列是先进先出的线性结构
• 进的一端称为队尾，出的一端称为队头，队列可以用顺序存储也可以用链式存储。
  • 插入元素时，尾指针所在位置先赋值，再往后移动一位，也就是说，尾指针不是指向最后元素位置，而是更后一位
  • 顺序存储和链式存储有什么区别？

顺序存储和链式存储的区别

• 1.链表存储结构的内存地址不一定是连续的，但顺序存储结构的内存地址一定是连续的
• 2.链式存储适用于频繁地插入、删除、更新元素的情况，而顺序存储结构适用于频繁查询。

队列的假溢出现象

• 队列的空间未利用完,但是却造成了元素的溢出(又称"假溢出")
• 
• 为了应对这个问题，提出循环队列

判断队列空和队列满

https://blog.csdn.net/lilililililiki/article/details/104317286

• 有三种方式来应对：
• 1.设计标记位
• 2.牺牲一个存储位置
• 3.count有效元素的个数

1.设计标记位

设置初始标记：  flag=false

当入队列时，让rear往后移动，让flag=true
当出队列时，让front往后移动，让flag=false

当队列为空时： rear == front && flag==false
当队列为满时： rear == front && flag == true

1
2
3
4
5
6
7
8

• 可以看到，在这种结构下，队空和队满都有前指针位置=尾指针位置
• 那这个flag的意义，就是看最后操作的状态是啥，如果是false,那最后的状态要么是出队列，要么就直接是没有元素入队的初始状态，也就是空队列状态，如果是true，那么上一个状态就是元素入队列，如果再满足rear==front，就肯定是队列满了呀

2.牺牲一个存储位置

当队列为空时条件：rear == front

当队列满时条件为：（rear+1）% maxsize == front
1
2
3

3.count有效元素的个数

• 队列为空时，count == 0

• 当有元素入队时，count++，当count和队列的maxsize相等时，代表队列已满

进队、出队、计算元素个数

进队：front = (front + 1) % maxSize
出队：rear = (rear + 1) % maxSize
队列中元素的个数 m = (rear - front + maxSize) % maxSize
1
2
3

python代码

• 判断队列是满是空，这里采用的方式是减少一个存储位
• 虽然之前说的是rear指针指向的是最后一个元素的下一位，但是给人用的时候，Rear()函数的功能得是指出最后一个元素值

class MyCircularQueue:

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        :type k: int
        """
        self.size = k+1
        self.data = [0]*self.size
        self.head = self.rear = 0

    def enQueue(self, value):
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear+1)%self.size
        return True
    def deQueue(self):
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.head = (self.head+1)%self.size
        return True
        
    def Front(self):
        """
        Get the front item from the queue.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        return self.data[self.head]
        

    def Rear(self):
        """
        Get the last item from the queue.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        return self.data[(self.rear-1)%self.size]

    def isEmpty(self):
        """
        Checks whether the circular queue is empty or not.
        :rtype: bool
        """
        return self.head ==self.rear
        

    def isFull(self):
        """
        Checks whether the circular queue is full or not.
        :rtype: bool
        """
        return (self.head - self.rear)%self.size ==1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66