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 是的，可以把它理解为注释，增强可读性的，实际上无法限制变量的类型

[ly3638]

为啥你现在不回复问题了，你书上说你会回复的我发了21天了没见你回复

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

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

[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则是访问队尾的元素

[wqk756633]

def pop(self, is_front: bool) -> int:
if is_empty():
raise IndexError("双向队列为空")
elif is_front:
node = self._front
self._front = node.next
else:
node = self._rear
self._rear = node.prev

双向队列基于链表实现的出队操作：为什么要暂存头节点和尾节点？不理解求大神指点（我上面写的对吗？）

[Liucc-123]

咦，你这里是问的为什么存放头节点值或尾节点值吧？这个值要暂存起来，方便在最后进行返回。
然后你代码里遗漏的点包括有：
1、没有返回被删除节点的值
2、节点移除后，没有维护头节点或尾节点的指针关系（如：头节点的 prev = None）

[jiuerya7]

你这样写，原来的头节点和新的头节点之间的双向指针关系还存在，如果你多出队几次，会发现头节点/尾节点依然牵着一堆节点😁

[UblezUnunsIOII]

Ab by Sent from Yahoo Mail for iPhone On Friday, January 24, 2025, 8:20 AM, wqk756633 ***@***.***> wrote: def pop(self, is_front: bool) -> int: if is_empty(): raise IndexError("双向队列为空") elif is_front: node = self._front self._front = node.next else: node = self._rear self._rear = node.prev 双向队列基于链表实现的出队操作：为什么要暂存头节点和尾节点？不理解求大神指点（我上面写的对吗？） — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[batreeon]

因为pop函数最终需要返回队首值或队尾值

[superZchen0701]

不管是队列还是双向队列，使用链表/双向链表实现的方案都看起来更直观更佳。

[TwentyInAQuiver]

可能和思维习惯有关吧，python明显是用环形数组更简明易懂也更方便。

[2450635073]

我要觉得链表好理解一点，python接触指针比较少，循环数组的指针给我绕的脑子疼

[Limit1996]

常用C++、C的链表很好理解
常用Java、C#的环形数组更好理解
区别就是对于指针的理解程度不同

[xiaozhuge123]

day04

[WangYun0918]

https://www.hello-algo.com/chapter_stack_and_queue/deque.assets/linkedlist_deque_step4_pop_last.png
Step 1：示例上面是队首，下面队尾，为何 Step 4 删除上面的节点1 变成了队尾出队操作？不解

[WangYun0918]

理解了，是把队尾4删除了

[wanglei952]

class LinkedListDeque {
private front: ListNode;
private rear: ListNode;
private queSize: number;

constructor() {
    this.front = null;     这个地方不会报错吗? private front: ListNode;没有包含null类型啊
    this.rear = null;
    this.queSize = 0;
}

[wanglei952]

peekLast(): number {
return this.queSize === 0 ? null : this.rear.val;
}这个地方也不对，空值管理的很混乱

[changzhihang]

return (i + self.capacity()) % self.capacity()
先加上 self.capacity 再取模感觉在 Python 里面好像没必要，Python 会把余数限制在 0 <= 余数 <= 除数 的范围内，负数也是这样。在 C 里面才需要这一步。

[changzhihang]

经过测试，
Python: -1 % 5 = 4
C: -1 % 5 = -1
C: -8 % 5 = -3
不同语言在这个地方规则不一样，似乎 C 的是把余数限制在 -除数 < 余数 < 除数 的范围内了

[ly3638]

第一次见你这种的，是对的吗

[2450635073]

大多数语言都是不支持负数除正数取余为正，但是python例外，这么写可能因为比较严谨，方便阅读和用其他语言编写教程统一写法

[ly3638]

为什么队尾不是指向元素呢而是指向空的数组呢