用链表实现堆栈

使用链表实现堆栈的过程

推送操作

在 Stack 中添加新节点称为推送操作。

在链表中压入一个节点与在数组中插入一个元素是完全不同的。使用链表实现堆栈推送操作涉及几个步骤：

首先创建一个节点并为其分配内存。

如果列表为空，则该节点作为链表的第一个节点被推送。这个操作给节点的数据部分赋值，给节点的地址部分赋NULL。

如果某些节点已经在链表中，那么我们必须在链表的开头添加一个新节点，以免违反 Stack 的属性。为此，将元素分配给新节点的地址字段并创建一个新节点，该节点将成为列表的起始节点。

如果堆栈已满，当我们尝试推送操作时会发生溢出情况。

空推（）
{
 整数值；
 结构节点 *ptr1 = (结构节点*)malloc(sizeof(结构节点));
 如果（ptr1 == NULL）
 {
  print("无法推送节点");
 }
 别的
 {
 printf("输入值");
 scanf(“%d”, &值);
 如果（开始== NULL）
{
 ptr1 -> 值 = 值；
 ptr1 -> 下一个 = NULL；
 开始= ptr1；
 }
别的
{
 ptr1 -> 值 = 值；
 ptr1 -> next = 开始；
 开始= ptr1；
}
 print("数据元素被压入");
}
}

弹出操作

从堆栈中删除节点称为弹出操作。

链表中的弹出节点不同于数组中的弹出元素。执行弹出操作涉及以下步骤：

在 Stack 中，节点从链表的末尾移除。因此，必须删除存储在头指针中的值，并且该节点必须得到释放。下面的链接节点现在将成为头节点。

当我们尝试在 Stack 已经为空时弹出操作时，会发生下溢情况。如果列表的头指针指向 NULL，则 Stack 将毫无意义。

弹出操作

从堆栈中删除节点称为弹出操作。

链表中的弹出节点不同于数组中的弹出元素。执行弹出操作涉及以下步骤：

在 Stack 中，节点从链表的末尾移除。因此，必须删除存储在头指针中的值，并且该节点必须得到释放。下面的链接节点现在将成为头节点。

当我们尝试在 Stack 已经为空时弹出操作时，会发生下溢情况。如果列表的头指针指向 NULL，则 Stack 将毫无意义。

空弹出（）
{
 整数数据；
 结构节点 *ptr1;
 如果（开始== NULL）
{
 printf(“下溢条件”);
}
别的
{
 数据 = 开始 -> 值；
 ptr1 = 开始；
 开始 = 开始 -> 下一步；
 免费（ptr1）；
 printf("dta 元素弹出");
}
}

空白打印
{
 诠释 x;
 结构节点 *ptr1;
 ptr1 ==开始；
 如果（ptr1 == NULL）
{
 printf("空栈");
}
 别的
{
 printf(“显示堆栈元素”);
 同时（ptr1！= NULL）
{
 printf(“%d”, ptr1 -> 值);
 ptr1 = ptr1 -> 下一个；
}
}
}

使用链表实现堆栈的优缺点

使用链表的堆栈实现有一些优点和缺点：

使用链表实现堆栈的优点

动态数据结构

链表是一种动态数据结构，因此它可以在运行时通过分配和释放内存来增长和收缩。

插入和删除

与数组不同，我们不必在插入和删除内容后移动元素。通过更新节点的下一个指针中存在的地址，链表中的插入和删除相对容易。

没有内存浪费

在链表中，可以在运行时增加和减少大小，从而不会浪费内存。

使用链表的堆栈实现的缺点

内存使用情况

需要更多的内存来存储链表中的元素，因为链表中的每个节点都包含一个指针，并且它本身需要额外的内存。

遍历

链表中的节点遍历非常棘手。比如我们要访问位置n的节点，那么就得遍历它之前的所有节点。所以访问一个节点所需的时间很大。

反向移动

使用链表在堆栈实现中反向遍历非常棘手，因为反向指针需要额外的内存，因此会浪费内存。

至此，我们使用链表文章完成了堆栈实现。