栈与队列和数组（下）

逆波兰表达式（补）

思路：可以直接建立一个大的数组作为栈，开始遍历字符串数据，当遇到数字的时候就把值存在新建的数组中吗，遇到运算符号就弹出两个值进行运算，之后又将字存在新建的数组中。

注意：1.int、char、short、long都是整型。在使用字符型的时候需要加上单引号。在里面很容易将字符打错。2.算完一次运算后需要将数据重新压回栈中

bool evalbool(char* tokens){ if(tokens[0]<='9'&&tokens[0]>='0'){// return true; } if(tokens[0]=='-'&&tokens[1]<='9'&&tokens[1]>='0'){ return true; } return false; } int evalRPN(char** tokens, int tokensSize) { int stackarr[10000]; int j=0; int sum=0; for(int i=0;i<tokensSize;i++){ if(evalbool(tokens[i])){// int mun =atoi(tokens[i]);// stackarr[j]=mun; j++; } else{ int right=stackarr[--j]; int left=stackarr[--j]; switch(tokens[i][0]){//这里可以看成一个二位数组的 case '+':sum=right+left; break; case '-':sum=left-right; break; case '*':sum=left*right; break; case '/':sum=left/right; break; } stackarr[j++]=sum;// } } return stackarr[0]; }

重点：二级指针的运用

二级指针是指向指针的指针，即一个指针变量存储的是另一个指针变量的地址。在逆波兰表达式的实现中，二级指针常用于在函数内部修改传入的指针本身，从而让栈顶指针的更新能够反映到调用方。

例如，当使用链表实现栈时，入栈操作需要修改栈顶指针 top 的指向。如果直接传入一级指针，函数内部对 top 的修改无法传回调用方；而传入二级指针（即 &top），函数内部通过 *top 就能修改调用方的 top 变量，从而正确维护栈顶。

典型写法如下：

void push(Node **top, int value) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = value; newNode->next = *top; *top = newNode; // 通过二级指针修改调用方的栈顶指针 } int pop(Node **top) { if (*top == NULL) return -1; Node *temp = *top; int value = temp->data; *top = temp->next; free(temp); return value; }

使用二级指针时需要注意：调用处必须传入栈顶指针的地址，即 &top；函数内部对 *top 的赋值会直接改变调用方的指针值。这样可以避免返回值传递的繁琐，也让代码更贴近底层指针操作的语义。

队列

队列是限定在一端插入、另一端删除的线性表，遵循先进先出（FIFO）原则。入队是在队尾进行插入，出队是在队头进行删除。实现队列时，通常采用链式存储或顺序存储两种方式。

链式存储实现队列的要点

链式存储使用链表节点保存数据，每个节点包含数据域和指向下一个节点的指针。实现时需要注意以下几点：

• 带头节点（哨兵位）：推荐使用带头节点的单链表，头节点不存储数据，便于统一处理空队列和首元素入队的情况。
• 维护 front 和 rear 指针：front 指向队头节点，rear 指向队尾节点。入队时在 rear 之后插入新节点并更新 rear；出队时删除 front 指向的节点并更新 front。
• 出队时注意 rear 指针：当队列中只剩一个节点时，出队后 front 和 rear 都会变为空，此时必须将 rear 也置为 NULL，否则 rear 会变成野指针。
• 判空条件：front 和 rear 都为空（或 front 指向头节点且 rear 指向头节点）时队列为空。
• 内存管理：出队删除节点后需要释放内存，避免内存泄漏。

顺序存储实现队列的要点

顺序存储使用数组保存数据，通过 front 和 rear 两个下标来标记队头和队尾。实现时需要注意以下几点：

• 假溢出问题：普通顺序队列中，rear 到达数组末尾时即使数组前面还有空闲空间，也无法继续入队，这就是假溢出。
• 解决假溢出：使用循环队列，让 rear 和 front 在到达数组末尾时回绕到数组开头。
• 判空与判满：循环队列中，判空条件为 front == rear；判满条件为 (rear + 1) % MaxSize == front，即牺牲一个存储单元来区分空和满。
• 元素个数计算：队列中元素个数为 (rear - front + MaxSize) % MaxSize。
• 入队操作：先判断是否满，不满则存入 data[rear]，再执行 rear = (rear + 1) % MaxSize。
• 出队操作：先判断是否空，不空则取出 data[front]，再执行 front = (front + 1) % MaxSize。

循环队列相关知识点

循环队列是顺序队列的改进，通过取模运算让 rear 和 front 在数组范围内循环移动，从而充分利用数组空间。核心知识点如下：

• 基本结构：使用数组 data[MaxSize] 存储元素，front 指向队头元素，rear 指向队尾元素的下一个位置。
• 入队：rear = (rear + 1) % MaxSize，然后将元素存入 data[rear]。
• 出队：取出 data[front]，然后 front = (front + 1) % MaxSize。
• 判空：front == rear。
• 判满：1.牺牲一个空间：(rear + 1) % MaxSize == front，此时数组中实际最多存储 MaxSize - 1 个元素。 2.通过计数的方式来判断是空还是满。
• 队列长度：(rear - front + MaxSize) % MaxSize。
• 应用场景：循环队列常用于操作系统中的缓冲区管理、生产者消费者模型、以及需要固定容量且频繁入队出队的场景。

队列的应用

这可以使用带有头节点的队列，这样可以方便插入，但是在删除的时候需要分情况讨论1.当队列中只有一个元素时，rear指针指与front指针指向同一位置;2.队列中元素不止有一个，这时直接进行头删即可

实现是会出现的问题：1.在执行的个个函数的时候需要检查队列是否是空队列。2.在销毁队列中：进行while循环释放队列的条件中：不能使用cur->next条件，这样的会跳过cur不空的情况；front和rear都需要置为空。3.把队列销毁后，使用打印函数会发生访问权限冲突。

#pragma once #include<assert.h> #include<stdlib.h> #include<stdio.h> typedef int QDataType; typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode; typedef struct Queue { QNode* _front; QNode* _rear; int size; }Queue; // 初始化队列 void QueueInit(Queue* q) { assert(q); q->_front = q->_rear = (QNode*)malloc(sizeof(QNode));//这里是为了创建一个节点 if (q->_front==NULL && q->_rear==NULL) { printf("creat shibai\n"); exit(-1); } q->_front->_next = NULL; q->size = 0; } // 队尾入队列 ,像是尾插 void QueuePush(Queue* q, QDataType data) { assert(q); QNode*pnew=(QNode*)malloc(sizeof(QNode)); pnew->_data = data; pnew->_next = NULL; q->_rear->_next = pnew; q->_rear = pnew; q->size++; } void PrintfQueue(Queue* q) { assert(q); QNode* cur = q->_front->_next; while (cur) { printf("%d-> ", cur->_data); cur = cur->_next; } printf("\n"); } // 队头出队列 void QueuePop(Queue* q) { QNode* cur = q->_front->_next; q->_front->_next = cur->_next; free(cur); } // 获取队列头部元素 QDataType QueueFront(Queue* q) { return q->_front->_next->_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { QNode* cur = q; while (cur->_next) { cur = cur->_next; } return cur->_data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { QNode* cur = q->_front; int num = 0; while (cur && cur->_next) { num++; cur = cur->_next; } return num; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { if (q->_front->_next == NULL) { return 1; } return 0; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->_front; while (cur) { QNode* pro = cur->_next; free(cur); cur = pro; } q->_front = NULL; q->_rear = NULL; q->size = 0; }