chapter_stack_and_queue/queue/ #149
Replies: 68 comments 68 replies
|
针对Java的Queue类补充一些知识点:
队列除了基本的 Collection 操作外,还提供特有的插入、提取和检查操作(如上)。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作)。 |
|
循环数组 -🐂的 |
|
pop = que.popleft() 这里python的实现应该是pop = que.pop(0),3.9.0版本无popleft用法,pooleft是用于collections中的deque对象 |
|
队列一章中,包括双向队列,有些地方入队用 push , 有些地方入队用 offer,建议统一一下使文章更严谨。比如统一使用 Java 中的用词 offer |
|
class typing.Deque 3.9 版后已移除,这个类型注解会导致程序报错 import typing
import collections
que: Deque[int] = collections.deque()
-------------------------------------------------
NameError: name 'Deque' is not defined |
|
打卡,手敲了一遍链表和循环数组实现队列,不过我好像只能跟着敲。 |
|
基于链表实现的队列进行入队操作,如果队列不为空,则将该节点添加到尾节点后中的else语句里这两句不理解 rear.next = node; rear = node;,不应该只用rear.next = node;就行了嘛 |
|
问题:执行到 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++;
} |
|
问题:环形数组队列的有效长度不应该是Maxsize=len(self.__nums)-1 |
|
res = [0] * self.size()这种初始化队列的方式,会导致res 的每个元素引用相同的地址吗,就是如果我改动res[0]=1,那么res[1]、res[2]、...会不会因为存放的是相同的地址,导致都变为1 |
|
在5.2.2的第1节基于链表的实现,C语言代码的打印队列函数中,for循环语句条件queue->front != queue->rear是用来检测队列是否为空吗?但是如果队列中只有一个元素,好像就会打印不出那个单独的元素 |
|
环形数组队列扩容 /* 入队 */
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;
} |
|
c++链表实现的队列,入队push()那里我有两个疑问: |
/* 出队 */
void pop(linkedListQueue *queue) {
int num = peek(queue);
ListNode *tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
queue->queSize--;
}这段代码中的 num 是为了记录出队元素吧 但是没看到相关的用处 原文中没有把它return出去 |
|
对指针不熟理解链表实现的队列还是有点难度。。。 /// <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];
}
} |
|
使用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 &¤t->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 |
|
day04 |
|
打卡 2025年6月12日 |
|
发现一个问题,容易引起歧义。 |
|
捉个虫,循环队列c语言中" queSize"的注释因该是队列长度吧,感觉写错了 |
|
所以说为什么可以通过环形数组取余操作找到队尾?这个是唯一且最有效的方法吗? |
|
基于链表实现的rust代码有bug: |
|
想起来老师教的队列定义方法跟博主的定义方法相反,博主教的是front指向第一个元素,rear指向队列后一个空位,我们老师是front指向前面一个空位,rear指向最后一个元素,虽然本质都一样,但是代码部分还是给我看迷糊了hhhhh |
|
先理解基本概念,代码部分第二轮再看 |
|
加油 |
|
基于数组的实现出队需先读取队首元素再自增front和front+size,不然就会丢失了这个元素数据 |
|
到目前为止,都是线性表的顺式与链式的衍生 |
|
5.2.2 队列实现 Error! your code is around 5613 URL-encoded bytes, which is too long for this tool. |
|
说一个设计上的思想,为什么在用链表实现栈和队列时要用栈顶和队首作为链表头部,而不是反过来。这个是由单链表的性质决定的,有尾指针的情况下,单表链不论头插、尾插、头删都很简单,但是尾删需要遍历一次链表。因此,在设计时把需要删除操作的一侧当做头部,对应的就是栈顶和队首做头部,栈底和队尾做尾部,下一章的双端队列由于两端都有删除操作,因此难以通过单链表实现,需要考虑使用双链表实现。 在删除的一端,头指针可以通过next访问到下一个元素,而反过来尾指针无法访问到上一个元素。在插入的一端则不受这个影响,不论头插或者尾插都很方便。 |

Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
chapter_stack_and_queue/queue/
一本动画图解、能运行、可提问的数据结构与算法入门书
https://www.hello-algo.com/chapter_stack_and_queue/queue/
All reactions