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;就行了嘛

[kiii0927]

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

[bodaq99]

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

[bodaq99]

噢我这个理解错了

[ZZY080]

属于尾插法需要不断更新尾
节点

[ZZY080]

rear.next = node; rear = node; 意思是 当前尾节点的下一个节点是node ； 然后把尾节点更改为node

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

[sunshinesDL]

K 大这里的例子有些小问题，对于 res = [[0] * self.size()]，实际相当于多次引用了同一个整型对象 0，当修改内层列表的某个元素时，由于整数类型不可变，解释器会创建新的整型对象并让被修改的列表元素指向新对象，因此内层列表其他元素的值不会改变。演示代码如下：

In [109]: res = [[0] * 3]
In [110]: res
Out[110]: [[0, 0, 0]]

In [111]: res[0][1] = 1
In [112]: res
Out[112]: [[0, 1, 0]]

然而，对于 res = [[0]] * self.size()，则相当于多次引用列表对象 [0]，当修改某个内层列表时，由于列表类型可变，解释器会原地修改该列表，使得引用该列表对象的所有内层列表一同更新。演示代码如下：

In [117]: res1 = [[0]] * 3
In [118]: res1
Out[118]: [[0], [0], [0]]

In [119]: res1[0][0] = 2
In [120]: res1
Out[120]: [[2], [2], [2]]

[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 了。

[Limit1996]

对指针不熟理解链表实现的队列还是有点难度。。。

/// <summary>
/// 数组队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class CustomArrayQueue<T>
{
    private readonly T[] _array = new T[10];
    private int _count = 0;
    private int _headIndex = 0;
    private int TailIndex => _headIndex + _count;
    public int Capacity => _array.Length;
    public int Count => _count;

    public void Enqueue(T value)
    {
        if (_count == _array.Length)
            throw new InvalidOperationException("队列已满");
        _array[TailIndex % Capacity] = value;
        _count++;
    }

    public T Dequeue()
    {
        var res = Peek();
        _array[_headIndex % Capacity] = default!;
        _headIndex++;
        _count--;
        return res;
    }

    public T Peek()
    {
        if (_count == 0)
            throw new InvalidOperationException("队列为空");
        return _array[_headIndex % Capacity];
    } 
}

[llsedu]

使用C语言中的void* 模拟其他语言中的泛型实现队列，确保队列的通用性。

#include "ListNode.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LISTNODE_GENERIC
#ifdef LISTNODE_GENERIC

ListNode *newListNode(void *value,size_t size){
    ListNode *node = malloc(sizeof(ListNode));
    if(!node){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    node->value = malloc(size);
    if(!node->value){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    memcpy(node->value,value,size);
    node->elementSize = size;
    node->next = NULL;
    return node;

}


ListNode *addListNode(ListNode *head, void *value, size_t size){
    ListNode *newNode =  newListNode(value,size);
    newNode->next = head;
    return newNode;
    
}

ListNode *delListNode(ListNode *head, void *value,size_t size){
    ListNode *previous =NULL;
    ListNode *current = head;
    while(current !=NULL &&current->elementSize ==size&&memcmp(current->value,value,size)){
        previous = current;
        current = current->next;
    }

    if(current ==NULL){
        printf("未找到相关值");
        return head;
    }

    if(previous ==NULL){
        head = current->next;
    }
    else{
        previous->next = current->next;
    }
    free(current->value);
    free(current);
    return head;

}


ListNode * delListNodeByIndex(ListNode *head, int index){
    if(!head || index<0){
        printf("Invalid index\n");
        return head;
    }
    ListNode *pre  = NULL;
    ListNode *cur = head;
    int currentIndex = 0;
    while(!cur && currentIndex<index){
        pre=cur;
        cur=cur->next;
        currentIndex++;
    }
    if(!cur){
        printf("Index out of bounds\n");
        return head;
    }
    if(pre ==NULL){
        head = cur->next;
    }
    else{
        pre->next = cur->next;
    }

    free(cur->value);
    free(cur);
    return head;
}

void printListNode(ListNode *head, void (*printFunc)(void *)){
    if(!head){
        printf("List is empty\n");
        return;
    }
    ListNode *cur = head;
    while(cur){
        printFunc(cur->value);
        cur=cur->next;
    }
    printf("\n");

}

void freeListNode(ListNode *head){
    ListNode *cur = head;
    ListNode *next=NULL;

    while(cur){
        ListNode *next= cur->next;
        free(cur->value);
        free(cur);
        cur=next;
    }


}

#endif

#ifdef TEST_LISTNODE_GENERIC
void printInt(void *value) {
    printf("%d -> ", *(int *)value);
}

int main() {
    ListNode *head = NULL;
    
    // 添加节点到链表
    int value1 = 10, value2 = 20, value3 = 30;
    head = addListNode(head, &value1, sizeof(int));
    head = addListNode(head, &value2, sizeof(int));
    head = addListNode(head, &value3, sizeof(int));
    
    // 打印链表
    printf("原始链表: ");
    printListNode(head, printInt);
    
    // 删除值为20的节点
    int valueToDelete = 20;
    ListNode *node = delListNode(head, &valueToDelete, sizeof(int));

    
    // 打印删除后的链表
    printf("删除后的链表: ");
    printListNode(head, printInt);
    
    // 释放链表
    freeListNode(head);
    
    return 0;
}

#endif
#ifdef LISTNODE_INT

ListNode *newListNode(int value){
    ListNode *node =  malloc(sizeof(ListNode));
    if(!node){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}


ListNode *addListNode(ListNode *head, int value){
    ListNode *newNode  = malloc(sizeof(ListNode));
    if(!newNode){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->value = value;
    newNode->next = head;
    head = newNode;
    return head;
}


ListNode *delListNode(ListNode *head,int value){

    ListNode *previous = NULL;
    ListNode *current = head;

    while(current!=NULL  && current->value!=value){
        previous = head;
        current=current->next;
    }

    if (current==NULL){
        printf("未找到相关值");
        return head;
    }
    if(previous==NULL){
        head = current->next;
    }
    else{
        previous->next = current->next;
    }

    free(current);
    return head;
}

void freeListNode(ListNode *head){
    ListNode *temp;
    while(head){
        temp=head;
        head =  head->next;
        free(temp);
    }

    free(head);
}
#endif

队列实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include "ListNode.h"

typedef struct LinkedListQueue{
    ListNode *head;
    ListNode *tail;
    int queueSize;
    
} LinkedListQueue;


LinkedListQueue* newLinkedListQueue(){
    LinkedListQueue *queue = malloc(sizeof(LinkedListQueue));
    if(!queue){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    queue->head = NULL;
    queue->tail = NULL;
    queue->queueSize = 0;
    return queue;
}

void delLinkedListQueue(LinkedListQueue *queue){
    ListNode * temp = queue->head;
    while(temp){
        ListNode *next = temp->next;
        free(temp);
        temp = next;
    }
    free(queue);
}



int size(LinkedListQueue *queue){
    return queue->queueSize;
}

bool isEmpty(LinkedListQueue *queue){
    return queue->queueSize == 0;

}

LinkedListQueue* enqueue(LinkedListQueue *queue, void *value,size_t elementSize){
    ListNode *node = newListNode(value,elementSize);
    if(queue->head==NULL){
        queue->head=queue->tail=node;
    }else{
        queue->tail->next=node;
        queue->tail=node;
    }
    queue->queueSize++;
    return queue;
}


void* peek(LinkedListQueue *queue){
    if(isEmpty(queue)){
        printf("Queue is empty\n");
        return NULL;
    }
    return queue->head->value;
}

void* deqeueu(LinkedListQueue *queue,size_t elementSize){
    if(isEmpty(queue)){
        printf("Queue is empty\n");
        return NULL;
    }
    void* temp=peek(queue);
    ListNode *tempNode = queue->head;
    queue->head=queue->head->next;
    free(tempNode);
    queue->queueSize--;
    
    return temp;
}

void printLinkedListQueue(LinkedListQueue* queue, void (*printFunc)(void*)){
    if(isEmpty(queue)){
        printf("Queue is empty\n");
        return;
    }
    ListNode *temp = queue->head;
    while(temp){
        printFunc(temp->value);
        temp = temp->next;
    }
    printf("\n");
}

#define TEST_LINKEDLISTQUEUE
#ifdef TEST_LINKEDLISTQUEUE

void printIntQueue(void *value){
    printf("%d->",*(int*)value);
}


int main(){
    LinkedListQueue *queue = newLinkedListQueue();
    int a=1,b=3,c=5,d=7,e=9;
    enqueue(queue,&a,sizeof(int));
    enqueue(queue,&b,sizeof(int));
    enqueue(queue,&c,sizeof(int));
    enqueue(queue,&d,sizeof(int));
    enqueue(queue,&e,sizeof(int));
    printLinkedListQueue(queue,printIntQueue);
    printf("Queue size: %d\n",size(queue));
    printf("Queue is empty: %d\n",isEmpty(queue));
    printf("Peek: %d\n",*(int*)peek(queue));
    printf("Dequeue: %d\n",*(int*)deqeueu(queue,sizeof(int)));
    printLinkedListQueue(queue,printIntQueue);
}
#endif

[xiaozhuge123]

day04

[Ivy129]

打卡 2025年6月12日

[Mars13333]

发现一个问题，容易引起歧义。
在 基于数组的实现 的Go版本代码中，push方法的内部备注有问题。
// 当 rear == queCapacity 表示队列已满

[rongchuan17]

捉个虫，循环队列c语言中" queSize"的注释因该是队列长度吧，感觉写错了

[hollandaise1]

所以说为什么可以通过环形数组取余操作找到队尾？这个是唯一且最有效的方法吗？

[night-god-7158]

这里我觉得应该是判断如果小于当前容量就是其自身，如果等于的话就是为0

[SunSai9980]

基于链表实现的rust代码有bug：
在实现push方法时，let new_rear = ListNode::new(num);应改为 let new_rear = Rc::new(RefCell::new(ListNode::new(num)));不然类型不配

[lingfeng11111]

想起来老师教的队列定义方法跟博主的定义方法相反,博主教的是front指向第一个元素,rear指向队列后一个空位,我们老师是front指向前面一个空位,rear指向最后一个元素,虽然本质都一样,但是代码部分还是给我看迷糊了hhhhh

[zhengads]

先理解基本概念，代码部分第二轮再看

[jyqs9]

加油

[stackoverfolw]

基于数组的实现出队需先读取队首元素再自增front和front+size,不然就会丢失了这个元素数据

[stackoverfolw]

这里使用数组定义的环形队列queuesize不是尾指针，二十当前元素个数。

[Zzy-maker-eng]

到目前为止,都是线性表的顺式与链式的衍生

[X-Fly-E]

5.2.2 队列实现
可视化运行 出现的下面的错误，其它地方也有一些。
有劳修正一下。

Error! your code is around 5613 URL-encoded bytes, which is too long for this tool.
Shorten your code to less than 5600 bytes and re-try. [#ErrorCodeTooLong]
see UNSUPPORTED FEATURES or click "Get AI Help" to debug this error

[OrangeAlien]

说一个设计上的思想，为什么在用链表实现栈和队列时要用栈顶和队首作为链表头部，而不是反过来。这个是由单链表的性质决定的，有尾指针的情况下，单表链不论头插、尾插、头删都很简单，但是尾删需要遍历一次链表。因此，在设计时把需要删除操作的一侧当做头部，对应的就是栈顶和队首做头部，栈底和队尾做尾部，下一章的双端队列由于两端都有删除操作，因此难以通过单链表实现，需要考虑使用双链表实现。

在删除的一端，头指针可以通过next访问到下一个元素，而反过来尾指针无法访问到上一个元素。在插入的一端则不受这个影响，不论头插或者尾插都很方便。