使用链表实现栈

与使用数组不同，我们还可以使用链表来实现栈。链表动态分配内存。然而，在所有操作（即 push、pop 和 peek）中，两种场景的时间复杂度是相同的。

在栈的链表实现中，节点在内存中非连续地维护。每个节点都包含一个指向其在栈中直接后继节点的指针。如果内存堆中没有足够的空间来创建节点，则栈会溢出。

栈中最顶端的节点在其地址字段中始终包含 null。让我们讨论在栈的链表实现中如何执行每个操作。

向栈添加节点（Push 操作）

向栈添加节点称为 push 操作。在链表实现中将元素推送到栈与数组实现不同。为了将元素推送到栈，涉及以下步骤。

时间复杂度：o(1)

1. 首先创建一个节点并为其分配内存。
2. 如果列表为空，则将要推送的项作为列表的起始节点。这包括为节点的 data 部分赋值，并为节点的 address 部分赋值 null。
3. 如果列表中已经有一些节点，那么我们必须在列表的开头添加新元素（以不违反栈的属性）。为此，将起始元素的地址赋给新节点的 address 字段，并将新节点设为列表的起始节点。
   1. 检查下溢条件：当尝试从空栈中弹出时，会发生下溢条件。如果列表的 head 指针指向 null，则栈将为空。
   2. 相应地调整 head 指针：在栈中，元素仅从一端弹出，因此，必须删除 head 指针中存储的值并释放节点。head 节点之后的下一个节点现在成为 head 节点。
4. 将 head 指针复制到临时指针。
5. 移动临时指针遍历列表中的所有节点，并打印附加到每个节点的 value 字段。

C 语言实现

从栈中删除节点（POP 操作）

从栈顶删除节点称为 pop 操作。从栈的链表实现中删除节点与数组实现中的不同。为了从栈中弹出元素，我们需要遵循以下步骤。

时间复杂度：o(n)

C 语言实现

显示节点（遍历）

显示栈中的所有节点需要遍历以栈形式组织的链表中的所有节点。为此，我们需要遵循以下步骤。

时间复杂度：o(n)

C 语言实现

使用链表实现所有栈操作的 C 语言菜单驱动程序