数据结构【链栈】

基于 C++ 实现链表栈：原理、代码与应用

一、引言

栈就是一个容器，可以当场一个盒子，只能一个一个拿，一个一个放，而且是从上面放入。
有序顺序栈操作比较容易【会了链栈之后顺序栈自然明白】，所以我们这里只对链表进行详细解释。

二、栈的链表实现原理

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。利用链表实现栈，就是将链表的头部作为栈顶，通过对链表头部的操作来模拟栈的入栈和出栈操作。这种实现方式的优点在于不需要预先分配固定大小的内存空间，能够根据实际需求动态调整栈的大小。

三、代码实现

1. 栈节点的定义

#include<iostream>
using namespace std;typedef struct stacknode {int date; // 存放数据struct stacknode* next; // 指针域
} lststack;lststack *S;

这里定义了一个名为 stacknode 的结构体，并重命名为 lststack。每个节点包含一个整数 date 用于存储数据，以及一个指向下一个节点的指针 next。同时，声明了一个全局的栈顶指针 S。

2. 栈的初始化

lststack *initstack()
{ // 初始化lststack* S = NULL;return S;
}

initstack 函数用于初始化栈，将栈顶指针置为 NULL，表示栈为空。

3. 判断栈是否为空

int empty(lststack* S)
{if (S == NULL) return 1;else return 0;
}

empty 函数用于判断栈是否为空。如果栈顶指针为 NULL，则返回 1，表示栈为空；否则返回 0。

4. 入栈操作

lststack *push(lststack* s, int x)
{lststack* p = (lststack*)malloc(sizeof(lststack));p->date = x;p->next = s;s = p;return s;
}

push 函数用于将元素 x 压入栈中。具体步骤如下：

• 使用 malloc 函数为新节点分配内存空间。
• 将元素 x 赋值给新节点的 date 成员。
• 让新节点的 next 指针指向原来的栈顶节点。
• 更新栈顶指针为新节点。
• 返回更新后的栈顶指针。

5. 出栈操作

lststack* pop(lststack* s, int *x)
{lststack* p = (lststack*)malloc(sizeof(lststack));if (empty(s)) {cout << "栈空了" << endl;return NULL;}*x = s->date;p = s;s = s->next;free(p);return s;
}

pop 函数用于将栈顶元素弹出栈。具体步骤如下：

• 首先检查栈是否为空，如果为空则输出提示信息并返回 NULL。
• 将栈顶元素的值赋给指针 x 所指向的变量。
• 用临时指针 p 指向栈顶节点。
• 更新栈顶指针为原栈顶节点的下一个节点。
• 释放原栈顶节点的内存空间。
• 返回更新后的栈顶指针。

6. 查看栈顶元素

int top(lststack* s, int* x)
{lststack* p = (lststack*)malloc(sizeof(lststack));if (empty(s)) {cout << "栈空了" << endl;return 0;}*x = s->date;return 1;
}

top 函数用于查看栈顶元素的值。如果栈为空，则输出提示信息并返回 0；否则将栈顶元素的值赋给指针 x 所指向的变量，并返回 1。

7. 打印栈元素

void print(lststack* s)
{lststack* p = (lststack*)malloc(sizeof(lststack));p = s;if (empty(s)) {cout << "栈空了" << endl;return;}while (p){cout << p->date;p = p->next;}return;
}

print 函数用于遍历栈并打印每个元素的值。如果栈为空，则输出提示信息；否则从栈顶开始依次打印每个元素的值。

8. 主函数测试

结果如下：

在主函数中，首先调用 initstack 函数初始化栈，然后使用 push 函数将元素 1、2、3、5 依次压入栈中，接着使用 print 函数打印栈中的元素，再使用 pop 函数弹出一个元素并打印弹出的元素的值，最后再次使用 print 函数打印栈中的元素。
`

五、总结

通过本文的介绍，我们学习了如何使用 C++ 语言，利用链表实现一个栈。这种实现方式具有动态调整大小的优点，适用于需要灵活管理内存的场景。同时，我们也对代码中存在的问题进行了分析，并给出了优化建议。在实际应用中，我们可以根据具体需求对代码进行进一步的扩展和优化。