What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 10:04] – [Deque 的方法] codingharecs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 11:30] (当前版本) – [Java 的 modulo 操作] codinghare
行 746: 行 746:
   * ''int size()''   * ''int size()''
 ===Deque 的实现（数组）=== ===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 10:04
  • ©2022 YGwiki.com