qq空间关闭申请网站,wordpress调取文章列表,微信公众平台小程序助手,网站建设流程策划栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底#xff08;因为先进后出#xff09;。栈中的数据元素遵守后进先出LIFO#xff08;Last In Firs… 栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶另一端称为栈底因为先进后出。栈中的数据元素遵守后进先出LIFOLast 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博客https://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 的结构体用于实现一个栈数据结构 STDataType这是一个类型定义它将 int 类型别名为 STDataType。这意味着在定义栈结构体时可以使用 STDataType 来表示栈中存储的数据类型为整数。 Stack 结构体 STDataType* _a这是一个指向 STDataType 类型数据的指针用于指向栈的内存空间。在栈的上下文中这个数组通常用来存储栈中的元素。_a 通常指向一个预先分配的数组该数组的大小由 _capacity 成员指定。int _top这个整数用来表示栈顶的位置。在大多数栈的实现中栈顶是一个非常重要的概念因为它指向了最后一个入栈的元素的位置。在这段代码中_top 初始化为0意味着栈顶位于数组的第一个元素在C语言中数组索引从0开始。如果使用 _top 初始化为-1则表示栈是空的因为此时没有元素入栈栈顶的下标为-1。int _capacity这个整数用来存储栈的最大容量即栈能存储的最大元素数量。在栈操作中这个值用来检查栈是否已满以避免栈溢出。 这个 Stack 结构体的定义为栈的实现提供了基础框架。通常还需要实现一些函数来操作这个栈比如 Push入栈、Pop出栈、Top获取栈顶元素、IsEmpty检查栈是否为空等。接下来我们会逐个实现。 初始化栈 #includeStack.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 StackInit(Stack* ps)这是 StackInit 函数的定义开始它接收一个指向 Stack 结构体的指针 ps 作为参数。 ps-_a NULL;这行代码将栈的数组指针 _a 初始化为 NULL。这意味着初始化时栈没有分配任何内存空间数组为空。ps-_capacity ps-_top 0;这里初始化了两个成员变量 - _capacity栈的容量这里初始化为0表示栈的最大容量为0即栈没有任何空间可以存储元素。 - _top栈顶的索引这里初始化为0表示栈顶位于数组的第一个位置。由于数组指针 _a 已经初始化为 NULL此时栈是空的。 _top 初始化的不同方式 - **初始化为-1**在一些栈的实现中_top 被初始化为-1用来表示栈为空。这种方式下数组的索引从0开始但 _top 的初始值-1意味着没有元素在栈中。当第一个元素被推入栈时_top 会增加到0表示数组的第一个元素现在包含数据。- **初始化为0**在这段代码中_top 被初始化为0这同样表示栈为空。由于 _a 是 NULL即使 _top 是0栈实际上也是空的。当第一个元素被推入栈时数组 _a 会被分配内存且 _top 保持不变直到有元素入栈。选择哪种初始化方式取决于你的栈操作的具体实现。如果你的栈操作允许在 _top 为0时推入元素那么初始化 _top 为0是合适的。如果你希望 _top 总是指向栈顶元素的下一个位置那么初始化 _top 为-1可能更合适。在这段代码中由于 _a 被初始化为 NULL栈的状态空或非空主要由 _a 的值决定。_top 的初始化值更多地是为将来元素入栈时的索引管理做准备。 这里我采取的是初始化为0也就可以简介表示实际的个数 销毁栈 // 销毁栈
void StackDestroy(Stack* ps)
{// 判断为不为空判断里面有没有数值assert(ps ps-_top);free(ps-_a);ps-_capacity ps-_top 0;
} free(ps-_a);这行代码调用 free 函数来释放栈的数组 _a 所占用的内存。这是销毁栈的关键步骤因为它避免了内存泄漏。 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博客https://blog.csdn.net/Jason_from_China/article/details/137074963注意realloc涉及一个原地扩容和异地扩容的情况所以才会出现这一行代码 ps-_a tmp; 这段代码定义了一个名为 StackPush 的函数用于向栈中添加一个新元素。 void StackPush(Stack* ps, STDataType data)函数定义开始StackPush 接收一个指向 Stack 结构体的指针 ps 和一个要入栈的数据 data。 if (ps-_capacity ps-_top)这行代码检查栈是否已满。_capacity 是栈的最大容量_top 是栈顶的索引。如果两者相等表示栈已经达到最大容量。 int newapacity ps-_capacity 0 ? 4 : 2 * ps-_capacity;如果栈已满则需要扩容。新的容量 newcapacity 是当前容量的两倍如果当前容量为0即栈是空的或尚未分配内存则新容量设置为4。 STDataType* tmp (STDataType*)realloc(ps-_a, newapacity * sizeof(STDataType));使用 realloc 函数为栈的数组 _a 分配新的内存空间。realloc 会处理原有内存块的复制并返回指向新内存块的指针。 if (tmp NULL)检查 realloc 是否成功。如果 tmp 是 NULL表示内存分配失败。 perror(StackPush:tmp:error:);如果内存分配失败使用 perror 函数输出错误信息。perror 会将参数字符串作为前缀后跟一个冒号和空格然后输出当前设定的 errno 描述的错误信息。 exit(1);如果内存分配失败调用 exit 函数以非零状态码退出程序。 ps-_capacity newapacity;如果内存分配成功更新栈的容量为新的容量。 ps-_a tmp;将栈的数组指针 _a 更新为指向新分配的内存空间。 ps-_a[ps-_top] data;将传入的数据 data 存储到栈顶位置。由于栈是顺序存储的这一步是直接通过数组索引来完成的。 ps-_top;更新栈顶索引 _top将其增加1以指向数组中的下一个位置为下一次入栈做准备。 这段代码实现了一个动态栈它可以根据需要自动扩容。当栈满时它会增加栈的容量并重新分配内存。需要注意的是realloc 的使用可能会导致原有内存块被移动到新的内存位置因此所有指向原内存块的指针都需要更新。此外realloc 失败时的错误处理是必要的以避免程序因内存分配问题而崩溃。 出栈 // 出栈
void StackPop(Stack* ps)
{// 判断为不为空判断里面有没有数值assert(ps ps-_top);ps-_top--;
} void StackPop(Stack* ps)函数定义开始StackPop 接收一个指向 Stack 结构体的指针 ps 作为参数。 assert(ps ps-_top);assert 是一个宏用于在运行时测试一个条件是否为真。如果条件为假则 assert 将产生一个断言失败通常会导致程序异常终止。在这里它用于确保传入的栈指针 ps 不是 NULL并且 ps-_top 也是非空的从而确保栈已经初始化过并且 _top 成员变量是有效的。 ps-_top--;这行代码将栈顶索引 _top 减一。由于栈是后进先出LIFO的数据结构减少 _top 的值就相当于从栈顶部移除了一个元素。在栈的顺序存储实现中通常不需要实际移动数组中的元素只需要更新栈顶的索引即可。 出栈其实就很简答只需要删除栈顶就可以 删除 获取栈顶元素 // 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps ps-_top);return ps-_a[ps-_top - 1];
} STDataType StackTop(Stack* ps)函数定义开始StackTop 接收一个指向 Stack 结构体的指针 ps 作为参数并返回栈顶的元素。 assert(ps ps-_top);assert 是一个宏用于在运行时测试一个条件是否为真。如果条件为假则 assert 将产生一个断言失败通常会导致程序异常终止。在这里它用于确保传入的栈指针 ps 不是 NULL并且 ps-_top 也是非空的从而确保栈已经初始化过并且 _top 成员变量是有效的。 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
#includestdio.h
#includeassert.h
#includestdlib.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 #includeStack.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 表示
}
