chapter_stack_and_queue/deque/

[giscus[bot]]

chapter_stack_and_queue/deque/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_stack_and_queue/deque/

[13422703801]

hi

[rookiexxj]

大佬，我看你在很多地方用了： 在python里是指解释说明吗，就是不影响实际程序运行。
如 self.next: ListNode | None = None

[krahets]

@rookiexxj 是的，可以把它理解为注释，增强可读性的，实际上无法限制变量的类型

[Teamsaa]

我想问一下K神，双向队列的具体操作体现在哪呢，我看大话数据结构中没有讲到这个，有点好奇它的实际应用，因为我细看了这一章节，更像是两个栈拼接在了一起

[krahets]

好问题，的确双向队列就像是栈和队列的组合，或者是两个栈拼在了一起；它表现的是栈 + 队列的逻辑，因此可以实现栈与队列的所有应用，并且更加灵活。

示例请见更新的 5.3.3. 双向队列应用

[deeprado]

撤销，如何实现呢，是通过移动指针吗？ 那部分软件支持ctrl+z 和 ctrl+y (比如idea)，具体要如何实现呢

[krahets]

@deeprado 使用两个堆栈，栈 A 用于撤销，栈 B 用于反撤销。

1. 每当用户执行一个操作，将这个操作压入栈 A ，并清空栈 B 。
2. 当用户执行“撤销”时，从栈 A 中弹出最近的操作，并将其压入栈 B 。
3. 当用户执行“反撤销”时，从栈 B 中弹出最近的操作，并将其压入栈 A 。

[PPcattt]

// 当 i 越过数组头部后，回到尾部
return (i + capacity()) % capacity();
怎样算越过头部？直接用i对capacity()取余不可以吗？

[krahets]

当进行头部插入时，有可能会越过数组头部，此时 i = -1 ，直接对 capacity() 取余结果不对，需要先加 capacity() 。详见负数取余定义。

[Eyrum]

array_deque 队尾出队 popLast 方法不需要重设 rear 指针吗？

[Eyrum]

哦，环形数组队列不需要尾指针

[krahets]

确实，用 front 和 size 来维护首尾～

[highlineee]

k神，基于双向链表的实现的图里，step4的popLast应该pop掉5吧？

[krahets]

Hi～ pop 掉的是节点 4 ，也就是上一张图中那个蓝绿色的节点。

[highlineee]

看岔了，感谢K大佬~

[lavamooncake-816]

def pop(self, is_front: bool) -> int:
"""出队操作"""
# 若队列为空，直接返回 None
if self.is_empty():
return None
# 队首出队操作
if is_front:
val: int = self.front.val # 暂存头节点值
# 删除头节点
fnext: ListNode | None = self.front.next
if fnext != None:
fnext.prev = None
self.front.next = None
self.front = fnext # 更新头节点 我想请问一下，这里的第二个if可以换成elif吗

[krahets]

Hi 可以的。因为第一个 if 执行的是 return 操作，所以第二个分支通常写 if ，这样逻辑更清晰，代表第一个分支进行了“提前返回”

[lavamooncake-816]

啊原来是这样，非常感谢快速回复！

[lavamooncake-816]

我想请问一下这部分代码：
fnext: ListNode | None = self.front.next
if fnext != None:
fnext.prev = None
self.front.next = None
self.front = fnext
我理解是，如果 fnext 为空，照样更新 front node 为 None（通过移动指针pop掉front node）。如果 fnext 不为空，通过 ‘fnext.prev = None’ pop 掉 front node，但为什么还要 ‘self.front.next = None’ 呢，这不是将两个元素 pop 掉了嘛，而且也没有更新节点？以及我还想再请问一下，这里为什么不像之前“基于链表实现的队列”中那样，仅通过移动指针 pop 元素，为什么还需要设 None 呢？

[krahets]

这里想要做的是将 front 指向 fnext ，而当 fnext != None 时，我们需要手动断开 front 和 fnext 的双向链接。只移动的话，被删除的节点仍然是可达的，因为这是一条双向链表。

[lavamooncake-816]

啊明白了，非常感谢！

[xiaobao1231]

补充回复None在Python中是没有Next的，也就是没有指针，空指针的意思

[xiaobao1231]

另外原来的self.front一定要指向非空元素吗，感觉直接把下一个节点指向空，self.front为下一个节点就行了吧

[krahets]

@xiaobao1231 Hi，self.front 也可以不指向非空元素，因为已经无法访问到它，在逻辑上它已经不在链表中了。但是可能会导致一些少见的内存回收 Bug ，详见断开连接对内存回收的影响。

[learntochangecode]

感觉这个地方会出bug啊
if (isFront) {
val = front.val; // 暂存头节点值
// 删除头节点
ListNode fNext = front.next;
if (fNext != null) {
fNext.prev = null;
front.next = null;
}
front = fNext; // 更新头节点
如果说这个队列只有一个节点的时候，代码只将front指针移动了，rear指针没有移动，还是指向原来的front。而进行出队操作后，正确的情况是front=rear=null，这段代码的运行结果是front=null，rear指向原来的front，不等于null。
不知道我想的对不对，请大佬指教。

[krahets]

你说的没错，rear 的指向没有被改变。但对于用户而言，访问尾节点需要调用以下函数，而非直接访问变量 rear 。在队列为空时，该函数返回 None ，没有问题。

    def peek_last(self) -> int:
        """访问队尾元素"""
        return None if self.is_empty() else self.rear.val

[learntochangecode]

好的，原来是这样，谢谢解答

[ShcRes]

这种情况下，如果 rear 的指向没有改变，对于内存自动回收是否有影响

[krahets]

@ShcRes 会影响 rear 指向的节点的回收。不过在一个动态的链表中，rear 的指向也在动态变化，所以我感觉可以忽略不计

[CarberryChai]

/* 双向链表节点 */
class ListNode {
    var val: Int // 节点值
    var next: ListNode? // 后继节点引用（指针）
    weak var prev: ListNode? // 前驱节点引用（指针）

    init(val: Int) {
        self.val = val
    }
}

在Swift中为了避免循环引用，是不是加个weak比较好🥹

[nuomi1]

#666 已提交 PR，感谢提醒。

[zhuasdfg]

return (i + capacity()) % capacity();这段代码我看了好久没明白，结果看到了front = index(front - 1);是这个原因吧

[is-liu]

这段代码的作用是实现循环索引。它返回的是 i 与 capacity() 的和模 capacity() 的结果。

具体来说，i 是要计算的索引，capacity() 是容器的容量。将 i 与 capacity() 相加后对 capacity() 取模，相当于将 i 的索引值循环滚动到下一个位置。

例如，如果 i 是 0，capacity() 是 5，那么 (i + capacity()) % capacity() 的结果就是 0。如果 i 是 4，capacity() 还是 5，那么 (i + capacity()) % capacity() 的结果就是 1。这样，无论索引值在哪个位置，都可以循环滚动到下一个位置。

这种循环索引的作用通常是为了在固定大小的容器中实现索引访问，避免出现越界问题。

[xtlxblk]

i是4，capacity()是5，那么(i + capacity()) % capacity()结果不该是4吗？为什么是1？

[SummerBlue-code]

先说结论：这段代码是为了让返回的值能够在 [ 0 , capacity ) 的区间内进行循环
首先我们先理解这个函数的 i 它的取值范围是应该是[ -capacity , capacity ]
然后我们把函数拆开来看，先不看括号里面的 capacity( )。
当代码为：i % capacity( ) 时
这段代码能够让 i 的自增永远不会超出capacity的大小，值域为(-∞ , capacity )。
当 i 为负数时，实际的返回值会小于 0 不满足我们的最终目的。
所以我们将代码改为下面这样
当代码为：（ i + capacity( ) ) % capacity( ) 时
我们分类讨论
当 i 为正数时，代码可以化简为：i % capacity( )
当 i 为负数时，代码为 （ capacity( ) + i ) % capacity( ) ,
capacity( ) + i 可以表示为 capacity( ) - | i |
当 0 > i >= -capacity 时, capacity( ) - | i | 永远不会大于capacity( )
最终化简为 capacity( ) - | i | ,
最后因为 capacity > i > - capacity 所以该函数值域为 [ 0 , capacity )

此处有图文讲解：https://zhuanlan.zhihu.com/p/398066452（很通俗易懂，我就是看这个学会的）

[xtlxblk]

我明白了，如果是这个逻辑的话，之前一个回复应该是笔误将负4写成了正4引起了误解

[Dunker-tap]

原来如此啊，撤销功能用的竟然是双栈队列

[muzishuiji]

+1，之前以为是用了两个队列～

[muzishuiji]

感觉理论上【双向队列」也是可以实现撤销重做和浏览器的前进后退的能力的。

[SummerBlue-code]

// 队首出队操作
if (isFront) {
val = front.val; // 暂存头节点值
// 删除头节点
ListNode fNext = front.next;
if (fNext != null) {
fNext.prev = null;
front.next = null;
}
front = fNext; // 更新头节点
}

大佬，我想请问下这段代码能不能替换成下面这样。

// 队首出队操作
if (isFront) {
val = front.val; // 暂存头节点值
// 删除头节点
front = front.next; // 更新头节点
if (front != null) {
front.pre = null; //删除头节点前的节点
}
}

[krahets]

最好将双向的连接都断开，添加 front.prev.next = null 。

[SummerBlue-code]

好的，感谢回答

[5710xIa]

关于最后撤销的实现，那么恢复（CTRL + Y）操作是怎么实现的？

[krahets]

可以看一下“小结”的Q&A，里面有

[samabl]

if (isFront) {
    val = front->val; // 暂存头节点值
     // 删除头节点
    DoublyListNode *fNext = front->next;
    if (fNext != nullptr) {
        fNext->prev = nullptr;
        front->next = nullptr;
        delete front;
    }
    front = fNext; // 更新头节点
    // 队尾出队操作
} else {
    val = rear->val; // 暂存尾节点值
     // 删除尾节点
    DoublyListNode *rPrev = rear->prev;
    if (rPrev != nullptr) {
    rPrev->next = nullptr;
    rear->prev = nullptr;
    delete rear;
    }
    rear = rPrev; // 更新尾节点
}

关于这段代码中删除节点的部分，为什么删除节点前需要手动断开连接，而单链表删除节点前不需要手动断开，不手动断开的话会有什么影响？

[krahets]

从数据结构与算法（做题）的角度看，不断开没有关系，只要保证程序的逻辑是正确的就行。从标准库的角度看，手动断开更加安全、逻辑更加清晰。如果不手动断开，可能会影响当前节点的内存回收，因为有一个指针仍然在指向它。

[orangegei]

在双向队列的pop函数中用if (fNext != null) {
fNext.prev = null;
front.next = null;
}是为了只有一个节点的情况吧，这种情况是不是应该rear也设为null

[krahets]

可以的，设置一下可读性更好。但原文代码的正确性也没问题

[ruomu007]

判断是不是空队列，能不能用 if（queSize==0）来判断。书上都是 if (isEmpty())。 这有什么利弊吗？

[zxbdzh]

判断队列是否为空可以用 if (queSize == 0) 或是 if (isEmpty())。两种方法表面上看起来都能达到相同的目的，但它们各有优劣。

使用 if (queSize == 0) 的优点：

简单直接： 如果你已经有队列大小的信息（queSize），直接判断是否为0是非常直观和简单的。
性能： 这种方法通常只涉及到一个简单的整数比较操作，执行起来可能会略快一些。
使用 if (queSize == 0) 的缺点：

易读性： queSize == 0 可能不如 isEmpty() 直观，后者明确表达了意图——检查队列是否为空。
封装性： 如果你直接访问队列大小变量，会暴露队列的内部实现细节，不符合面向对象编程的封装原则。
维护性： 如果队列的实现发生变化，例如queSize的计算方式改变，所有使用queSize == 0判断的地方都需要修改。
同步问题： 如果队列为多线程环境设计，直接访问 queSize 可能会导致线程安全问题，而调用isEmpty() 则可以在内部处理同步。
使用 if (isEmpty()) 的优点：

易读性： isEmpty() 方法名明确表达了其用途，代码更加直观和可读。
封装性： 使用 isEmpty() 能隐藏队列内部实现细节，符合封装原则，使队列类的实现和接口分离。
维护性： 如果队列的实现发生变化，只需修改 isEmpty() 方法，不需要修改所有判断队列是否为空的地方。
同步问题： 能在 isEmpty() 方法内部处理同步问题，确保线程安全。
使用 if (isEmpty()) 的缺点：

可能略微复杂： 需要调用一个方法，可能涉及额外的函数调用开销，不过通常开销很小，可以忽略不计。
总的来说，推荐使用 isEmpty() 方法来判断队列是否为空，因为它在代码可读性、封装性和维护性方面具有更明显的优势，特别是在面对复杂系统或未来可能变化的实现时。

[ruomu007]

真棒！谢谢大佬。

[krahets]

简单来说，isEmpty() 是我们定义的方法，它会处理好我们想要的一切，因此我们倾向于用它。

在这里，queSize == 0 也足够直接，不影响可读性。但是在比较复杂的逻辑下，两种选择的差距就会被体现出来

[ayu255]

双向队列只要维护好一个头结点一个尾节点，就不是一定要用双向链表实现。

[ayu255]

说错了，hhh

[nfrjyrymccan]

环形数组真的太秒啦!!!

[ruomu007]

有个问题：刚开始是空队列，然后入队1个元素，入队的时候c++代码只对front进行了维护，但是正因为只入队了一个元素，该元素即是队首也是队尾，是不是也应该对 rear 进行维护。

[ruomu007]

增加提问：正因为是环形数组，双向都可以出队入队，出队入队操作后，如果全部出队，变成空队列后，front 和rear是不一定 指向0索引的。

[hpstory]

Hi @ruomu007 , 1. rear可以通过front和队列长度计算出来，不需要单独维护。2. 是的，不一定会在0

[HP-Patience]

有个问题：

1.来源：
基于双向链表的实现中，出队操作中的 队首出队 代码部分:
if fnext != None:
fnext.prev = None
self._front.next = None
self._front = fnext # 更新头节点

其中的self._front.next = None代码语句

2.问题：
这段代码是不需要的操作

3.原因：
下面更新头节点时会把这个节点删去，所以不需要在前面把该节点的next指向None

以上是个人见解，如果哪里错了还请诸位解答解答🙂

[Asce-ops]

我理解这么做是为了使得原先的头节点不再和链表有任何关联，便于内存回收

[HP-Patience]

第二个问题：

def index(self, i: int) -> int:
    """计算环形数组索引"""
    # 通过取余操作实现数组首尾相连
    # 当 i 越过数组尾部后，回到头部
    # 当 i 越过数组头部后，回到尾部
    return (i + self.capacity()) % self.capacity()

此处 return (i + self.capacity()) % self.capacity()

i + self.capacity()是多余的，为什么要加上呢？

[HP-Patience]

哦哦，明白了！
原因是self._front - 1可能是负数。
比如在队首入队时，self._front = 0，self._front - 1=-1，这时候指的其实是数组的最后一个元素

[niaidaye]

图 5-9 基于数组实现双向队列的入队出队操作，Step 2：push_last 有点小小的失误，应该没有尾指针rear，而就是数组的size嘞？我看你代码里实现，也是，直接用size，从队尾出队的。

[krahets]

rear 是由 front 和 size 计算得来的（Step1 展示了，Step2 省略了这个过程）：

        # 计算队尾指针，指向队尾索引 + 1
        rear = self.index(self._front + self._size)

[lovebuizel]

5.3.1 双向队列常用操作的JS和TS的isEmpty有問題，因為size賦的值是數字(屬於primitive values)，所以不會因為之後deque.length變更而跟著更新
/* 获取双向队列的长度 */
const size = deque.length;

/* 判断双向队列是否为空 */
const isEmpty = size === 0;

應該改成
const isEmpty = deque.length === 0;

[justin-tse]

Hi @lovebuizel, 这里isEmpty是没问题的，其实你给出的修改建议和原来的代码是等价的，只是把两行合为一行。
我们这里isEmpty只是开了一个有意义的变量名来存储一个结果判断，并不是一个方法调用。

[wchwawa]

另一个可以resize的arraydeque，大家参考

[wchwawa]

import java.util.*;
import java.lang.Math;

public class ArrayDeque61B implements Deque61B {
private T[] items;
private int size;
private int itemLength;
private int nextFirst;
private int nextLast;

public ArrayDeque61B(){
    items = (T[]) new Object[8];
    size = 0;
    itemLength = items.length;
    this.nextFirst = items.length - 1;
    this.nextLast = 0;

}

@Override
public void addFirst(T x) {
    if (size == itemLength){
        resize(2);
    }
    size ++;
    items[nextFirst] = x;
    nextFirst = Math.floorMod(nextFirst - 1, itemLength);

}

@Override
public void addLast(T x) {
    if (size == itemLength){
        resize(2);
    }
    size++;
    items[nextLast] = x;
    nextLast = Math.floorMod(nextLast + 1, itemLength);
}

@Override
public List<T> toList() {
    List<T> l = new ArrayList<>();

    for (int i = 0; i < items.length; i ++){
        if (items[i] == null){
            continue;
        }else {
            l.add(items[i]);
        }
    }
    return l;
}

@Override
public boolean isEmpty() {
    if (size == 0){
        return true;
    }else {
        return false;
    }
}

@Override
public int size() {
    return size;
}

@Override
public T removeFirst() {
    if (size == 0){
        return null;
    }
    if (size < 0.25 * itemLength){
        resize(0.50);
    }
    size --;
    T removedItem = items[nextFirst + 1];
    items[nextFirst + 1] = null;
    nextFirst = Math.floorMod(nextFirst + 1, itemLength);
    return removedItem;
}

@Override
public T removeLast() {
    if (size == 0){
        return null;
    }
    if (size < 0.25 * itemLength){
        resize(0.50);
    }

    size --;
    T removedItem = items[nextLast - 1];
    items[nextLast - 1] = null;
    nextLast = Math.floorMod(nextLast - 1, itemLength);
    return removedItem;
}

@Override
public T get(int index) {
    if (index < itemLength && index >= 0){
        return items[index];
    }
    return null;
}

@Override
public T getRecursive(int index) {
    return null;
}

public void resize(double factor){
    double cal = itemLength * factor;
    int newLength = (int)cal;
    T[] newItem = (T[]) new Object[newLength];

    for (int i = 0; i < nextLast; i++) {
        newItem[i] = items[i];
    }
    int totalFirstItemCount = itemLength - 1 - nextFirst;
    int newItemLength = newItem.length;
    for (int j = itemLength - 1; j > nextFirst; j --){
        newItem[newItemLength - 1] = items[j];
        newItemLength --;
    }
    items = newItem;
    itemLength = items.length;
    nextFirst = itemLength - totalFirstItemCount - 1;
}

}

[krahets]

没有resize

resize() 不是本节的重点内容，这个概念已经在“列表”中讲解。

也没有常数时间的get

1. 文中的 peekFirst() 和 peekLast() 的时间复杂度是 O(1) ，用于获取队首和队尾元素。
2. 标准的双向队列一般不提供 get() 随机访问方法，例如 Java 的 ArrayDeque。

没有用到array的特性

没有用到什么特性？

[wchwawa]

明白了，抱歉，我之前没有仔细看，已经删除并修正原来的评论。

[Kore-yoshi]

python中 return (i + self.capacity()) % self.capacity()这里和这个return i % self.capacity()是一样的效果的吧，没太理解为什么要加上一个capacity
def test_mod(i, capacity):
result1 = i % capacity
result2 = (i + capacity) % capacity
return result1, result2

示例测试

capacity = 5
test_cases = [3, -2, 10, -7]

results = [test_mod(i, capacity) for i in test_cases]
for i, (result1, result2) in zip(test_cases, results):
print(f"i: {i}, i % capacity: {result1}, (i + capacity) % capacity: {result2}")
输出：
i: 3, i % capacity: 3, (i + capacity) % capacity: 3
i: -2, i % capacity: 3, (i + capacity) % capacity: 3
i: 10, i % capacity: 0, (i + capacity) % capacity: 0
i: -7, i % capacity: 3, (i + capacity) % capacity: 3

[Teslajia]

队列不停地进出，会导致第一个索引不断往后，为了重复利用前面的位置（已出队列的，空出来的数据），+队列长度，可以实现这一效果

[921000]

public class LinkDeque {

private Node head;

private Node tail;

private int size;

public class Node {

    private int data;

    private Node prev;

    private Node next;

    public Node(int data) {
        this.data = data;
    }

}

public LinkDeque() {
    this.head = null;
    this.size = 0;
}

private boolean isEmpty() {
    return this.size == 0;
}

public void addFirst(int data) {
    Node node = new Node(data);

    if(head == null) {
        head = node;
        tail = node;
    } else {
        head.prev = node;
        node.next = head;
        head = node;
    }

    size++;
}

public void addLast(int data) {
    Node node = new Node(data);
    if (tail == null) {
        tail = node;
        head = node;
    } else {
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    size ++;
}

public int removeFirst() {
    if (head == null) {
        return -1;
    }
    int data = head.data;
    if (head == tail) {
        head = null;
        tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }
    size--;
    return data;
}

public int removeLast() {
    if (tail == null) {
        return -1;
    }
    int data = tail.data;
    if (head == tail) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
    size--;
    return data;
}

public int peekFirst() {
    if (head == null) {
        return -1;
    }
    return head.data;
}

public int peekLast() {
    if (tail == null) {
        return -1;
    }
    return tail.data;
}

}
链表实现 双端队列

[921000]

public class ArrayDeque {

private int[] array;

private int front;

private int rear;

private int size;

private int capacity;

public ArrayDeque() {
    this.capacity = capacity;
    this.array = new int[capacity];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
}


public boolean isEmpty() {
    return size == 0;
}

public boolean isFull() {
    return size == capacity;
}

public void addFirst(int data) {
    if (isFull()) {
        return;
    }
    array[front] = data;
    front = (front + 1) % capacity;
    size++;
}

public void addLast(int data) {
    if (isFull()) {
        return;
    }
    rear = (rear - 1 + capacity) % capacity;
    array[rear] = data;
    size++;
}

public int pollFirst() {
    if (isEmpty()) {
        return -1;
    }
    front = (front - 1 + capacity) % capacity;
    size--;
    return array[front];
}

public int pollLast() {
    if (isEmpty()) {
        return -1;
    }
    int data = array[rear];
    rear = (rear + 1) % capacity;
    size--;
    return data;
}

public int peekFirst() {
    if (isEmpty()) {
        return -1;
    }
    return array[(front - 1 + capacity) % capacity];
}

public int peekLast() {
    if (isEmpty()) {
        return -1;
    }
    return array[rear];
}

public int size() {
    return size;
}

数组实现双端队列

[YangyuChenXS]

基于链表的双向队列的Python实现中，关于pop方法有疑问：
1.删除头节点的时候，如果只有节点，是不是也得更新尾节点：
if self._front is None:
self._rear = None
2. 删除尾节点也同理

[Gxxx-x]

我的 理解是可以但是没必要，因为在不修改的情况下也不影响其他操作，_rear的值并不重要，我们不能从空队列中获取任何值（个人理解）

[YangyuChenXS]

感谢，我理解了。
核心应该是这段代码的其它操作的方法，如push(), peek_first()方法的内部逻辑都有关于队列是否为空的检查，所以是否有“self._rear = None” 都不影响

[FrierenGreatDemonLord]

也可通过传递具体的操作函数实现push 和pop 的通用，如：

C 的指针函数

void _push(Deque* q, int val, void(*fPush)(Deque*, ListNode*));
void _pushFirst(Deque* q, ListNode* node);
void _pushLast(Deque* q, ListNode* node);

void pushFirst(Deque* q, int val) {
	_push(q, val, _pushFirst);
}
void pushLast(Deque* q, int val) {
	_push(q, val, _pushLast);
}

Python 的可调用对象

def _push(self, val: int, f_push: Callable[['Deque', ListNode], None])
	pass

def push_first(self, val):
	def _push_first(q: 'Deque', node: ListNode):
		pass
	self._push(val, _push_first)

def push_last(self, val):
	def _push_last(q: 'Deque', node: ListNode):
		pass
	self._push(val, _push_last)

[FrierenGreatDemonLord]

补充一点：C 中可以通过给函数加上关键字static，使其具有内部链接——通过include 导包后，无法被访问。
如（如此一来使用者仅需调用pushFirst() 或pushLast() 即可，无需关注也无法访问到具体的内部实现）：

void static _push(Deque* q, int val, void(*fPush)(Deque*, ListNode*));
void staitc _pushFirst(Deque* q, ListNode* node);
void static _pushLast(Deque* q, ListNode* node);

[FrierenGreatDemonLord]

to_list(self) -> list[int] 也可使用列表解析式实现

def to_list(self) -> list[int]:
    return [self.nums[self.index(self.front + i)] for i in range(self.size)]