What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 10:52] – [removeLast()] codingharecs:dsa:courses:gtx_1332x:i_lists:start [2024/02/12 11:30] (当前版本) – [Java 的 modulo 操作] codinghare
行 750: 行 750:
   * addLast() 通过 ''back % capacity'' 维护插入位置   * addLast() 通过 ''back % capacity'' 维护插入位置
   * removeFirst() 通过 ''front % capacity'' 维护删除位置   * removeFirst() 通过 ''front % capacity'' 维护删除位置
-==addFirst()== +==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:52
  • ©2022 YGwiki.com