您的位置：首页 > 房产 > 建筑 > 数据结构——栈

数据结构——栈

2024/12/22 20:39:56 来源：https://blog.csdn.net/TENET123/article/details/140192722  浏览:  次   关键词：数据结构——栈

文章目录

1. 定义

2. 概念

3. 原理

函数调用栈的原理

调用栈的示例

代码示例

4. 存储结构

顺序栈

链式栈

顺序栈和链式栈的比较

5. 函数功能

6. 代码示例

1. 定义

栈 (stack) 是一种限制在表的一端进行插入和删除操作的线性表。插入和删除操作只能在栈顶（top）进行，遵循“后进先出” (LIFO, Last In First Out) 或“先进后出” (FILO, First In Last Out) 的原则。这种特性使得栈在某些场景中非常有用，如处理递归调用、表达式求值、深度优先搜索等。

特点：后进先出 (LIFO) 或先进后出 (FILO)

栈的基本特点是“后进先出”或“先进后出”。这意味着最新插入的元素最先被删除，而最早插入的元素最后被删除。栈的这种特性可以通过日常生活中的一些例子来理解：

  • 堆叠的盘子：最上面的盘子最先被拿走，而最下面的盘子最后被拿走。
  • 报纸：最上面的一期报纸最先被拿走，而最下面的一期报纸最后被拿走。
  • 电梯中的人们：最后进电梯的人最先出电梯。
  • 邮局的邮件：最新到达的邮件最先被处理。

这些例子都体现了栈的“后进先出”或“先进后出”的特性。

栈的基本操作

栈的基本操作包括：

  1. 入栈 (push)：将元素压入栈顶。
  2. 出栈 (pop)：将栈顶元素弹出。
  3. 查看栈顶元素 (peek)：查看栈顶元素但不弹出。
  4. 检查栈是否为空 (isEmpty)：判断栈是否为空。
  5. 获取栈的大小 (size)：获取栈中元素的个数。

如下图所示，栈的入栈和出栈操作分别将元素添加到栈顶和从栈顶移除。

在这个图中，元素 a0​ 最先被压入栈底，接着依次是 a1​、a2、a3 和 a4。当执行出栈操作时，最先被移除的是 a4​，然后是 a3​、a2​、a1​，最后是 a0​。

2. 概念

栈顶 (Top)

  • 定义：栈顶是允许进行插入和删除操作的一端，又称为栈尾。栈顶由一个称为栈顶指针的位置指示器来指示，它是动态变化的。
  • 作用：在栈的所有操作中，栈顶是最重要的，因为所有的插入和删除操作都在栈顶进行。

栈底 (Bottom)

  • 定义：栈底是固定不变的，不允许进行插入和删除操作的一端，又称为表头。
  • 作用：栈底是栈的起始点，标志着栈的开始。

空栈

  • 定义：不含任何元素的空表称为空栈。
  • 作用：空栈的判定是栈操作的一个重要条件，当栈为空时，不能进行出栈操作。

栈的操作

  • 入栈 (Push)：将元素压入栈顶。
  • 出栈 (Pop)：将栈顶元素弹出。
  • 栈顶元素 (Peek)：查看栈顶元素但不弹出。
  • 检查栈是否为空 (IsEmpty)：判断栈是否为空。
  • 获取栈的大小 (Size)：获取栈中元素的个数。

栈的顺序表表示

设栈 S={a1,a2,…,an}，则 a1​ 称为栈底元素，an 为栈顶元素。栈中元素按 a1,a2,…,an 的次序进栈 (Push)，出栈 (Pop) 的顺序为：an,…,a2,a1。

栈的操作示例

情况 1：初始情况下 top=−1

  1. 空栈：初始时栈为空，栈顶指针 top 指向 -1。
  2. Push A：将元素 A 入栈，栈顶指针 top 移动到 0，A 成为栈顶元素。
  3. Push B, C, D：依次将元素 B, C, D 入栈，栈顶指针 top 依次移动，最终 D 成为栈顶元素。
  4. Pop D：将栈顶元素 D 出栈，栈顶指针 top 移动到 2，C 成为新的栈顶元素。

情况 2：初始情况下 top=0

  1. 空栈：初始时栈为空，栈顶指针 top 指向 0。
  2. Push A：将元素 A 入栈，栈顶指针 top 移动到 1，A 成为栈顶元素。
  3. Push B, C, D：依次将元素 B, C, D 入栈，栈顶指针 top 依次移动，最终 D 成为栈顶元素。
  4. Pop D：将栈顶元素 D 出栈，栈顶指针 top 移动到 3，C 成为新的栈顶元素。

3. 原理

栈在计算机科学中的一个重要应用是函数调用。函数调用是程序执行过程中的基本操作之一，无论何种编程语言，函数调用都遵循一个“先进后出”的原则。这种“先进后出”机制的实现离不开栈。

函数调用栈的原理

在函数调用过程中，当前执行的函数需要调用另一个函数时，当前函数的状态（包括当前指令位置、局部变量等）会被压入栈中，然后开始执行被调用的函数。当被调用的函数执行完毕后，栈顶的状态会被弹出，恢复到之前的状态，继续执行原函数。

void funcA() {funcB();
}void funcB() {funcC();
}

调用顺序和返回顺序

在上面的例子中：

  • 调用顺序：funcA() -> funcB() -> funcC()
  • 返回顺序：funcC() -> funcB() -> funcA()

  1. 调用 funcA()：

    • 首先调用 funcA()，在执行 funcA() 时，程序遇到 funcB() 的调用，暂停 funcA() 的执行，把 funcA() 的状态压入栈中，然后转去执行 funcB()。

  2. 调用 funcB()：

    • 在 funcB() 中，同样遇到 funcC() 的调用，暂停 funcB() 的执行，把 funcB() 的状态压入栈中，然后转去执行 funcC()。

  3. 调用 funcC()：

    • 执行 funcC() 时没有进一步的调用，所以 funcC() 完成后，程序从栈中弹出 funcB() 的状态，恢复执行 funcB()。

  4. 返回 funcB()：

    • funcB() 执行完毕后，程序从栈中弹出 funcA() 的状态，恢复执行 funcA()。

  5. 返回 funcA()：

    • 最后 funcA() 执行完毕，整个调用过程结束。

调用栈的示例

在函数调用过程中，栈的变化如下：

  1. 初始情况（栈为空）：

    [空]

  2. 调用 funcA() 后：

    [funcA]

  3. 调用 funcB() 后：

    [funcA]
[funcB]

  4. 调用 funcC() 后：

    [funcA]
[funcB]
[funcC]

  5. funcC() 返回后：

    [funcA]
[funcB]

  6. funcB() 返回后：

    [funcA]

  7. funcA() 返回后（栈为空）：

    [空]

通过这个例子，我们可以直观地看到栈在函数调用过程中的作用。每次函数调用时，当前状态会被压入栈中，而函数返回时，栈顶状态会被弹出并恢复。这种机制保证了函数调用的有序进行和正确返回。

代码示例

在这个例子中，程序从 main 函数开始，调用 funcA，然后 funcA 调用 funcB，接着 funcB 调用 funcC。每次函数调用时，当前函数的状态都会被压入栈中，当调用的函数执行完毕后，程序会返回到上一个函数继续执行。

#include <stdio.h>// 示例函数A
void funcA() {printf("Inside funcA\n");funcB();
}// 示例函数B
void funcB() {printf("Inside funcB\n");funcC();
}// 示例函数C
void funcC() {printf("Inside funcC\n");
}int main() {funcA();  // 从这里开始调用链return 0;
}

 

4. 存储结构

栈的存储结构可以分为两种：顺序栈和链式栈。它们分别利用数组和链表来实现栈的功能。

顺序栈

顺序栈是使用数组来实现的栈结构。其特点是利用数组的顺序存储方式，直接通过下标访问数组中的元素。

顺序栈的基本操作

  1. 初始化栈
  2. 判断栈是否为空
  3. 判断栈是否满
  4. 入栈操作（push）
  5. 出栈操作（pop）
  6. 获取栈顶元素

链式栈

链式栈是使用链表来实现的栈结构。其特点是利用链表的链式存储方式，不需要预分配存储空间，能灵活地进行内存管理。

链式栈的基本操作

  1. 初始化栈
  2. 判断栈是否为空
  3. 入栈操作（push）
  4. 出栈操作（pop）
  5. 获取栈顶元素

顺序栈和链式栈的比较

顺序栈的优缺点

优点：

  • 内存利用率高，存取元素速度快。
  • 支持随机访问，通过下标可以直接访问任意元素。

缺点：

  • 需要预先分配固定大小的数组，可能会导致内存浪费或不够用。
  • 入栈和出栈操作可能需要移动大量元素，效率较低。

链式栈的优缺点

优点：

  • 不需要预先分配存储空间，可以根据需要动态分配内存。
  • 插入和删除操作不需要移动元素，效率较高。

缺点：

  • 由于每个节点需要额外存储指针，会占用更多的内存空间。
  • 访问速度较慢，不能随机访问，只能顺序访问。

5. 函数功能

栈是一种后进先出（LIFO，Last In First Out）的数据结构。本节将基于动态数组实现一个栈，实现以下函数：

  1. 初始化栈
  2. 返回栈内元素个数
  3. 添加新元素（压栈）
  4. 栈顶元素出栈并返回
  5. 释放栈内存

初始化栈

void initStack(Stack *stack, size_t capacity)
{stack->data = (int *)malloc(capacity * sizeof(int)); // 分配初始内存stack->size = 0;                                     // 初始化栈内元素个数为0stack->capacity = capacity;                          // 设置栈的初始容量
}

返回栈内元素个数

size_t getSize(const Stack *stack)
{return stack->size; // 返回栈内的元素个数
}

添加新元素（压栈）

void push(Stack *stack, int element)
{if (stack->size >= stack->capacity) // 如果栈已满，扩展栈容量{size_t newCapacity = stack->capacity * 2;stack->data = (int *)realloc(stack->data, newCapacity * sizeof(int));stack->capacity = newCapacity;}stack->data[stack->size++] = element; // 将新元素压入栈顶，并更新栈内元素个数
}

栈顶元素出栈并返回

int pop(Stack *stack)
{if (stack->size == 0){printf("栈为空，无法出栈\n");exit(1); // 栈为空，无法出栈}return stack->data[--stack->size]; // 栈顶元素出栈，并更新栈内元素个数
}

释放栈内存

void destroyStack(Stack *stack)
{free(stack->data); // 释放栈内存stack->size = 0;   // 重置栈内元素个数stack->capacity = 0; // 重置栈容量
}

6. 代码示例

以下是一个完整代码，实现了一个基于动态数组的栈，包含初始化、添加新元素、弹出栈顶元素、获取栈内元素个数和释放栈内存的基本操作。

#include <stdio.h>
#include <stdlib.h>// 栈结构
typedef struct
{int *data;       // 动态数组存储栈元素size_t size;     // 栈内元素个数size_t capacity; // 动态数组的容量
} Stack;// 初始化栈
void initStack(Stack *stack, size_t capacity)
{stack->data = (int *)malloc(capacity * sizeof(int)); // 分配初始容量的内存stack->size = 0;                                     // 初始元素个数为0stack->capacity = capacity;                          // 设置容量
}// 返回栈内元素个数
size_t getSize(const Stack *stack)
{return stack->size;
}// 添加新元素（压栈）
void push(Stack *stack, int element)
{if (stack->size == stack->capacity) // 如果栈已满，需要扩展容量{stack->capacity *= 2; // 容量翻倍stack->data = (int *)realloc(stack->data, stack->capacity * sizeof(int)); // 重新分配内存}stack->data[stack->size] = element; // 将元素压入栈顶stack->size++;                      // 更新元素个数
}// 栈顶元素出栈并返回
int pop(Stack *stack)
{if (stack->size == 0) // 如果栈为空{return -1; // 返回无效值}stack->size--;                 // 更新元素个数return stack->data[stack->size]; // 返回栈顶元素
}// 释放栈内存
void destroyStack(Stack *stack)
{free(stack->data); // 释放动态数组内存stack->data = NULL;stack->size = 0;stack->capacity = 0;
}int main()
{Stack myStack; // 声明栈// 初始化栈initStack(&myStack, 2);printf("初始化栈,初始容量为2\n");// 向栈压入元素push(&myStack, 1);push(&myStack, 2);push(&myStack, 3); // 添加一个元素以触发容量扩展printf("栈内元素个数:%zu\n", getSize(&myStack)); // 打印栈内元素个数// 弹出栈顶元素printf("弹出栈顶元素:%d\n", pop(&myStack));printf("弹出栈顶元素:%d\n", pop(&myStack));printf("弹出栈顶元素:%d\n", pop(&myStack));// 释放栈内存destroyStack(&myStack);printf("栈内存已释放\n");return 0;
}

  1. 栈结构定义

    • int *data: 动态数组，用于存储栈的元素。
    • size_t size: 当前栈内元素的个数。
    • size_t capacity: 动态数组的容量。

  2. 初始化栈

    • initStack(Stack *stack, size_t capacity): 分配初始容量的内存，并将栈的元素个数和容量初始化。

  3. 返回栈内元素个数

    • getSize(const Stack *stack): 返回当前栈内的元素个数。

  4. 添加新元素（压栈）

    • push(Stack *stack, int element): 将新元素压入栈顶，如果栈已满，则扩展栈的容量（容量翻倍）。

  5. 栈顶元素出栈并返回

    • pop(Stack *stack): 将栈顶元素弹出并返回，如果栈为空，则返回-1表示无效值。

  6. 释放栈内存

    • destroyStack(Stack *stack): 释放动态数组的内存，并将栈的元素个数和容量重置。

在 main 函数中，进行了以下操作：

  • 初始化栈并设置初始容量为2。
  • 向栈中压入元素，并打印栈内元素的个数。
  • 从栈中弹出元素，并打印出栈元素。
  • 释放栈的内存。

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

记录踩过的坑-金蝶云苍穹平台-许可、用户、角色和权限（慢慢更新） 2024-2025-1 20241312 《计算机基础与程序设计》第十三周学习总结 electron-vite【实战系列教程】 数据结构-链表-代码 请说下你对html的发展历史的了解及认知 在Less中,命名空间和访问器有什么作用？

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989