What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 07:37] – [数组与循环机制] 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
行 727: 行 727:
  
 ==enqueue== ==enqueue==
 +===Priority queues===
 +//Priority queues// 是另外一种线性的 ADT。其特点是，当前移除的对象是**优先级最高的对象** 。这种 ADT 通常用于搜寻最大最小值。 由于有大小的存在，Priority queues 中的对象必须是 Comparable 的。
 +==功能与效率性==
 +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:37
  • ©2022 YGwiki.com