IT评测·应用市场-qidao123.com
标题:
【数据结构】循环队列原理与代码
[打印本页]
作者:
用多少眼泪才能让你相信
时间:
2024-12-14 01:56
标题:
【数据结构】循环队列原理与代码
理论
存在的意义：
将序次队列从逻辑上视为一个环。解决“假溢出”（出队入队连续操作后两个指针均到数组末了maxsize-1处，虽然队里没有元素但无法让元素进队）。
两种定义
1.标题是队列非空时队头指针和队尾指针分别指向队头元素和队尾元素时，则初始时front=0,rear=n-1，每次入队时rear++再放新元素。
这种情况下 q.front=(q.rear+maxsize-q.length+1)%maxsize
2.而队尾指针指向队尾元素的下一个时，则front=rear=0，每次入队时先放新元素再rear++;
这种情况下 q.front==(q.rear+maxsize-q.length)%maxsize
总结：front初始只有大概为0！
严蔚敏版的定义
【严书规定】初始front=rear=0；非空队列中头指针始终指向队头，尾指针始终指向队尾的下一个位置。
初始：Q.front=Q.rear=0;
进队：Q.rear=(Q.rear+1)%MaxSize;
出队：Q.front=(Q.front+1)%MaxSize;
队列长度 (Q.rear-Q.front+MaxSize)%MaxSize;
区分队满的三种解决办法
牺牲一个单元，入队时少用一个队列单元，否则队空队满的判断条件相同导致无法确定。
队满条件：(Q.rear+1)%MaxSize==Q.front;//rear所指的单元始终为空。
队空条件：Q.rear=Q.front;
队列长度
Q.rear-Q.front+MaxSize)%MaxSize;
增设表现元素个数数据成员Q.size
增设tag，删除时tag=0;入队时tag=1;当Q.front==Q.rear时可区分。（操作完后检查空满并赋值tag）
注意：出队入队之前的检查空满的条件
循环链队判空：rear->next ==rear
代码练习
https://www.lintcode.com/problem/955/
class CircularQueue:
def __init__(self, n):
# do intialization if necessary
self.arr = [None]*n
self.head, self.tail = 0, -1 #队尾先+1再放元素
self.size = n
"""
@return: return true if the array is full
"""
def isFull(self):
return self.head == (self.tail + 1) % self.size and not self.arr[self.tail] is None
"""
@return: return true if there is no element in the array
"""
def isEmpty(self):
return self.arr[self.tail] is None #队尾始终指向最后一个元素
"""
@param element: the element given to be added
@return: nothing
"""
def enqueue(self, element):
self.tail = (self.tail + 1) % self.size
self.arr[self.tail] = element
"""
@return: pop an element from the queue
"""
def dequeue(self):
ele = self.arr[self.head]
self.arr[self.head] = None
self.head = (self.head + 1) % self.size
return ele
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)
Powered by Discuz! X3.4
Q.rear-Q.front+MaxSize)%MaxSize;Q.rear-Q.front+MaxSize)%MaxSize;