python中的数据结构和算法

Question

Q1-假设最初为空的队列Q已执行了总共32个队列操作，10个首次操作和15个出队操作，其中5个引发了被捕获和忽略的空错误。目前是什么Q的大小？

我认为这个问题的答案是22;但在这个问题上我需要帮助...

Q2-如果先前问题的队列是ArrayQueue的实例最初使用容量为30的数组，并且其大小从未大于大于30，前端实例变量的最终值是多少？

Answer 1

首先严格定义队列上的操作将有帮助：

• void Enqueue（Item）-将Item插入队列的末尾。
• 项目出队-删除并返回队列前面的项目。如果在调用操作时队列为空，则抛出空错误。
• Item First-返回队列前面的Item，不要删除它。

这意味着Enqueues将队列的大小加1，如果队列的大小大于0，则Dequeues从队列的大小中删除一个，并且Firsts不会影响队列的大小。

因此，我们有32个增量，10个无操作和15个潜在递减。这些潜在的减量中有五个不会影响队列大小，因此仅剩下十个。

32 * 1 + 10 * 0 + 5 * 0 + 10 * -1 = 22

仅当操作如上定义时才有效。例如，如果我们将Enqueue和Dequeue的定义更改为如下形式：

• 无效入队（项目列表）-将列表中的每个项目插入队列的末尾。
• 项目列表出队（计数）-从队列的开头删除并返回计数项目。返回最大（计数，队列大小）项目。

现在，我们没有足够的信息来回答问题。这就是为什么要精确考虑要考虑的操作很重要的原因。

关于第二个问题，假设ArrayQueue被实现为大小为30的圆形数组缓冲区（具有指向“ front”和“ back”元素的指针的30个元素的数组），并且假定Enqueues发生在“ back”上并且出队发生在“前端”，那么我们要做的就是计算出队的数量，因为这是唯一影响前端指针的操作。

15种可能的操作可以更改前端的位置。其中5个不会更改前面板的位置，因此前面板总共移动了10次。假设数组是零索引的，则front将指向数组索引10（第11个项目，准备进行下一个出队或第一个操作）。

ArrayArray的不同实现会有不同的答案。同样，在尝试推理其内部工作原理时，有助于具体说明结构的实现。