chapter_stack_and_queue/queue/

[giscus[bot]]

chapter_stack_and_queue/queue/

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

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

[JackCmd233]

针对Java的Queue类补充一些知识点：

	抛出异常	返回特殊值
插入	add(e)	offer(e)
删除	remove()	poll()
查看队头元素	element()	peek()

队列除了基本的 Collection 操作外，还提供特有的插入、提取和检查操作(如上)。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。
除非有容量限制，否则在大多数实现中，插入操作不会失败。

[krahets]

顶

[cylovecode]

基于数组的实现，入队后将将输入元素赋值给 rear 索引处，感觉后面少了一句rear+1

[krahets]

不需要哈，rear 应该指向的就是尾元素

[zdxkaixin]

循环数组 -🐂的

[64yuer]

pop = que.popleft() 这里python的实现应该是pop = que.pop(0)，3.9.0版本无popleft用法，pooleft是用于collections中的deque对象

[64yuer]

抱歉，没看注释，没问题写的

[MackieLin]

队列一章中，包括双向队列，有些地方入队用 push , 有些地方入队用 offer，建议统一一下使文章更严谨。比如统一使用 Java 中的用词 offer

[krahets]

谢谢建议，已统一为 push()

[FFFPrime]

class typing.Deque 3.9 版后已移除，这个类型注解会导致程序报错

import typing
import collections
que: Deque[int] = collections.deque()
-------------------------------------------------
NameError: name 'Deque' is not defined

[krahets]

谢谢！本来采用的是 typing 标准，与 LeetCode 统一。已在 439 中更新为 PEP 585 标准，请拉取最新代码运行测试～

[zhuasdfg]

打卡，手敲了一遍链表和循环数组实现队列，不过我好像只能跟着敲。

[krahets]

第一遍跟着敲，后面慢慢就能自己写了～

[fiona-liu12]

基于链表实现的队列进行入队操作，如果队列不为空，则将该节点添加到尾节点后中的else语句里这两句不理解 rear.next = node; rear = node;，不应该只用rear.next = node;就行了嘛

[krahets]

添加节点后，尾节点就是 node 了。因此我们需要将 rear 指向这个新的尾节点 node

[kiii0927]

rear.next = node; rear = node; 它们不是同时都指向新的尾结点了嘛。不应该是把下一个next指向新的尾结点node就可以吗

[bodaq99]

不知道是不是队尾rear和它的next都是node，然后node又是rear，所以node的next又是node，从而形成闭环，不知道这样理解对不对

[bodaq99]

噢我这个理解错了

[stySunshine]

问题：执行到 rear.next = node;（1处）这里后，当此时push的是2的时候，real.next.val = 2这个很好理解，为什么front.next.val = 2 也会赋值呢？在push的时候，又没有写front.next = node; 这里我不太理解~
/* 初始化队列 */
LinkedListQueue queue = new LinkedListQueue();

    /* 元素入队 */
    queue.push(1);
    queue.push(3);
    queue.push(2);
    queue.push(5);
    queue.push(4);
    System.out.println("队列 queue = " + Arrays.toString(queue.toArray()));

/* 入队 */
public void push(int num) {
// 尾节点后添加 num
ListNode node = new ListNode(num);
// 如果队列为空，则令头、尾节点都指向该节点
if (front == null) {
front = node;
rear = node;
// 如果队列不为空，则将该节点添加到尾节点后
} else {
rear.next = node; // 1处
rear = node;
}
queSize++;
}

[palp1tate]

用数组实现队列的三张演示图中的第二张，也就是push操作，并没有提及rear自增1的操作：

三个步骤应该是：

1. 将元素添加至rear处
2. 将rear自增1
3. 将queSize自增1

[krahets]

请看一下代码，rear 是用 font 和 queSize 计算的，图中的步骤没问题

[palp1tate]

get it，thanks

[l0190]

问题:环形数组队列的有效长度不应该是Maxsize=len(self.__nums)-1
python代码中的if self.__size == self.capacity()是不是不能作为队列已满的条件。应该改成if (self.__size+1) == self.capacity()

[krahets]

环形数组队列最大长度为 n - 1 、保留一个空位的原因是为了区分队列为空 or 满。文中的实现利用了一个 size 变量来记录数组长度，因此无需保留这个空位了

[yasaorder]

res = [0] * self.size()这种初始化队列的方式，会导致res 的每个元素引用相同的地址吗，就是如果我改动res[0]=1，那么res[1]、res[2]、...会不会因为存放的是相同的地址，导致都变为1

[krahets]

不会，但二维数组就不行了，例如 res = [[0] * self.size()] ，这样相当于多次引用了同一个一维列表 [0] 。

[ChinaYong]

在5.2.2的第1节基于链表的实现，C语言代码的打印队列函数中，for循环语句条件queue->front != queue->rear是用来检测队列是否为空吗？但是如果队列中只有一个元素，好像就会打印不出那个单独的元素

[Gonglja]

感谢指正，已修复

[pureliumy]

环形数组队列扩容

    /* 入队 */
    push(num) {
        if (this.size === this.capacity) {
            this.extendCapacity();
        }

        // ...
    }

    /* 扩容 */
    extendCapacity() {
      const extraSize = Math.round(this.capacity * 0.5);
      const arr = new Array(extraSize);

      this.#nums = this.toArray().concat(...arr);
      this.#front = 0;
      this.capacity += extraSize;
    }

[BIGcarter]

c++链表实现的队列，入队push()那里我有两个疑问：
（1）当链表为空时，front=node; rear = node; rear 不应该指向front吗？
（2）当链表不为空时，rear->next = node; read=node; 为什么不是node->next = rear; rear = node;
新节点指向原来的rear节点, 然后node成为新的rear节点？
感觉我还是对链表不甚了解..

[krahets]

emmm 感觉你需要重新看一下链表章节

[CitySunRise]

/* 出队 */
void pop(linkedListQueue *queue) {
int num = peek(queue);
ListNode *tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
queue->queSize--;
}
这段代码中的 num 是为了记录出队元素吧 但是没看到相关的用处 原文中没有把它return出去

[krahets]

这里当时是为了和 C++ 内置队列的 pop() 操作行为对齐，是不 return 的。不过为了多语言一致性，我准备添加 return 了。

[ZLL6]

C语言：
如果没看错的话应该存在两个结构体，ListNode和LinkedListQueue;那么能否写出ListNode的定义呢，因为看到一处
/* 入队 */
void push(LinkedListQueue *queue, int num) {
// 尾节点处添加 node
ListNode *node = newListNode(num);
// 如果队列为空，则令头、尾节点都指向该节点
if (queue->front == NULL) {
queue->front = node;
queue->rear = node;
}
// 如果队列不为空，则将该节点添加到尾节点后
else {
queue->rear->next = node; /**************************************************/
queue->rear = node;
}
queue->queSize++;
}
这里的queue->rear->next = node;从这里可以看到是queue->rear里面也是有一个next指针存在的，那么感觉有点混乱，LinkedListQueue的定义内部的指针类型是否应该是LinkedListQueue，而不是ListNode呢

[krahets]

ListNode 在 codes/c/utils/list_node.h 中定义。建议前往代码仓下载源代码并运行～

[mobiusy]

取余操作这样写是不是好理解
push操作需要向尾部添加1个元素，所以尾部加1，得到的结果对队列长度取余

// 通过取余操作，实现 rear 越过数组尾部后回到头部
const rear = (this.rear + 1) % this.capacity;

[krahets]

可以的，不过要先用 front 和 queSize 计算出 rear

[yusui-shun]

c语言中对于链表队列的出队pop实现：
void pop(LinkedListQueue *queue) {
int num = peek(queue);
ListNode *tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
queue->queSize--;
}是不是应该把这个num使用起来，void改为int并return num，这个出队再在开头加入一个判空操作是不是更好

[krahets]

Hi，在 C++ 中，内置栈、队列的 pop() 方法不返回元素。为了保持一致，特意将 C 和 C++ 的 pop() 函数设计为 void 类型。因此代码中会有一个未使用的 num ，这个其实是其他编程语言中会返回的那个值。
为避免歧义，已经将所有 pop() 的返回值统一为 int 类型。

[bnufw]

这个_front感觉没必要有

[bnufw]

用0代替front，感觉是一样的

[krahets]

在弹出元素时，_front 是会移动的，并非恒为 0

[bnufw]

谢谢

[Terran0629]

作者你好，有没有别的可视化工具呀，我想从图上看一下“环形数组”队列超出范围后是什么样的

[krahets]

Hi，暂时没有噢，你可以多添加一些“入队”和“出队”的操作，直至超出队列长度范围，就可以观察到啦

[Terran0629]

好的 谢谢大佬

[qw124341789]

5.2.2的C语言的代码里少了前面一部分的结构体：
typedef struct ListNode{
int data;
ListNode *next;
}ListNode;

[krahets]

Hi，请前往仓库 https://github.com/krahets/hello-algo 下载完整代码，并在本地运行

[shinehhht]

for (int i = 0; i < queue->queSize && queue->front != NULL; i++) 中i < queue->queSize && queue->front != NULL不应该是等价条件吗？应该留一个就行吧？

[Gonglja]

是的，二者是等价的，可以移除冗余的条件
已更新：main...Gonglja:hello-algo:main

[Gerhart1998]

K神，我自己手敲了一个循环数组队列的读写，为啥read不到write的第一个值呢？期待您回复

#define QUEUE_SIZE 1
#define ARRAY_SIZE (QUEUE_SIZE + 1)
int main(void)
{
    int i = 0;
    STACK_TYPE ret;
    for(i = 0; i < 500000; i++)
    {
        write(i);
        ret= read();
    }
    return 0;
}

#if Stack_of_Buffer 

static STACK_TYPE queue[ARRAY_SIZE];
static int front = 1;
static int rear = 0;

void write(STACK_TYPE value)
{
    assert(!is_full());
    rear = (rear + 1) % ARRAY_SIZE;
    queue[rear] = value;
}

STACK_TYPE read(void)
{
    assert(!is_empty());
    STACK_TYPE ret = queue[front];
    front = (front + 1) % ARRAY_SIZE;
    return ret;
}

int is_full(void)
{
    return (rear + 2) % ARRAY_SIZE == front;
}

int is_empty(void)
{
    return (rear + 1) % ARRAY_SIZE == front;
}

#endif

[KLYkl]

你好，你的front是从1开始的，而read（）里这个STACK_TYPE ret = queue[front];就是从queue[1]开始就是读的吧？

[KLYkl]

好像是我理解错了，hh，不太懂

[Gipsyfine]

在queue.py中：
访问队首元素
front: int = que[0];

这里多了个分号🧐

[krahets]

谢谢指正！

[MingyuW488]

为什么pop不用判断队列是否为空呢

[esmmmmme]

我觉得是因为 pop里面 有 self.peek(). peek 里面有判断吧

[lys849]

perfect!

[wubaozhen]

作者你好，

class LinkedListQueue:
    """基于链表实现的队列"""

    def __init__(self):
        """构造方法"""
        self._front: ListNode | None = None  # 头节点 front   
        self._rear: ListNode | None = None  # 尾节点 rear
        self._size: int = 0

请问上面代码的self._front: ListNode | None = None 这个代码怎么理解啊，ListNode是个什么类型，为什么在下面的push(num)方法中可以调用ListNode(num)？

[hpstory]

Hi @wubaozhen , 这个是自定义的类型，代码在这里 list_node.py

[syd168]

ListNode 是作者定义的类，这里没显示

self._front: ListNode | None = None 表示self._front可以是ListNode或者是None类型，默认值是None
: ListNode | None 是python的类型注释。
在 Python 中，变量可以不声明类型，但类型注解可以提高代码的可读性，这里用 = None 来表示 _front 初始时是空的。

[Laypeople]

请问js链表队列删除头节点后，什么时候会将头节点的内存释放掉？这里我理解只是改变类中#front的引用，而之前的头节点并未释放。

    pop() {
        const num = this.peek();
        // 删除头节点
        this.#front = this.#front.next;
        this.#queSize--;
        return num;
    }

[Vaeeeee-WJ]

太精妙了，算法的魅力！

[1127924631]

基于数组实现队列的C代码中第五行定义queSize的注释是不是错了？queSize应该是队列长度而不是尾指针吧？