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]

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

[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，这时候指的其实是数组的最后一个元素

[skyswordw]

Python的取模运算 % 总是返回非负数
数学上，对于任意整数n和正整数m，(n + m) % m 等于 n % m
所以在这个python实现中加上 capacity 确实是多余的。其他编程语言（如C/C++）的实现负数取模的结果可能是负数。

[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)]

[subdoctor]

def peek_first(self) -> int:
"""访问队首元素"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._nums[self._front]
此时的self._front是多少呢？

[subdoctor]

def peek_first(self) -> int:
"""访问队首元素"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._nums[self._front]

def peek_last(self) -> int:
    """访问队尾元素"""
    if self.is_empty():
        raise IndexError("双向队列为空")
    # 计算尾元素索引
    last = self.index(self._front + self._size - 1)
    return self._nums[last]

这个不对吧，队列不是先入先出吗，这个好像是先入后出的？

[HarrryHe]

这个是peek不是pop，即访问队首和队尾的元素 第一个peek first就是访问队首的元素，而peek last则是访问队尾的元素