📝栈的概念及结构
栈的概念:
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈是一种限定只允许在一端进行插入和删除操作的线性数据结构。
栈的主要特点:
-
先进后出(LIFO, Last In First Out)。新添加的元素都放在栈顶,取出元素时也是从栈顶取出。
-
只允许在一端(栈顶)进行插入和删除操作。插入操作称为入栈,删除操作称为出栈。
-
栈内元素的访问只能是顺序访问,不能随机访问。
-
通常使用数组或链表来实现栈。
栈的基本操作:
- push(item): 将元素添加到栈顶。
- pop(): 弹出栈顶元素,同时删除该元素。
- peek(): 返回栈顶元素,但不删除。
- isEmpty(): 检查栈是否为空。
- size(): 返回栈中元素的个数。
栈的结构:
使用数组实现栈时,维护一个top指针指向栈顶元素的下一个位置。入栈时将元素添加到数组top位置,并将top加1;出栈时从top位置取元素,并将top减1。
使用链表实现栈时,链表的头结点指向栈顶元素。入栈添加新节点到头结点后面,出栈删除头结点。
所以栈具有后进先出的特性,是一种限定只允许在一端插入和删除的线性数据结构。
🌉栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。
使用数组实现栈确实具有一些优点：
- 内存连续性：数组在内存中是连续存储的，这使得对数组的访问速度相对较快，因为它允许缓存友好的访问模式。
-
尾部操作高效：数组在尾部插入或删除元素的时间复杂度为
O(1)，这使得栈的 push 和 pop 操作效率很高。
但是，使用数组实现栈也有一些限制：
4. 固定大小：数组的大小一旦确定，就不能动态扩展，如果栈需要存储的元素数量超过了数组的大小，就会导致栈溢出。
5. 动态调整的开销：当栈的大小超出数组容量时，需要重新分配更大的数组并将原始数据复制到新数组中，这会引入一定的开销。
相比，链表实现栈的优点是：
- 动态大小：链表可以根据需要动态扩展，不受固定大小的限制。
- 插入和删除操作的效率：在链表中，插入和删除操作的时间复杂度为 O(1)，不会像数组那样需要重新分配和复制数据。
但链表实现也有其缺点：
- 空间开销：链表中的每个节点都需要额外的指针来指向下一个节点，这会增加存储开销。
- 缓存不友好：由于节点在内存中不一定是连续存储的，可能会导致缓存未命中，从而降低访问速度。
因此，选择使用数组或链表实现栈取决于具体的需求和性能要求。如果需要高效的尾部操作和内存连续性，则数组实现可能更合适；而如果需要动态大小和高效的插入/删除操作，则链表实现可能更合适。
🌠栈的接口
本文将将使用动态链表实现栈：
StackCode.h
# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//方便修改
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top;//栈顶
int _capacity;//容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测栈是否有空，如果为空返true，如果不为空，返回false；
bool StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);
🌉初始化栈
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);//assert(ps)检查ps指针是否合法,防止空指针问题。
ps->_a = NULL;//栈初始化时还未分配数组空间。
ps->_capacity = ps->_top = 0;
}
注意：
将_capacity和_top成员都设置为0。_capacity表示栈的总容量,初始化时为0表示还未分配空间。_top表示栈顶元素的下一个位置,作为栈的有效元素计数器。初始化时为0表示栈为空。
🌠入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
//满了，需要扩容
if (ps->_top == ps->_capacity)//判断栈是否满了(ps->_top == ps->_capacity),如果满了需要扩容:
{//如果_capacity为0,新容量为4,否则新容量为原容量的2倍
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));//使用realloc重新分配数组空间
if (NULL == temp)
{
perror("realloc temp");//实际分配失败会打印错误并返回
return;
}
ps->_a = temp;//扩容成功后,更新_a指针和_capacity
ps->_capacity = newcapacity;
}
//将元素x赋值到栈顶位置ps->_a[ps->_top]
ps->_a[ps->_top] = x;
ps->_top++;
}
🌉出栈
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->_top--;
}
修改_top指针,就可以模拟出栈操作了。元素本身不做删除,只是修改指针来"移除"顶部元素。
🌠获取栈顶元素
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
由于栈使用数组实现,元素位置从0开始编号，栈顶指针_top指向当前栈顶元素的下一个位置，所以实际栈顶元素的位置是_top - 1
🌉获取栈中有效元素个数
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
栈使用数组实现,元素从0开始插入，_top指针指向当前最后一个元素的下一个位置，所以_top值就代表当前栈中元素的个数
🌉检测栈是否为空
//检测栈是否为空，如果为空返回true，结果不为空false
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->_top == 0)
return true;
else
return false;
}
🌉销毁栈
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
🌉Stack.c文件：
# define _CRT_SECURE_NO_WARNINGS 1
#include "StackCode.h"
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
//满了，需要扩容
if (ps->_top == ps->_capacity)
{
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
if (NULL == temp)
{
perror("realloc temp");
return;
}
ps->_a = temp;
ps->_capacity = newcapacity;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->_top--;
}
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
//检测栈是否为空，如果为空返回true，结果不为空false
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->_top == 0)
return true;
else
return false;
}
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
🌉测试文件
Test.c
#include "STackCode.h"
int main()
{
Stack s;
StackInit(&s);
StackPush(&s,1);
StackPush(&s,2);
StackPush(&s,3);
StackPush(&s,4);
int top = StackTop(&s);
printf("%d", top);
StackPop(&s);
StackPush(&s, 5);
StackPush(&s, 6);
while (!StackEmpty(&s))
{
int top = StackTop(&s);
printf("%d", top);
StackPop(&s);
}
StackDestroy(&s);
return 0;
}
测试结果：
文章来源：https://www.toymoban.com/news/detail-838566.html
🚩总结
文章来源地址https://www.toymoban.com/news/detail-838566.html
到了这里，关于【算法与数据结构】栈的实现详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
