当前位置：首页 > news >正文

线性表之数组与栈详解

news 来源：原创 2025/8/3 22:58:47

线性表之数组与栈详解

前言
一、数组（Array）
- 1.1 数组的基本概念
- 1.2 数组的实现与操作
- 1.3 数组的应用场景
- 1.4 数组的优缺点
二、栈（Stack）
- 2.1 栈的基本概念
- 2.2 栈的实现方式
- 2.3 栈的应用场景
- 2.4 栈的优缺点
三、数组与栈的对比
总结

前言

线性表是一种基础且重要的数据结构，它是由相同数据类型的有限个数据元素组成的序列。数组和栈作为线性表的典型代表，在数据存储、算法设计以及程序运行中发挥着关键作用。本文我将深入探讨数组和栈的原理、实现方式、操作特点以及实际应用场景，并结合代码示例，帮助你全面掌握这两种重要的数据结构。

一、数组（Array）

1.1 数组的基本概念

数组是一种线性表，它将相同类型的元素按顺序存储在一段连续的内存空间中。通过数组的下标（索引），可以快速访问数组中的元素。例如，对于一个包含n个元素的数组arr，其元素可以通过arr[0]到arr[n - 1]的方式进行访问，其中0是数组的起始下标，n - 1是最后一个元素的下标。

数组的特点如下：

随机访问高效：由于元素在内存中连续存储，通过下标计算元素的内存地址非常迅速，随机访问元素的时间复杂度为 $O (1)$ 。
固定大小：在创建数组时，通常需要指定数组的大小，一旦创建完成，其大小一般不能动态改变（在某些编程语言中通过特殊方式可实现动态扩容，但本质上是重新分配更大的连续内存并复制元素）。
内存连续：这种连续的存储方式使得数组在遍历和进行批量数据操作时效率较高。

1.2 数组的实现与操作

以 C++ 语言为例，数组的声明和基本操作如下：

#include <iostream>
using namespace std;// 声明并初始化数组
int main() {int arr[5] = {1, 2, 3, 4, 5};  // 声明一个包含5个整数的数组并初始化// 访问数组元素cout << "访问数组第一个元素：" << arr[0] << endl;// 修改数组元素arr[2] = 10;cout << "修改后的数组第三个元素：" << arr[2] << endl;// 遍历数组cout << "遍历数组：";for (int i = 0; i < 5; ++i) {cout << arr[i] << " ";}cout << endl;return 0;
}

在 Python 语言中，虽然没有传统意义上的固定大小数组，但可以使用列表（list）来模拟数组的功能，并且列表具有动态扩容的特性：

# 声明并初始化列表（类似数组）
arr = [1, 2, 3, 4, 5]
# 访问列表元素
print("访问列表第一个元素：", arr[0])
# 修改列表元素
arr[2] = 10
print("修改后的列表第三个元素：", arr[2])
# 遍历列表
print("遍历列表：", end="")
for num in arr:print(num, end=" ")
print()

1.3 数组的应用场景

数据存储：用于存储大量同类型的数据，如学生成绩表、员工信息列表等。在数据库系统中，也会使用数组来存储和管理数据页。
算法实现：许多算法依赖数组作为基础数据结构，例如排序算法（如冒泡排序、快速排序等）、查找算法（如二分查找）等。在这些算法中，数组的随机访问特性使得元素的比较和交换操作更加高效。
矩阵运算：在数学和图形处理领域，二维数组常用于表示矩阵，方便进行矩阵的加法、乘法等运算。

1.4 数组的优缺点

优点：
- 随机访问速度快，能快速定位和获取元素。
- 内存连续，遍历效率高，适合批量数据处理。
缺点：
- 大小固定，插入和删除元素时，可能需要移动大量后续元素，时间复杂度较高（平均时间复杂度为 $O (n)$ ）。
- 动态扩容需要重新分配内存并复制数据，会带来额外的性能开销。

二、栈（Stack）

2.1 栈的基本概念

栈是一种特殊的线性表，它遵循 后进先出（Last In First Out，LIFO）的原则。栈只有一端是开口的，这一端称为栈顶，数据的插入（入栈，push操作）和删除（出栈，pop操作）都在栈顶进行。就像一摞盘子，最后放上去的盘子会最先被拿走。

栈的主要操作包括：

入栈（Push）：将元素添加到栈顶。
出栈（Pop）：移除并返回栈顶元素。
查看栈顶元素（Peek）：返回栈顶元素但不移除它。
判断栈是否为空（Is Empty）：检查栈中是否没有元素。

2.2 栈的实现方式

栈可以使用数组或链表来实现，以下分别展示使用 C++ 实现的数组栈和链表栈：

数组实现栈：

#include <iostream>
using namespace std;const int MAX_SIZE = 100;class ArrayStack {
private:int top;int arr[MAX_SIZE];
public:ArrayStack() {top = -1;}// 入栈操作void push(int value) {if (top == MAX_SIZE - 1) {cout << "栈已满，无法入栈" << endl;return;}arr[++top] = value;}// 出栈操作int pop() {if (top == -1) {cout << "栈为空，无法出栈" << endl;return -1;}return arr[top--];}// 查看栈顶元素int peek() {if (top == -1) {cout << "栈为空" << endl;return -1;}return arr[top];}// 判断栈是否为空bool isEmpty() {return top == -1;}
};

链表实现栈：

#include <iostream>
using namespace std;// 链表节点结构
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};class ListStack {
private:ListNode* top;
public:ListStack() {top = NULL;}// 入栈操作void push(int value) {ListNode* newNode = new ListNode(value);newNode->next = top;top = newNode;}// 出栈操作int pop() {if (top == NULL) {cout << "栈为空，无法出栈" << endl;return -1;}int val = top->val;ListNode* temp = top;top = top->next;delete temp;return val;}// 查看栈顶元素int peek() {if (top == NULL) {cout << "栈为空" << endl;return -1;}return top->val;}// 判断栈是否为空bool isEmpty() {return top == NULL;}
};

2.3 栈的应用场景

函数调用栈：在程序运行时，函数的调用和返回依赖栈来管理。当一个函数被调用时，其相关信息（如参数、局部变量等）会被压入栈中；函数执行完毕返回时，这些信息会从栈中弹出。
表达式求值：在计算算术表达式（如中缀表达式、后缀表达式）时，栈可以用来存储操作数和操作符，帮助完成表达式的求值过程。例如，通过栈可以将中缀表达式转换为后缀表达式，并计算后缀表达式的值。
括号匹配：检查代码中的括号是否匹配是栈的一个常见应用。遍历代码中的括号，遇到左括号时将其入栈，遇到右括号时检查栈顶元素是否为对应的左括号，若是则出栈，否则说明括号不匹配。

2.4 栈的优缺点

优点：
- 操作简单，遵循后进先出原则，逻辑清晰。
- 在实现某些特定功能（如函数调用、表达式求值）时，效率高且代码简洁。
缺点：
- 只能访问栈顶元素，无法随机访问栈内其他元素。
- 使用数组实现时，若栈的大小固定，可能会出现栈满的情况；使用链表实现时，会有额外的指针空间开销。

三、数组与栈的对比

数据结构	访问方式	插入 / 删除操作	内存特性	典型应用
数组	随机访问（通过下标）	插入 / 删除平均时间复杂度为 $O (n)$ ，可能需移动大量元素	内存连续，大小固定（或需动态扩容）	数据存储、算法实现、矩阵运算
栈	只能访问栈顶元素	入栈和出栈操作时间复杂度为 $O (1)$	可使用数组或链表实现，数组实现可能有栈满问题	函数调用、表达式求值、括号匹配

总结

数组和栈作为线性表的重要组成部分，各自具有独特的特性和应用场景。数组凭借其随机访问高效、内存连续的特点，在数据存储和算法基础操作中发挥着重要作用；栈遵循后进先出原则，在函数调用管理、表达式处理等方面表现出色。了解数组和栈的原理、实现方式以及应用场景，有助于我们在实际编程中根据具体需求选择合适的数据结构，优化程序性能，解决各种复杂的问题。下一篇博客我将详细讲述线性表----队列的知识, 不容错过哦!

That’s all, thanks for reading!
创作不易，点赞鼓励；
知识无价，收藏备用；
持续精彩，关注不错过！

线性表之数组与栈详解

前言

一、数组（Array）

1.1 数组的基本概念

1.2 数组的实现与操作

1.3 数组的应用场景

1.4 数组的优缺点

二、栈（Stack）

2.1 栈的基本概念

2.2 栈的实现方式

2.3 栈的应用场景

2.4 栈的优缺点

三、数组与栈的对比

总结

相关文章：