栈的讲解

  • 开发
  • 11

栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底（因为先进后出）。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶

后进先出，后进去的先出来（就像羽毛球桶）

图片实例（这里是我画了一个图，找了两个图）

实现栈的方式

栈的实现可以是顺序表，也可以是链表

入数据 1 2 3 4

出数据 4 3 2 1

顺序表（数组）实现

链表实现的话最好是双链表

当然单链表也是可以的

不过一般情况下我们都是采取单链表的方式进行实现

因为

C语言中栈的实现通常采用顺序表的方式而不是链表的方式，原因包括但不限于以下几点：

1. **简单性**：顺序表的实现相对简单，它是基于数组的，而数组是C语言的基本数据结构。链表的实现需要额外的指针操作，对于栈的基本操作（入栈和出栈）来说，这种复杂性通常是不必要的。

2. **性能**：顺序表（数组）在内存中是连续存储的，这意味着存取速度快，CPU缓存的效率也更高。而链表由于其非连续性，访问速度相对较慢，且不利于缓存优化。

3. **空间效率**：顺序表可以预先分配固定大小的内存空间，而链表则需要为每个元素分配独立的内存空间，并且每个节点都需要额外的指针空间。在栈的应用场景中，通常可以预估栈的最大深度，因此顺序表可以更有效地利用内存。

4. **栈特性**：栈是后进先出（LIFO）的数据结构，其操作主要集中在栈顶进行。顺序表可以通过索引直接访问栈顶元素，而链表则需要从头开始遍历，直到找到最后一个元素。

5. **边界检查**：顺序表可以方便地进行上溢检查，只需比较栈的当前元素数量和预分配的大小即可。链表则需要维护一个额外的计数器来记录元素数量，以进行上溢检查。

6. **缓存局部性**：由于顺序表的数据存储是连续的，它具有较好的时间局部性和空间局部性，这使得它更适合现代计算机系统的缓存机制。

7. **编译器优化**：现代编译器对数组和循环有很好的优化，可以生成高效的代码。而链表的优化则更为复杂，且效果可能不如顺序表。

8. **编程习惯**：C语言程序员通常习惯于使用数组来实现栈，因为数组在C语言中使用非常普遍，且容易理解。

然而，这并不意味着链表不能用于实现栈。在一些特定场景下，链表实现的栈也有其优势，例如当栈的大小频繁变化或者对内存的使用有更严格的要求时。链表可以根据需要动态分配内存，而不需要像顺序表那样预先分配一块较大的内存空间。

选择顺序表还是链表来实现栈，最终取决于具体的应用场景和性能要求。

存在CPU缓存的问题 所以数组其实还是比较好用的

计算机的存储体系-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/Jason_from_China/article/details/138589959

栈的实现

 创建文件

创建栈的结构

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a; // 首元素的地址
	int _top;		// 栈顶，初始化为0，也就是等同于size，初始化为-1，等同于下标
	int _capacity;  // 容量 
}Stack;

这段代码定义了一个名为 Stack 的结构体，用于实现一个栈数据结构：

  1. STDataType：这是一个类型定义，它将 int 类型别名为 STDataType。这意味着在定义栈结构体时，可以使用 STDataType 来表示栈中存储的数据类型为整数。

  2. Stack 结构体：

    • STDataType* _a：这是一个指向 STDataType 类型数据的指针，用于指向栈的内存空间。在栈的上下文中，这个数组通常用来存储栈中的元素。_a 通常指向一个预先分配的数组，该数组的大小由 _capacity 成员指定。
    • int _top：这个整数用来表示栈顶的位置。在大多数栈的实现中，栈顶是一个非常重要的概念，因为它指向了最后一个入栈的元素的位置。在这段代码中，_top 初始化为0，意味着栈顶位于数组的第一个元素（在C语言中数组索引从0开始）。如果使用 _top 初始化为-1，则表示栈是空的，因为此时没有元素入栈，栈顶的下标为-1。
    • int _capacity：这个整数用来存储栈的最大容量，即栈能存储的最大元素数量。在栈操作中，这个值用来检查栈是否已满，以避免栈溢出。

这个 Stack 结构体的定义为栈的实现提供了基础框架。通常，还需要实现一些函数来操作这个栈，比如 Push（入栈）、Pop（出栈）、Top（获取栈顶元素）、IsEmpty（检查栈是否为空）等。接下来我们会逐个实现。

初始化栈

#include"Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{
	ps->_a = NULL;
	
	// 这里栈顶初始化为-1和初始化为0是不一样的
	//    0 0 0 0 0 0 0 0 数组
	// -1 0 0 0 0 0 0 0 0 初始化为-1
	//    0 0 0 0 0 0 0 0 初始化为0
    // 初始化为0，也就是等同于size，初始化为-1，等同于下标
	ps->_capacity = ps->_top = 0;
}

代码解释

  1. `void StackInit(Stack* ps)`：这是 `StackInit` 函数的定义开始，它接收一个指向 `Stack` 结构体的指针 `ps` 作为参数。
  2.  `ps->_a = NULL;`：这行代码将栈的数组指针 `_a` 初始化为 `NULL`。这意味着初始化时栈没有分配任何内存空间，数组为空。
  3. `ps->_capacity = ps->_top = 0;`：这里初始化了两个成员变量：
  4.    - `_capacity`：栈的容量，这里初始化为0，表示栈的最大容量为0，即栈没有任何空间可以存储元素。
  5.  - `_top`：栈顶的索引，这里初始化为0，表示栈顶位于数组的第一个位置。由于数组指针 `_a` 已经初始化为 `NULL`，此时栈是空的。

_top 初始化的不同方式：

  1. - **初始化为-1**：在一些栈的实现中，`_top` 被初始化为-1，用来表示栈为空。这种方式下，数组的索引从0开始，但 `_top` 的初始值-1意味着没有元素在栈中。当第一个元素被推入栈时，`_top` 会增加到0，表示数组的第一个元素现在包含数据。
  2. - **初始化为0**：在这段代码中，`_top` 被初始化为0，这同样表示栈为空。由于 `_a` 是 `NULL`，即使 `_top` 是0，栈实际上也是空的。当第一个元素被推入栈时，数组 `_a` 会被分配内存，且 `_top` 保持不变，直到有元素入栈。
  3. 选择哪种初始化方式取决于你的栈操作的具体实现。如果你的栈操作允许在 `_top` 为0时推入元素，那么初始化 `_top` 为0是合适的。如果你希望 `_top` 总是指向栈顶元素的下一个位置，那么初始化 `_top` 为-1可能更合适。
  4. 在这段代码中，由于 `_a` 被初始化为 `NULL`，栈的状态（空或非空）主要由 `_a` 的值决定。
  5. `_top` 的初始化值更多地是为将来元素入栈时的索引管理做准备。

这里我采取的是初始化为0，也就可以简介表示实际的个数

销毁栈

// 销毁栈 
void StackDestroy(Stack* ps)
{
	// 判断为不为空，判断里面有没有数值
	assert(ps && ps->_top);
	free(ps->_a);
	ps->_capacity = ps->_top = 0;
}

  1. free(ps->_a);：这行代码调用 free 函数来释放栈的数组 _a 所占用的内存。这是销毁栈的关键步骤，因为它避免了内存泄漏。

  2. ps->_capacity = ps->_top = 0;：在释放了栈的内存之后，将 _capacity 和 _top 成员变量重置为0。_capacity 表示栈的容量，重置为0意味着栈不再具有存储任何元素的能力。_top 表示栈顶的位置，重置为0可以表示栈现在是空的（取决于你的栈实现中 _top 的使用方式）。

入栈

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	//首先判断容量是多少，然后进行扩容
	if (ps->_capacity == ps->_top)
	{
		//扩容
		int newapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("StackPush:tmp:error:");
			exit(1);
		}
		//改变容量大小，指向新空间的头第一个元素位置的地址
		ps->_capacity = newapacity;
		ps->_a = tmp;
	}
	//插入数值
	ps->_a[ps->_top] = data;
	ps->_top++;
}

C语言-realloc函数的使用-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/Jason_from_China/article/details/137074963注意，realloc涉及一个原地扩容和异地扩容的情况，所以才会出现这一行代码

ps->_a = tmp;

这段代码定义了一个名为 StackPush 的函数，用于向栈中添加一个新元素。

  1. void StackPush(Stack* ps, STDataType data)：函数定义开始，StackPush 接收一个指向 Stack 结构体的指针 ps 和一个要入栈的数据 data。

  2. if (ps->_capacity == ps->_top)：这行代码检查栈是否已满。_capacity 是栈的最大容量，_top 是栈顶的索引。如果两者相等，表示栈已经达到最大容量。

  3. int newapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;：如果栈已满，则需要扩容。新的容量 newcapacity 是当前容量的两倍，如果当前容量为0（即栈是空的或尚未分配内存），则新容量设置为4。

  4. STDataType* tmp = (STDataType*)realloc(ps->_a, newapacity * sizeof(STDataType));：使用 realloc 函数为栈的数组 _a 分配新的内存空间。realloc 会处理原有内存块的复制，并返回指向新内存块的指针。

  5. if (tmp == NULL)：检查 realloc 是否成功。如果 tmp 是 NULL，表示内存分配失败。

  6. perror("StackPush:tmp:error:");：如果内存分配失败，使用 perror 函数输出错误信息。perror 会将参数字符串作为前缀，后跟一个冒号和空格，然后输出当前设定的 errno 描述的错误信息。

  7. exit(1);：如果内存分配失败，调用 exit 函数以非零状态码退出程序。

  8. ps->_capacity = newapacity;：如果内存分配成功，更新栈的容量为新的容量。

  9. ps->_a = tmp;：将栈的数组指针 _a 更新为指向新分配的内存空间。

  10. ps->_a[ps->_top] = data;：将传入的数据 data 存储到栈顶位置。由于栈是顺序存储的，这一步是直接通过数组索引来完成的。

  11. ps->_top++;：更新栈顶索引 _top，将其增加1，以指向数组中的下一个位置，为下一次入栈做准备。

这段代码实现了一个动态栈，它可以根据需要自动扩容。当栈满时，它会增加栈的容量并重新分配内存。需要注意的是，realloc 的使用可能会导致原有内存块被移动到新的内存位置，因此所有指向原内存块的指针都需要更新。此外，realloc 失败时的错误处理是必要的，以避免程序因内存分配问题而崩溃。

出栈

// 出栈 
void StackPop(Stack* ps)
{
	// 判断为不为空，判断里面有没有数值
	assert(ps && ps->_top);
	ps->_top--;
}

  1. void StackPop(Stack* ps)：函数定义开始，StackPop 接收一个指向 Stack 结构体的指针 ps 作为参数。

  2. assert(ps && ps->_top);：assert 是一个宏，用于在运行时测试一个条件是否为真。如果条件为假，则 assert 将产生一个断言失败，通常会导致程序异常终止。在这里，它用于确保传入的栈指针 ps 不是 NULL，并且 ps->_top 也是非空的，从而确保栈已经初始化过并且 _top 成员变量是有效的。

  3. ps->_top--;：这行代码将栈顶索引 _top 减一。由于栈是后进先出（LIFO）的数据结构，减少 _top 的值就相当于从栈顶部移除了一个元素。在栈的顺序存储实现中，通常不需要实际移动数组中的元素，只需要更新栈顶的索引即可。

出栈其实就很简答，只需要删除栈顶就可以

删除

获取栈顶元素 

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_a[ps->_top - 1];
}

  1. STDataType StackTop(Stack* ps)：函数定义开始，StackTop 接收一个指向 Stack 结构体的指针 ps 作为参数，并返回栈顶的元素。

  2. assert(ps && ps->_top);：assert 是一个宏，用于在运行时测试一个条件是否为真。如果条件为假，则 assert 将产生一个断言失败，通常会导致程序异常终止。在这里，它用于确保传入的栈指针 ps 不是 NULL，并且 ps->_top 也是非空的，从而确保栈已经初始化过并且 _top 成员变量是有效的。

  3. return ps->_a[ps->_top - 1];：这行代码返回栈顶元素的值。由于栈是后进先出（LIFO）的数据结构，栈顶元素就是数组 _a 中索引为 _top - 1 的元素。这里假设 _top 初始化为0并且数组索引从0开始，所以栈顶元素的索引是 _top - 1。

获取栈中有效元素个数 

int StackSize(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_top - 1;
}

检测栈是否为空，如果为空返回非零结果(1)，如果不为空返回0 

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
	// 所以，ps->_top == 0 这个表达式的作用是比较栈顶位置 ps->_top 是否等于 0。
	// 如果相等，说明栈为空，表达式结果为 true（在C语言中用 1 表示）；
	// 如果不相等，说明栈不为空，表达式结果为 false（在C语言中用 0 表示）
}

栈代码的总结

Stack.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a; // 首元素的地址
	int _top;		// 栈顶，初始化为0，也就是等同于size，初始化为-1，等同于下标
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);

Stack.c

#include"Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{
	ps->_a = NULL;
	
	// 这里栈顶初始化为-1和初始化为0是不一样的
	//    0 0 0 0 0 0 0 0 数组
	// -1 0 0 0 0 0 0 0 0 初始化为-1
	//    0 0 0 0 0 0 0 0 初始化为0
    // 初始化为0，也就是等同于size，初始化为-1，等同于下标
	ps->_capacity = ps->_top = 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	// 判断为不为空，判断里面有没有数值
	assert(ps && ps->_top);
	free(ps->_a);
	ps->_capacity = ps->_top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	//首先判断容量是多少，然后进行扩容
	if (ps->_capacity == ps->_top)
	{
		//扩容
		int newapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("StackPush:tmp:error:");
			exit(1);
		}
		//改变容量大小，指向新空间的头第一个元素位置的地址
		ps->_capacity = newapacity;
		ps->_a = tmp;
	}
	//插入数值
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	// 判断为不为空，判断里面有没有数值
	assert(ps && ps->_top);
	ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_top - 1;
}
// 检测栈是否为空，如果为空返回非零结果(1)，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
	// 所以，ps->_top == 0 这个表达式的作用是比较栈顶位置 ps->_top 是否等于 0。
	// 如果相等，说明栈为空，表达式结果为 true（在C语言中用 1 表示）；
	// 如果不相等，说明栈不为空，表达式结果为 false（在C语言中用 0 表示）
}

阅读全部

相关推荐

  2. jvm中堆与栈的区别详细讲解

    2024-05-13 08:10:05       17 阅读

  8. [Algorithm][栈][删除字符串中的所有相邻重复项][比较含退格的字符串][基本计算器Ⅱ][字符串解码][验证栈序列]详细讲解

    2024-05-13 08:10:05       15 阅读

最近更新

  1. tensorflow学习笔记(二)

    2024-05-13 08:10:05       0 阅读

  3. Typescript【网址取ID传入后端API】

    2024-05-13 08:10:05       0 阅读

  4. mongodb-数据备份和恢复

    2024-05-13 08:10:05       0 阅读

  7. 64、基于去噪卷积神经网络的彩色图像去噪(matlab)

    2024-05-13 08:10:05       0 阅读

  10. 《C++20设计模式》中单例模式

    2024-05-13 08:10:05       1 阅读

  13. 数字孪生技术在智能家居中的应用

    2024-05-13 08:10:05       1 阅读

  14. 单例模式的多种实现方式及其在框架中的使用

    2024-05-13 08:10:05       1 阅读

  17. 一、Prometheus和Grafana搭建

    2024-05-13 08:10:05       1 阅读

热门阅读

  1. Cpython 的使用

    2024-05-13 08:10:05       15 阅读

  5. Vue3实战笔记（06）--- Axios 基本用法

    2024-05-13 08:10:05       16 阅读

  6. iOS ------ MRC

    2024-05-13 08:10:05       9 阅读

  7. axios的安装和引入

    2024-05-13 08:10:05       6 阅读

  9. AI学习指南概率论篇-期望和方差

    2024-05-13 08:10:05       14 阅读

  10. MPLS技术基础

    2024-05-13 08:10:05       10 阅读

  14. Gone框架介绍16 - 自动生成Priest

    2024-05-13 08:10:05       15 阅读

  15. 39-1 Web应用防火墙 - WAF应用程序层绕过

    2024-05-13 08:10:05       11 阅读
  18. PHP笔记

    PHP笔记

    2024-05-13 08:10:05      13 阅读

  21. 什么事防抖和节流，有什么区别，如何实现

    2024-05-13 08:10:05       9 阅读

  30. 并行执行参数的应用技巧——《OceanBase 并行执行》系列 5

    2024-05-13 08:10:05       14 阅读