数据结构（栈）

ops/2024/10/23 22:04:49/

1栈的定义和操作

栈（Stack）是一种线性数据结构，遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后一个被放入栈中的元素会第一个被取出。栈通常用于需要在其中临时存储数据并按照特定顺序访问这些数据的场景。

栈的基本操作

  1. Push（压栈）：

    • 将一个元素放入栈的顶部。
    • 如果栈已经满了，可能会导致栈溢出（Stack Overflow）。

  2. Pop（弹栈）：

    • 从栈的顶部移除一个元素，并返回该元素。
    • 如果栈是空的，可能会导致栈下溢（Stack Underflow）。

  3. Peek（查看栈顶）：

    • 查看栈顶的元素，但不移除它。
    • 这个操作不会改变栈的状态。

  4. IsEmpty（判断栈是否为空）：

    • 检查栈是否为空。
    • 返回一个布尔值，通常是 true 或 false。

  5. IsFull（判断栈是否已满）：

    • 检查栈是否已满。
    • 返回一个布尔值，通常是 true 或 false。

栈的实现方式

栈可以通过数组或链表来实现：

  1. 数组实现：

    • 需要预先分配固定大小的数组。
    • 优点是存取时间快，但缺点是大小固定。

  2. 链表实现：

    • 使用链表节点动态分配内存。
    • 优点是大小灵活，但存取时间可能稍慢。

栈的应用

栈在计算机科学中有广泛的应用，例如：

  1. 函数调用：

    • 在程序执行过程中，函数调用和返回的顺序与栈的操作模式一致。

  2. 表达式求值：

    • 使用栈来解析和计算数学表达式，例如中缀表达式转换为后缀表达式。

  3. 括号匹配：

    • 使用栈来检查括号是否正确匹配。

  4. 浏览器历史记录：

    • 浏览器的前进和后退功能可以使用两个栈来实现。

  5. 回溯算法：

    • 在需要回溯的算法中，栈用于保存当前状态以便回退。

2栈的存储和实现

2.1顺序栈

1顺序栈的定义和初始化

固定长度顺序栈的定义

我们首先定义一个结构体 SeqStack，其中包含一个固定长度的数组 data 来存储栈的元素，以及一个整型变量 top 来表示栈顶的位置。

#define MAX_SIZE 5  // 定义栈的最大容量typedef struct {int data[MAX_SIZE];  // 存储栈元素的数组int top;             // 栈顶指针
} SeqStack;

固定长度顺序栈的初始化

初始化顺序栈时，我们需要将栈顶指针 top 设置为 -1，表示栈为空。

void initStack(SeqStack* stack) {stack->top = -1;  // 初始化栈顶指针为 -1，表示栈为空
}

 2动态分配顺序栈初始化

#define INITIAL_SIZE 10 // 初始容量// 顺序栈结构
typedef struct {int *data; // 存储栈元素的动态数组int top;   // 当前栈顶元素的索引int size;  // 栈的当前容量
} SeqStack;// 初始化顺序栈
SeqStack* initStack() {SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack)); // 分配栈结构的内存if (!stack) {printf("内存分配失败\n");return NULL;}stack->data = (int*)malloc(INITIAL_SIZE * sizeof(int)); // 分配栈数据的内存if (!stack->data) {printf("内存分配失败\n");free(stack); // 如果数据分配失败，释放栈结构的内存return NULL;}stack->top = -1;  // 栈顶索引初始化为 -1（表示栈为空）stack->size = INITIAL_SIZE; // 初始容量设置return stack;
}

 2顺序栈的基本操作

判断栈是否为空

// 判断栈是否为空的函数
// 返回值: 如果栈为空，返回 1；否则返回 0
int isEmpty(SeqStack* stack) {if (stack->top == -1) {// 当栈顶索引为 -1 时，表示栈中没有元素，栈为空return 1; // 栈为空} else {return 0; // 栈非空}
}

判断栈是否已满

// 判断栈是否已满的函数
// 参数: stack - 指向顺序栈的指针
// 返回值: 如果栈已满，返回 1；否则返回 0
int isFull(SeqStack* stack) {if (stack->top >= stack->size - 1) {// 当栈顶索引大于等于栈的最大容量减 1 时，表示栈已满return 1; // 栈已满} else {return 0; // 栈未满}
}


顺序栈的进栈 

int push(SeqStack* stack, int value) {// 检查是否已满if (isFull(stack)) {// 如果已满，扩展栈的容量int newSize = stack->size * 2; // 新容量为当前容量的两倍int* newData = (int*)realloc(stack->data, newSize * sizeof(int)); // 扩容if (!newData) {printf("内存重新分配失败\n");return 0; // 扩容失败，返回 0}stack->data = newData; // 更新数据指针stack->size = newSize; // 更新栈的容量}// 先更新栈顶索引，再将元素添加到栈顶stack->top++; // 将栈顶索引加 1stack->data[stack->top] = value; // 将新元素赋值给栈顶return 1; // 返回成功标志
}

顺序栈的出栈 

int pop(SeqStack* stack) {// 检查栈是否为空if (isEmpty(stack)) {printf("栈为空，无法出栈\n");return -1; // 栈为空，返回 -1}// 1. 获取当前栈顶元素int topElement = stack->data[stack->top];// 2. 更新栈顶索引，表示出栈操作stack->top--;// 返回栈顶元素return topElement;
}

获取栈顶元素

// 获取栈顶元素
int top(SeqStack* stack) {// 检查栈是否为空if (isEmpty(stack)) {printf("栈为空，无法获取栈顶元素\n");return -1; // 栈为空，返回 -1}// 返回当前栈顶元素return stack->data[stack->top]; // 直接访问栈顶元素
}

2.2链式栈

1链式栈的定义与初始化

.链式栈的节点定义

首先，我们需要定义链式栈的节点结构体。每个节点将包含一个数据字段和一个指向下一个节点的指针。

#include <stdio.h>
#include <stdlib.h>// 链式栈节点结构
typedef struct Node {int data;               // 节点存储的数据struct Node* next;     // 指向下一个节点的指针
} Node;

链式栈的结构定义

接下来，我们定义链式栈的结构体。它将包含一个指向栈顶节点的指针。

// 链式栈结构
typedef struct {Node* top;  // 指向栈顶节点的指针
} LinkStack;

初始化链式栈

初始化链式栈时，我们只需将栈顶指针设置为 NULL，表示栈初始为空。

// 初始化链式栈
LinkStack* initLinkStack() {LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack)); // 分配内存if (stack == NULL) {printf("内存分配失败\n");return NULL; // 初始化失败}stack->top = NULL; // 初始化栈顶指针为 NULLreturn stack; // 返回初始化后的栈
}

2链式栈的基本操作

  判断栈是否为空

// 判断栈是否为空
int isEmpty(LinkStack* stack) {return stack->top == NULL; // 返回栈顶指针是否为 NULL
}

入栈操作（push）

// 入栈操作
void push(LinkStack* stack, int value) {// 1. 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");return;}// 2. 设置新节点的数据和指针newNode->data = value;   // 设置新节点的数据newNode->next = stack->top; // 新节点的下一个节点指向当前的栈顶节点// 3. 更新栈顶指针stack->top = newNode;    // 栈顶指针指向新节点
}

出栈操作（pop）

// 出栈操作
int pop(LinkStack* stack) {// 1. 检查栈是否为空if (isEmpty(stack)) {printf("栈为空，无法出栈\n");return -1; // 栈为空，返回 -1}// 2. 获取当前栈顶节点的数据Node* topNode = stack->top; // 获取当前栈顶节点int value = topNode->data;  // 获取当前栈顶节点的数据// 3. 更新栈顶指针stack->top = topNode->next; // 栈顶指针指向下一个节点// 4. 释放原栈顶节点free(topNode);              // 释放原栈顶节点的内存// 5. 返回出栈的元素return value;
}

完整示例代码：

#include <stdio.h>
#include <stdlib.h>// 链式栈节点结构
typedef struct Node {int data;               // 节点存储的数据struct Node* next;     // 指向下一个节点的指针
} Node;// 链式栈结构
typedef struct {Node* top;  // 指向栈顶节点的指针
} LinkStack;// 初始化链式栈
LinkStack* initLinkStack() {LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack)); // 分配内存if (stack == NULL) {printf("内存分配失败\n");return NULL; // 初始化失败}stack->top = NULL; // 初始化栈顶指针为 NULLreturn stack; // 返回初始化后的栈
}// 判断栈是否为空
int isEmpty(LinkStack* stack) {return stack->top == NULL; // 返回栈顶指针是否为 NULL
}// 入栈操作
void push(LinkStack* stack, int value) {// 1. 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");return;}// 2. 设置新节点的数据和指针newNode->data = value;   // 设置新节点的数据newNode->next = stack->top; // 新节点的下一个节点指向当前的栈顶节点// 3. 更新栈顶指针stack->top = newNode;    // 栈顶指针指向新节点
}// 出栈操作
int pop(LinkStack* stack) {// 1. 检查栈是否为空if (isEmpty(stack)) {printf("栈为空，无法出栈\n");return -1; // 栈为空，返回 -1}// 2. 获取当前栈顶节点的数据Node* topNode = stack->top; // 获取当前栈顶节点int value = topNode->data;  // 获取当前栈顶节点的数据// 3. 更新栈顶指针stack->top = topNode->next; // 栈顶指针指向下一个节点// 4. 释放原栈顶节点free(topNode);              // 释放原栈顶节点的内存// 5. 返回出栈的元素return value;
}// 主函数示例
int main() {LinkStack* stack = initLinkStack(); // 初始化链式栈if (stack == NULL) {return -1; // 初始化失败}// 进行入栈操作push(stack, 10); // 入栈 10push(stack, 20); // 入栈 20push(stack, 30); // 入栈 30// 进行出栈操作int poppedValue = pop(stack);if (poppedValue != -1) {printf("出栈元素: %d\n", poppedValue); // 打印出栈元素}// 打印剩余的栈元素Node* current = stack->top;while (current != NULL) {printf("栈元素: %d\n", current->data);current = current->next;}return 0;
}

3栈的应用举例

3.1进制转换

进制转换是一种常见的应用场景，特别是在需要将一个数从一种进制（例如十进制）转换为另一种进制（例如二进制、八进制或十六进制）时。栈的先进后出（LIFO）特性非常适合用于这种转换，因为我们需要从高位到低位依次处理数字。

进制转换的基本原理

假设我们有一个十进制数 N，我们希望将其转换为 B 进制表示。进制转换的基本步骤如下：

  1. 使用 N 除以 B，得到商和余数。
  2. 将余数压入栈中（因为我们需要从低位到高位依次处理）。
  3. 将商作为新的 N，重复步骤 1 和 2，直到 N 变为 0。
  4. 依次出栈，得到的结果就是 N 的 B 进制表示。

使用栈进行进制转换的示例代码

以下是一个将十进制数转换为二进制的示例代码，使用顺序栈来存储余数。

void conversion(int n) {SeqStack stack; // 创建顺序栈initStack(&stack); // 初始化栈// 处理十进制数的转换while (n > 0) {int abse = n % 2; // 计算余数push(&stack, abse); // 将余数入栈n /= 2; // 更新 n 的值}// 输出转换结果printf("二进制表示: ");while (!isEmpty(&stack)) {printf("%d", pop(&stack)); // 出栈并打印}printf("\n");
}

完整代码：


#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 定义栈的最大容量// 顺序栈结构
typedef struct {int data[MAX_SIZE]; // 存储元素的数组int top;            // 栈顶指针
} SeqStack;// 初始化顺序栈
void initStack(SeqStack* stack) {stack->top = -1; // 栈指针初始化为 -1，表示栈空
}// 判断栈是否为空
int isEmpty(SeqStack* stack) {return stack->top == -1; // 栈空返回 1，否则返回 0
}// 入栈操作
int push(SeqStack* stack, int value) {if (stack->top == MAX_SIZE - 1) {printf("栈满，无法入栈\n");return -1; // 栈满，返回 -1}stack->top++; // 先增加栈顶指针stack->data[stack->top] = value; // 然后将值存入栈中return 0; // 成功入栈
}// 出栈操作
int pop(SeqStack* stack) {if (isEmpty(stack)) {printf("栈空，无法出栈\n");return -1; // 栈空，返回 -1}int value = stack->data[stack->top]; // 先获取栈顶数据stack->top--; // 然后减少栈顶指针return value; // 返回栈顶数据; // 返回栈顶数据并减少栈顶指针
}// 十进制转二进制函数
void conversion(int n) {SeqStack stack; // 创建顺序栈initStack(&stack); // 初始化栈// 处理十进制数的转换while (n > 0) {int abse = n % 2; // 计算余数push(&stack, abse); // 将余数入栈n /= 2; // 更新 n 的值}// 输出转换结果printf("二进制表示: ");while (!isEmpty(&stack)) {printf("%d", pop(&stack)); // 出栈并打印}printf("\n");
}// 主函数
int main() {int number;printf("请输入一个十进制整数: ");scanf("%d", &number);conversion(number); // 调用进制转换函数return 0;
}

3.2表达式转换和求值

使用栈来实现表达式转换和求值是一个常见的编程任务。我们可以通过栈来实现中缀表达式到后缀表达式（逆波兰表达式）的转换，然后再使用栈来计算后缀表达式的值。

中缀表达式转后缀表达式

中缀表达式是我们通常使用的表达式形式，例如 3 + 4 * 2 / (1 - 5)^2。后缀表达式（逆波兰表达式）是一种不需要括号的表达式形式，例如 3 4 2 * 1 5 - 2 ^ / +。

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

思路：

逆波兰表达式部分代码：

// 计算逆波兰表达式的值
int evalRPN(char** tokens, int tokensSize) {int stack[tokensSize]; // 定义栈，用于存储操作数int top = -1;          // 栈顶指针，初始值为 -1 表示栈为空// 遍历给定的令牌数组for (int i = 0; i < tokensSize; ++i) {// 判断当前令牌是否为运算符if (strcmp(tokens[i], "+") == 0 || strcmp(tokens[i], "-") == 0 || strcmp(tokens[i], "*") == 0 || strcmp(tokens[i], "/") == 0) {// 弹出栈顶的两个操作数int a = stack[top--]; // 第一个操作数int b = stack[top--]; // 第二个操作数// 执行相应的运算并将结果压入栈中if (strcmp(tokens[i], "+") == 0) {stack[++top] = b + a; // 加法}if (strcmp(tokens[i], "-") == 0) {stack[++top] = b - a; // 减法}if (strcmp(tokens[i], "*") == 0) {stack[++top] = b * a; // 乘法}if (strcmp(tokens[i], "/") == 0) {stack[++top] = b / a; // 除法}} // 如果当前令牌是数字else {// 将字符串转换为整数并压入栈中stack[++top] = atoi(tokens[i]);}}// 返回栈顶的结果，即逆波兰表达式的值return stack[top];
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 计算逆波兰表达式的值
int evalRPN(char** tokens, int tokensSize) {int stack[tokensSize]; // 定义栈，用于存储操作数int top = -1;          // 栈顶指针，初始值为 -1 表示栈为空// 遍历给定的令牌数组for (int i = 0; i < tokensSize; ++i) {// 判断当前令牌是否为运算符if (strcmp(tokens[i], "+") == 0 || strcmp(tokens[i], "-") == 0 || strcmp(tokens[i], "*") == 0 || strcmp(tokens[i], "/") == 0) {// 弹出栈顶的两个操作数int a = stack[top--]; // 第一个操作数int b = stack[top--]; // 第二个操作数// 执行相应的运算并将结果压入栈中if (strcmp(tokens[i], "+") == 0) {stack[++top] = b + a; // 加法}if (strcmp(tokens[i], "-") == 0) {stack[++top] = b - a; // 减法}if (strcmp(tokens[i], "*") == 0) {stack[++top] = b * a; // 乘法}if (strcmp(tokens[i], "/") == 0) {stack[++top] = b / a; // 除法}} // 如果当前令牌是数字else {// 将字符串转换为整数并压入栈中stack[++top] = atoi(tokens[i]);}}// 返回栈顶的结果，即逆波兰表达式的值return stack[top];
}// 示例主函数
int main() {char* tokens[] = {"2", "1", "+", "3", "*"}; // 示例逆波兰表达式: (2 + 1) * 3int tokensSize = sizeof(tokens) / sizeof(tokens[0]);int result = evalRPN(tokens, tokensSize);printf("计算结果: %d\n", result); // 输出: 9return 0;
}


http://www.ppmy.cn/ops/127930.html

相关文章

数据处理利器：图片识别转Excel表格让数据录入变简单

数据处理利器：图片识别转Excel表格让数据录入变简单

在现代职场中&#xff0c;手动录入数据是一个耗时且容易出错的过程。无论是纸质文件、照片还是截图&#xff0c;繁琐的输入常常让人感到头疼。如何高效地将这些信息转化为电子表格&#xff0c;是许多职场人士面临的挑战。 为了解决这一问题&#xff0c;我们推出了图片识别转Exc…
阅读更多...
【优选算法】探索双指针之美（一）:双指针与单调性的完美邂逅

【优选算法】探索双指针之美（一）:双指针与单调性的完美邂逅

文章目录 前言&#xff1a;1.盛水最多的容器2.有效三角形个数3. 和为s的两个数字4. 三数之和5. 四数之和 最后想说&#xff1a; 前言&#xff1a; 在上一章中我们已经认识到了双指针&#xff0c;在这章里我们就来探索一下当双指针和单调性遇见后会擦出怎样的火花呢&#xff1f…
阅读更多...
c++ STL标准模板库-算法

c++ STL标准模板库-算法

C Standard Template Library&#xff08;STL&#xff09;算法是一组泛型算法&#xff0c;它们可以在各种容器上操作。这些算法被设计为与容器无关&#xff0c;因此可以在任何提供必要迭代器接口的容器上使用。STL算法分为以下几个主要类别&#xff1a; 非修改算法Non-modifyi…
阅读更多...
滚雪球学Redis[9.2讲]：Redis的最佳实践：高效应用与常见反模式规避指南

滚雪球学Redis[9.2讲]：Redis的最佳实践：高效应用与常见反模式规避指南

全文目录&#xff1a; &#x1f389;前言&#x1f6a6;1. Redis使用中的通用原则&#x1f34b;1.1 数据结构的选择与优化&#x1f34b;‍&#x1f7e9;1.2 有效利用过期策略&#x1f34c;1.3 避免大型键值 &#x1f504;2. 典型业务场景中的最佳实践&#x1f34d;2.1 缓存场景&…
阅读更多...
AD如何制作原理图的模版、原理图模板绘制修改以及如何导入原理图模版

AD如何制作原理图的模版、原理图模板绘制修改以及如何导入原理图模版

作为硬件工程师&#xff0c;制定原理图模板是一项至关重要的任务&#xff0c;旨在标准化和规范原理图的绘制过程。在AD20中制作、绘制修改以及导入原理图模板的步骤如下&#xff1a; 1制作原理图模板 首先需在AD原理图设计环境下新建一个原理图文件&#xff1b; 在原理图界面…
阅读更多...
RabbitMQ系列学习笔记（八）--发布订阅模式

RabbitMQ系列学习笔记（八）--发布订阅模式

文章目录 一、发布订阅模式原理二、发布订阅模式实战1、消费者代码2、生产者代码3、查看运行结果 本文参考&#xff1a; 尚硅谷RabbitMQ教程丨快速掌握MQ消息中间件rabbitmq RabbitMQ 详解 Centos7环境安装Erlang、RabbitMQ详细过程(配图) 一、发布订阅模式原理 在开发过程中&…
阅读更多...
基于Redis的字符串来进行营业状态的存储

基于Redis的字符串来进行营业状态的存储

简介&#xff1a;苍穹外卖p63-p65&#xff1b;Redis配置类见本人博客&#xff1a;一文搞懂Redis所有知识点 管理端Controller类 package com.sky.controller.admin;import com.sky.result.Result; import io.swagger.annotations.Api; import io.swagger.annotations.ApiO…
阅读更多...
10月22日，每日信息差

10月22日，每日信息差

第一、北京京能氢安科技有限公司近日成立&#xff0c;法定代表人为刘毅&#xff0c;注册资本 4800 万元。该公司由北京京能科技有限公司全资持股&#xff0c;后者是北京能源集团有限责任公司的全资子公司。公司经营范围包括站用加氢及储氢设施销售、储能技术服务、新兴能源技术…
阅读更多...
最新文章

Copyright @ 2022~2023