主要内容 #

1. 链栈
2. 链栈元素入栈
3. 链栈元素出栈

1. 链栈 #

链栈是栈的一种实现方法，特指用链表实现栈存储结构。
链栈的实现思路和顺序栈类似，顺序栈是将顺序表（数组）的一端做栈底，另一端做栈顶；链栈也是如此，我们通常将链表的头部做栈顶，尾部做栈底，如图 1 所示：

图 1 链栈示意图
以链表的头部做栈顶，最大的好处是：可以避免在实现元素 “入栈” 和 “出栈” 时做大量遍历链表的耗时操作。有元素入栈时，只需要将其插入到链表的头部；有元素出栈时，只需要从链表的头部依次摘取结点。
因此，链栈实际上是一个采用头插法插入或删除数据的链表。

2. 链栈元素入栈 #

例如，依次将 1、2、3、4 存储到栈中，每个元素的入栈过程如图 2 所示：

图 2 链栈元素依次入栈过程示意图
C++语言实现代码为：

//链表中的节点结构
struct LineStack {
    int data;
    struct LineStack* next;
};
//stack为当前的链栈，a表示入栈元素
LineStack* push(LineStack* stack, int a) {
    //创建存储新元素的节点
    LineStack* line = (LineStack*)malloc(sizeof(LineStack));
    line->data = a;
    //新节点与头节点建立逻辑关系
    line->next = stack;
    //更新头指针的指向
    stack = line;
    return stack;
}

3. 链栈元素出栈 #

在图 2e) 所示链表的基础上，假设将元素 3 从栈中取出，根据”先进后出”的原则，要先将元素 4 出栈，然后元素 3 才能出栈，整个操作过程如图 3 所示：

图 3 链栈元素出栈示意图
实现栈顶元素出栈的C++语言代码为：

//栈顶元素出链栈的实现函数
LineStack* pop(LineStack* stack) {
    if (stack) {
        //声明一个新指针指向栈顶节点
        LineStack* p = stack;
        //更新头指针
        stack = stack->next;
       cout <<"出栈元素： " << p->data ;
        if (stack) {
            cout << "新栈顶元素 " << stack->data << endl;
        }
        else {
            cout << "栈已空" << endl;;
        }
        free(p);
    }
    else {
        cout << "栈内没有元素";
        return stack;
    }
    return stack;
}

代码中通过使用 if 判断语句，避免了用户执行”栈已空却还要数据出栈”错误操作。

总结 #

本节，通过采用头插法操作数据的单链表实现了链栈结构，这里给出链栈及基本操作的C++语言完整代码：

#include <iostream>
using namespace std;
//链表中的节点结构
struct LineStack {
    int data;
    struct LineStack* next;
};
//stack为当前的链栈，a表示入栈元素
LineStack* push(LineStack* stack, int a) {
    //创建存储新元素的节点
    LineStack* line = (LineStack*)malloc(sizeof(LineStack));
    line->data = a;
    //新节点与头节点建立逻辑关系
    line->next = stack;
    //更新头指针的指向
    stack = line;
    return stack;
}

//栈顶元素出链栈的实现函数
LineStack* pop(LineStack* stack) {
    if (stack) {
        //声明一个新指针指向栈顶节点
        LineStack* p = stack;
        //更新头指针
        stack = stack->next;
       cout <<"出栈元素： " << p->data ;
        if (stack) {
            cout << "新栈顶元素 " << stack->data << endl;
        }
        else {
            cout << "栈已空" << endl;;
        }
        free(p);
    }
    else {
        cout << "栈内没有元素";
        return stack;
    }
    return stack;
}

int main() {
    LineStack* stack = NULL;
    stack = push(stack, 1);
    stack = push(stack, 2);
    stack = push(stack, 3);
    stack = push(stack, 4);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    return 0;
}

程序运行结果为：

弹栈元素：4 栈顶元素：3
弹栈元素：3 栈顶元素：2
弹栈元素：2 栈顶元素：1
弹栈元素：1 栈已空
栈内没有元素