What & How & Why

您在这里: start » cs » dsa » courses » gtx_1332x » i_lists

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 07:21] – [Queues 的实现（数组）] codingharecs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 11:30] (当前版本) – [Java 的 modulo 操作] codinghare
行 692: 行 692:
   * ''void enqueue(x)''：添加 ''x'' 到队列的最后   * ''void enqueue(x)''：添加 ''x'' 到队列的最后
   * ''x dequeue()''：从队列中移除最先进入的元素   * ''x dequeue()''：从队列中移除最先进入的元素
-  * ''x peak() & x top()''：返回队列的头元素+  * ''x peak() & x top()''：返回队列的最新 dequeue 的元素
   * ''boolean isEmpty()''：检查 size 是否为 0 或者 front 是否为 Null   * ''boolean isEmpty()''：检查 size 是否为 0 或者 front 是否为 Null
   * ''void clear()''：将 front 设置为 null   * ''void clear()''：将 front 设置为 null
行 715: 行 715:
 无论是哪种，我们都没有办法用 //ArrayList// 来实现。因为 //ArrayList// 要求首元素不能为空，且必须连续存储。因此，数组队列只能使用 //Array// 来实现。 无论是哪种，我们都没有办法用 //ArrayList// 来实现。因为 //ArrayList// 要求首元素不能为空，且必须连续存储。因此，数组队列只能使用 //Array// 来实现。
 \\ \\  \\ \\ 
-在观察一下第二种情况。以图为例，这种例子出现的情况是：数列 ''[6,3,11]'' 存储在数组的最后三位。假设我们此时希望对该数列进行 enqueue 的操作；此时 capcity 为 7，数列长度为 3，即便添加一个元素也没有超过数组的容量。但由于存储的位置处于数组的末端，我们没有办法再往里插入新的元素了。\\ \\ +再观察一下第二种情况。以图为例，这种例子出现的情况是：数列 ''[6,3,11]'' 存储在数组的最后三位。假设我们此时希望对该数列进行 enqueue 的操作；此时 capcity 为 7，数列长度为 3，即便添加一个元素也没有超过数组的容量。但由于存储的位置处于数组的末端，我们没有办法再往里插入新的元素了。\\ \\ 
 为了解决这个问题，数组数列的实现引入了循环（//WrapAround//）的机制。如果 enqueue 的位置超出了数组的上限，但数组本身还有空可以做 enqueue 的话，我们就将 enqueue 的位置（back 的位置）往数组前方的空闲位置插入。具体的计算方式为： 为了解决这个问题，数组数列的实现引入了循环（//WrapAround//）的机制。如果 enqueue 的位置超出了数组的上限，但数组本身还有空可以做 enqueue 的话，我们就将 enqueue 的位置（back 的位置）往数组前方的空闲位置插入。具体的计算方式为：
 + \\ 
 $$ $$
 \texttt{back = Index mod Capacity} \texttt{back = Index mod Capacity}
 $$ $$
 +以上图为例，我们原来希望插入的位置是 index = 7（当然没有 7），通过上述转换之后就是在 index = 0 处 enqueue 了。
 +<WRAP center round box 100%>
 +''back''（起点） 并不是必须的。知道 ''front''（终点）和 ''size'' 长度，就可以计算出起点。
 +</WRAP>
 +
 ==enqueue== ==enqueue==
-//Eneuque// 在数组队列中的实现需要维护一个循环的（//Wrap around//）的 index。循环的大小与 capacity 挂钩。比如我们从 index 0 开始，使用 ''back'' 指针记录当前 enqueue 对象的 index。假设整个数组 capacity 为 7，那么 back 的取值范围就是 ''[0, 7)''。 当 Index 为 7 的时候已经超出了整个数组队列的范围了，因此 enqueue 的位置需要回滚到整个数组队列的首位 0。按照这种思路，''back'' 的计算方式为： +===Priority queues=== 
-$$ +//Priority queues// 是另外一种线性的 ADT。其特点是，当前移除的对象是**优先级最高的对象** 。这种 ADT 通常用于搜寻最大最小值。 由于有大小的存在，Priority queues 中的对象必须是 Comparable 的。 
-\texttt{back} = \texttt{Index mod Capacity} +==功能与效率性== 
-$$  +Priority queues 会分为两个区：一个 Priority 区和一个备选区。Priority 区中存放优先级最高的数据用于操作。当 Priority 区中的数据移除后，备选区需要通过另一轮筛选选出下一个优先级最高的数据推送到 Priority 区中，以便接下来的操作。 
-为什么需要这么做呢？+\\ \\  
 +可以注意到，每处理一轮 Priority 区中的数据，备选区中的数据就需要排序一次，为了更好的效率，具体实现是基于 heap 的。 
 +<WRAP center round box 100%> 
 +Priority queues 是线性类型的 ADT，但使用线性数据结构实现确十分低效。不论使用数组还是链表，我们都需要Priority queue 是一个有序数列。这意味着，每次 enqueue 需要进行一次排序（链表需要遍历到插入新元素的位置），也就是每次 enqueue 的复杂度都在 $O(n)$。这样是非常不效率的。 
 +</WRAP> 
 +===Deques=== 
 +//Deques//，指 //Double-ended queue//。//Deque// 允许在队列的两端添加和删除元素。//Deque// 不支持随机访问（添加删除）以及搜寻操作。 
 +==Deque 的方法== 
 +  * ''void addFirst(x)''：在 Deque 队首添加元素 
 +  * ''void addLast(x)''：在 Deque 队尾添加元素 
 +  * ''x removeFirst()''：在 Deque 队首删除元素 
 +  * ''x removeLast()''：在 Deque 队尾删除元素 
 +  * ''boolean isEmpty()'' 
 +  * ''int size()'' 
 +===Deque 的实现（数组）=== 
 +//Deque// 的数组实现同样需要使用到循环的方式。 
 +==addLast() & removeFirst()== 
 +  * addLast() 通过 ''back % capacity'' 维护插入位置 
 +  * removeFirst() 通过 ''front % capacity'' 维护删除位置 
 +==addFirst() & removeLast()== 
 +这两个方法也需要通过循环的方式进行位置的维护。但由于其进出方向与之前的两个方法完全相反，如果使用同样的 ''back'' & ''front'' 指针，那么指针移动的操作是减而不是加。这意味着指针指向的 Index 很可能会变为负数，也就是会出现向前循环的情况。这种情况下，我们需要进行手动判断并做出以下处理： 
 +<code java> 
 +//this applied to back as well 
 +if (front < 0) { 
 +    front  = capacity - front; 
 +} 
 +</code> 
 +<WRAP center round box 100%> 
 +所有的操作（除开 resize）都是 $O(1)$，总的说来是 $O(1)^*$ 
 +</WRAP> 
 +==Java 的 modulo 操作== 
 +通常情况下，末除是一个分类的过程。所有余数相同的数字都会被放入到一个类中。在这个类中，**最小的**，**非负的成员**会成为余数。这导致了负数做末除时存在着不同。比如 $9 % 5 = 4$；但进行 $-9 % 5$ 时，因为要保证余数非负，取余的方向实际上需要更往负数方向上进行。比如这里，如果之间按正数的取余方式 $-9$ 去除 $(-1)\times5$ 还有 $-4$，但由于需要余数为正，因此需要再去除一个 $(-1)\times5$。因此余数是 $1$。\\ \\  
 +但在 Java 中，余数的结果并不要求为正，而是**最接近 0 的数**。这种情况是我们之前讨论的第一种情况：''9 % -5 = -4''。 
 +===Deque 的实现（链表）=== 
 +//Deque// 的实现需要使用**双链表**（DLL）： 
 +  * //add first// & //remove first// 均在 head 处操作 
 +  * //add fisrt// & //remove last// 均在 tail 处操作 
 +由于使用双链表，所有的操作都是 ($O(1)$) 
  • 最后更改: 2024/02/12 07:21
  • ©2022 YGwiki.com