数据结构中的栈（C语言版）

ops/2024/12/22 16:02:52/

一.栈的概念

栈是一种常见的数据结构，它遵循后进先出的原则。栈可以看作是一种容器，其中的元素按照一种特定的顺序进行插入和删除操作。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.栈的特点

    1.元素的插入和删除操作只能在栈的一端进行，该端被称为栈顶。

    2.最后插入的元素是第一个被删除的元素，因此称为后进先出。

    3.栈中的元素没有编号或索引，只有栈顶指针来指示栈的当前位置。

2.栈的优点

  1. 简单高效：栈的操作是基于后进先出（LIFO）的原则，入栈和出栈操作都只涉及栈顶元素，因此操作的时间复杂度都是O(1)，使得栈的操作非常高效。

  2. 空间效率高：栈的底层实现可以使用数组或链表，无论是使用静态数组还是动态链表，都可以根据实际需要灵活分配内存，因此在空间利用上比较高效。

  3. 递归和回溯：栈在递归和回溯算法中扮演着重要的角色。递归函数调用时会将当前函数的状态（包括局部变量、返回地址等）压入栈中，当递归函数返回时，栈顶的状态会被弹出，恢复到上一层递归函数的状态。

  4. 撤销操作：栈可以用于实现撤销操作，比如文本编辑器中的撤销功能。每当执行一个操作时，将操作的状态存储在栈中，当需要撤销时，只需从栈中弹出最近的状态。

3.栈的缺点

  1. 容量限制：栈的容量是有限的，无论是基于数组还是链表实现的栈，都会受到内存大小的限制。当栈的元素个数超过容量时，会发生栈上溢（stack overflow）的错误。

  2. 无随机访问：栈的特点是只能在栈顶进行插入和删除操作，没有提供随机访问的能力。如果需要访问或修改栈中的其他元素，必须先将栈顶的元素弹出，直到达到目标位置。

  3. 不灵活：栈的特性决定了它的使用场景受到一定的限制。对于需要随机访问、频繁插入和删除的场景，栈可能不是最佳选择。

二.栈的功能

栈作为一种数据结构，具有以下几个主要的功能：

  1. 入栈：将元素添加到栈的顶部（栈顶）。新元素成为栈顶，原有的栈顶元素依次向下移动。入栈操作可以用于将数据添加到栈中。

  2. 出栈：从栈的顶部（栈顶）移除元素。被移除的元素是最后一个入栈的元素，即栈顶元素。出栈操作会改变栈的结构，并返回被移除的元素。

  3. 获取栈顶元素：获取栈顶的元素，但不对栈进行修改。这个操作可以让我们查看栈顶的元素，而不改变栈的结构。

  4. 判断栈是否为空：检查栈是否不包含任何元素。如果栈中没有元素，即栈为空，该函数返回真；否则，返回假。

  5. 判断栈是否已满：检查栈是否已达到其容量上限。对于基于数组实现的栈，如果数组已满，即栈已满，该函数返回真；否则，返回假。

三.栈的实现

1.创建栈

创建一个结构体，里面的成员是数组以及指针。（在这里，为了大家能够方便理解，用静态的顺序表来实现）

#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针，指向栈顶元素的索引
} Stack;

2.初始化栈

将栈顶的指针初始化为-1，表示此栈为空。

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

3.判断栈是否为空

判断栈是否为空。如果栈顶指针top等于-1，表示栈为空，返回1；否则，返回0。

// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1; // 栈为空时，栈顶指针为-1
}

4. 判断是否已满

判断栈是否已满。如果栈顶指针top等于数组最大索引（MAX_SIZE - 1），表示栈已满，返回1；否则，返回0。

// 判断栈是否已满
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1; // 栈满时，栈顶指针等于数组最大索引
}

5.入栈

 入栈操作。首先使用isFull函数检查栈是否已满，如果已满，则打印错误信息并返回；否则，将栈顶指针top加1，并将元素item放入栈顶位置data[top]。

// 入栈
void push(Stack* stack, int item) {
if (isFull(stack)) {
printf("Stack overflow!\n"); // 栈已满，无法入栈
return;
}
stack->data[++stack->top] = item; // 栈顶指针加1，并将元素放入栈顶
}

 6.出栈

出栈操作。首先使用isEmpty函数检查栈是否为空，如果为空，则打印错误信息并返回-1；否则，返回栈顶元素data[top]，并将栈顶指针top减1。

// 出栈
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n"); // 栈为空，无法出栈
return -1;
}
return stack->data[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}

 7.获取栈顶元素

获取栈顶元素。首先使用isEmpty函数检查栈是否为空，如果为空，则打印错误信息并返回-1；否则，返回栈顶元素data[top]，但不修改栈的结构。

/ 获取栈顶元素
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n"); // 栈为空，无栈顶元素
return -1;
}
return stack->data[stack->top]; // 返回栈顶元素，不修改栈的结构
}

8.打印栈中元素

 打印栈中的元素。首先使用isEmpty函数检查栈是否为空，如果为空，则打印提示信息；否则，使用循环从栈底到栈顶依次打印栈中的元素。

/ 打印栈中的元素（用于调试）
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}

四.栈的源码呈现

 

#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针，指向栈顶元素的索引
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1; // 栈顶指针初始化为-1，表示栈为空
}// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1; // 栈为空时，栈顶指针为-1
}// 判断栈是否已满
int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1; // 栈满时，栈顶指针等于数组最大索引
}// 入栈
void push(Stack* stack, int item) {if (isFull(stack)) {printf("Stack overflow!\n"); // 栈已满，无法入栈return;}stack->data[++stack->top] = item; // 栈顶指针加1，并将元素放入栈顶
}// 出栈
int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack underflow!\n"); // 栈为空，无法出栈return -1;}return stack->data[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}// 获取栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n"); // 栈为空，无栈顶元素return -1;}return stack->data[stack->top]; // 返回栈顶元素，不修改栈的结构
}// 打印栈中的元素（用于调试）
void printStack(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return;}printf("Stack: ");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}// 主函数用于测试栈的功能
int main() {Stack stack;initStack(&stack); // 初始化栈push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack); // 打印栈中的元素printf("Top element: %d\n", peek(&stack)); // 获取栈顶元素while (!isEmpty(&stack)) {printf("Popped element: %d\n", pop(&stack)); // 依次出栈并输出元素}return 0;
}


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

相关文章

vue生命周期

vue生命周期

Vue beforeCreate: //在实例生成之前会自动执行的函数 created: // 在实例生成之后会自动执行的函数 beforeMount://在模版渲染完成之前&#xff08;实例挂载&#xff09;执行 mounted&#xff1a; //在模版渲染完成之后&#xff08;实例挂载&#xff09;执行 beforeUpdate: /…
阅读更多...
openlayers6在uniapp中结合rendjs

openlayers6在uniapp中结合rendjs

步骤 1: 安装 OpenLayers 在你的 UniApp 项目中&#xff0c;使用 npm 或 yarn 安装 OpenLayers&#xff1a; bash复制代码 npm install ol 步骤 2: 创建地图组件 在 UniApp 中创建一个新的 Vue 组件&#xff08;例如 Map.vue&#xff09;&#xff0c;并在其中引入 OpenLaye…
阅读更多...
浅谈电能质量电网谐波

浅谈电能质量电网谐波

目录 浅谈电能质量电网谐波 1.什么是谐波？ 2.谐波的产生原因？
阅读更多...
pytorch简单神经网络模型训练

pytorch简单神经网络模型训练

目录 一、导入包 二、数据预处理 三、定义神经网络 四、训练模型和测试模型 五、程序入口 一、导入包 import torch import torch.nn as nn import torch.optim as optim # 导入优化器 from torchvision import datasets, transforms # 导入数据集和数据预处理库 from tor…
阅读更多...
软考网络工程师 第六章 第二部分 第二节 IP分片与计算

软考网络工程师 第六章 第二部分 第二节 IP分片与计算

IP定义 IP报文最大65535字节&#xff0c;而以太网MTU为1500字节。 相当于货轮能载重65535&#xff0c;而火车载重1500&#xff0c;那么必须把货轮上的货物分装给多个火车运输 例题精选解析 以太网主机发送一个IP分组&#xff0c;长度3000字节&#xff0c;头长度为标准长度&a…
阅读更多...
Content type ‘application/json；charset=UTF-8‘ not supported异常的解决过程

Content type ‘application/json；charset=UTF-8‘ not supported异常的解决过程

1.首先说明开发场景 *就是对该json格式数据传输到后台 后台实体类 import com.baomidou.mybatisplus.annotation.TableId; import com.baomidou.mybatisplus.annotation.TableName; import com.fasterxml.jackson.annotation.JsonIgnore; import lombok.Data; import org.sp…
阅读更多...
LangChain入门2 RAG详解

LangChain入门2 RAG详解

RAG概述 一个典型的RAG应用程序,它有两个主要组件&#xff1a; 索引&#xff1a;从源中获取数据并对其进行索引的管道。这通常在脱机情况下发生。检索和生成&#xff1a;在运行时接受用户查询&#xff0c;并从索引中检索相关数据&#xff0c;然后将其传递给模型。 从原始数据…
阅读更多...
python Django 的内置权限系统或自定义模型来存储更复杂的角色和权限关系

python Django 的内置权限系统或自定义模型来存储更复杂的角色和权限关系

在 Django 中，管理用户权限和角色通常涉及到使用 Django 的内置权限系统或自定义模型来存储更复杂的角色和权限关系。下面是一个基本的指南，说明如何在 Django 中为后台管理系统分配权限并将其保存在数据库中，同时结合 Vue.js 和 Element UI 作为前端框架。 后端（Django）…
阅读更多...
最新文章

Copyright @ 2022~2023