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

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

[1127924631]

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

[illusionno]

基于链表实现中 判断队列是否为空 , 应该是这样吧
isEmpty() {
return this.size() === 0;
}

[illusionno]

是我看错了，前面用get 声明，可以直接用属性访问

[921000]

public class ArrayQueue {

private int[] queue;

/**
 * 头指针 指向 最先进去的元素，取出队列时 +1
 */
private int front;

/**
 * 尾指针 指向 入队位置，从0开始
 */
private int rear;

/**
 * 队列容量
 */
private int capacity;

/**
 * 队列长度
 */
private int size;

public ArrayQueue(int capacity) {
    this.capacity = capacity;
    this.queue = new int[capacity];
    this.front = 0;
    this.rear = -1;
}

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

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

public int peek() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return queue[front];
}

public int pop() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    int data = queue[front];
    front = (front + 1) % capacity;
    size--;
    return data;
}

public void push(int data) {
    if (isFull()) {
        throw new IndexOutOfBoundsException();
    }
    rear = (rear + 1) % capacity;
    queue[rear] = data;
    size++;
}

}
基于数组实现队列

[Blueman123456]

为什么基于链表实现访问队列队首元素时要考虑长度不为0的同时，还要考虑头节点是否为空；而访问栈顶元素时不要考虑顶部节点为空；我认为访问队首元素时，只需要考虑该队列是否为空，而判断是否为空的函数isempty也是基于队列元素个数是否为0判断的；所以我认为应该不需要判断头节点是否为空也无大碍。

[921000]

栈添加和删除都是在头节点，所以不需要判空
队列是头节点删除，尾节点添加。队列需要再添加第一条数据的时候给头节点赋值，不判空怎么确定啥时候给头节点赋值呢？

[921000]

看错了，访问的时候 如果不判空，没有数据，不就空指针了么

[xlyyddy]

int peek(LinkedListQueue *queue) {
assert(size(queue) && queue->front);
return queue->front->val;
}为什么基于链表实现访问队列队首元素时要考虑长度不为0的同时，还要考虑头节点是否为空；而访问栈顶元素时不要考虑顶部节点为空；我认为访问队首元素时，可以只需要考虑该队列是否为空，而判断是否为空的函数isempty也是基于队列元素个数是否为0判断的；如果不出现特殊的异常情况，那么我是否可以认为应该不需要判断头节点是否为空也无大碍吗
gpt回答：
你提出了一个很好的问题。在使用链表实现队列时,访问队首元素时需要同时检查队列是否为空和头节点是否为空,而访问栈顶元素时只需要检查栈是否为空,不需要检查栈顶节点是否为空。这是因为两种数据结构的特点不同导致的。

队列:

队列是先进先出的数据结构,队首元素是最早进入队列的元素。
如果队列为空,那么队首元素肯定是不存在的,此时需要检查队列是否为空。
如果队列不为空,但是头节点为空,也意味着队首元素不存在,需要同时检查这两种情况。
栈:

栈是先进后出的数据结构,栈顶元素是最后进入栈的元素。
如果栈为空,那么栈顶元素肯定是不存在的,此时需要检查栈是否为空。
但是,即使栈不为空,栈顶节点也一定存在,因为如果栈不为空,那么栈顶节点一定存在。所以不需要额外检查栈顶节点是否为空。
你提出的观点是正确的,在正常情况下,如果队列不为空,那么头节点一定存在,不需要额外检查头节点是否为空。但是,为了处理一些特殊情况,比如在插入或删除操作时出现了异常,导致头节点为空的情况,还是需要对头节点进行检查。这样可以更健壮地处理各种情况,避免出现未定义行为或崩溃。

所以你说的,如果不出现特殊的异常情况,那么只需要判断队列是否为空,而不需要判断头节点是否为空,这个观点是正确的。但为了更健壮的实现,最好还是同时检查这两个条件。

[ZZY080]

当队列为空时 队首节点问null return this.#front.value; null.value 会报错

[921000]

public class LinkQueue {

private Node<T> head;

private Node<T> tail;

private int size;

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

public class Node<T> {

    /**
     * 存储数据 节点
     */
    private T data;

    /**
     * 下一个节点
     */
    private Node<T> next;

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

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

public void push(T data){
    Node<T> newNode = new Node<>(data);
    if (isEmpty()) {
        head = newNode;
    } else {
        // 队尾添加
        tail.next = newNode;
    }
    // 队尾 指向新节点
    tail = newNode;
    size++;
}

public T peek() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return head.data;
}

public T pop() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    T data = head.data;
    // 队首删除
    head = head.next;
    size--;
    return data;
}

}
基于链表实现队列

[iVapor]

作者你好，数组实现队列的 js 代码 array_queue.js 类 LinkedListQueue 的方法 get size 命名有点问题，应该是驼峰的。

get size() {
        return this.#queSize;
    }

[ZZY080]

使用了 JavaScript 的getter特性。get size() 是一个 getter 方法，它允许你像访问属性一样访问 size，而不是调用一个函数。

[lildayuan]

freeMemoryLinkedList(front)这个是内置函数还是什么呀？怎么没有看到这个函数的实现？

[ouyangyipeng]

void freeMemoryLinkedList(ListNode* a){
while(a!=nullptr){
ListNode* tmp=a;
a=a->next;
free(tmp);
}
}

[gopherHsu]

基于数组的队列，扩容方法：

/* 扩容队列 */
private void extendCapacity() {
    // 新建一个长度为原数组 extendRatio 倍的新数组，并将原数组复制到新数组
    nums = Arrays.copyOf(toArray(), capacity() * extendRatio);
    front = 0;
}

[FrierenGreatDemonLord]

1. 取模保证了下标不会溢出[0, capacity-1]
2. font + size = rear，同时取模保证不会溢出
3. front + 1 = new_front（在出队时的新front 下标），同时取模保证不会溢出

[FrierenGreatDemonLord]

这个用“环形数组”实现队列真的太巧妙了，各种操作刚好保证了下标不会溢出，而且数据在数组里都是连续存储的，也不会被覆盖或者打印了内存里的垃圾值（如 python 里默认给的0，C 里该地址上的随机值……）

[FrierenGreatDemonLord]

这设计、这操作够学一辈子😀

[yexiaoye-blue]

你好，在 队列实现 => 基于链表的实现章节 python代码中

def pop(self) -> int:
  """出队"""
  num = self.peek()
  # 删除头节点
  self._front = self._front.next
  self._size -= 1
  return num

是否需要考虑当队列中只有1个元素的情况，文章中的self._front=self._front.next虽在“只有1个元素”时，将_front至为None，但是_rear仍然有值。只是初学者，单纯不太懂其中含义。

# 出队
def pop(self) -> int:
  num = self.peek()
  if self.size() == 1:
    self._front = None
    self._rear = None
  else:
    self._front = self._front.next
  self._size -= 1
  return num

[YiChau]

我也觉得这里有问题，当只有一个元素时，front和rear都应该置为null。

[wangbingqiang909]

在 hello-algo 里面的基于环形数组实现的队列用c语言在vim上运行之后最后的答案是有问题的

[wangbingqiang909]

在测试环形数组那一节得出来的答案有问题的。

[shyGuide]

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

---

rear.next = node;
rear = node;

这两行还是理解了很长时间

[YiChau]

先把node添加到现有的队列的尾节点之后，再让尾指针指向最新的“尾”节点。

[xuaidongx]

#ifndef __CUSTOMQUEUE_HPP__
#define __CUSTOMQUEUE_HPP__

/**
 * @file customQueue.hpp
 * @brief 基于数组和链表实现队列
 */

#include <cstdint>
#include <memory>
#include <stdexcept>

template<typename T, template<typename> typename Container>
class customQueue
{
public:
    void push_back(const T& v){m_elements.push_back(v);}
    void pop_front() {m_elements.pop_front();}
    const T& front() const {return m_elements.front();}
    T& front() {return const_cast<T&>(const_cast<const customQueue*>(this)->front());}
    bool empty() const {return m_elements.empty();}
    std::size_t size() const {return m_elements.size();}
private:
    Container<T> m_elements;
};

template<typename T>
class listContainer
{
struct linknode
{
    T value;
    std::shared_ptr<linknode> next;
    linknode(const T& v, std::shared_ptr<linknode> node):value(v), next(node){}
};
public:
    void push_back(const T& v)
    {
        if (!m_front && !m_rear)
        {
            m_front = std::make_shared<linknode>(v, m_rear);
            m_rear = m_front;
        }
        else
        {
            m_rear->next = std::make_shared<linknode>(v, nullptr);
            m_rear = m_rear->next;
        }
        ++m_size;
    }

    void pop_front()
    {
        if (empty())
            return;
        
        if (m_front == m_rear)
        {
            m_front = nullptr, m_rear = nullptr;
            --m_size;
            return;
        }

        m_front = m_front->next;
        --m_size;
    }

    const T& front() const {return m_front->value;}

    bool empty() const {return m_size == 0;}
    std::size_t size() const {return m_size;}
private:
    std::size_t m_size{0};
    std::shared_ptr<linknode> m_front{nullptr};
    std::shared_ptr<linknode> m_rear{nullptr};
};

template<typename T>
class arrayContainer
{
public:
    arrayContainer(std::size_t capacity = 100):m_capacity(capacity)
    {
        m_array = std::make_unique<T[]>(m_capacity);
    }

    void push_back(const T& v)
    {
        if (m_size == m_capacity && !realloc())
            return;

        auto rear = (m_front + m_size) % m_capacity;
        m_array[rear] = v;
        ++m_size;
    }

    void pop_front()
    {
        if (empty())
            return;
        
        m_front = (m_front + 1) % m_capacity;
        --m_size;
    }

    const T& front() const
    {
        if (empty())
            throw std::out_of_range("container is empty");
        
        return m_array[m_front];
    }

    bool empty() const {return m_size == 0;}
    std::size_t size() const {return m_size;}

    bool realloc()
    {
        auto new_capacity = m_capacity * 2;
        auto new_array = std::make_unique<T[]>(new_capacity);
        if (!new_array)
            return false;
        std::copy(&m_array[0], &m_array[m_size - 1], &new_array[0]);
        m_array = std::move(new_array);
        m_capacity = new_capacity;
        return true;
    }
private:
    std::size_t m_size{0};
    std::size_t m_capacity{0};
    std::unique_ptr<T[]> m_array;

    std::size_t m_front{0};
};

template<typename T>
using queueByList = customQueue<T, listContainer>;

template<typename T>
using queueByArray = customQueue<T, arrayContainer>;

#endif

[Unsichtbare1]

分享一个我在引入扩容机制的时候遇到的问题吧。一开始我在尝试用.size()去处理扩容问题，但是会遇到如下问题：
假设初始长度=5，
1：push成[1,2,3,4,5]
2：pop(), [2,3,4,5]
3: push(6), push(7)打印的结果会是[2,3,4,5,0,7] 这是因为用size计数push(6)的时候不会触发扩容，也就是push(6)之后的数组是[6,2,3,4,5]，再push(7)触发扩容变成[6,2,3,4,5,0,7]了。（扩容就是在后边加很多0）

所以要解决这个就是要在push(6)的时候就扩容，也就是对push也计数并根据push的个数来触发扩容，这样就可以解决这个问题。