数据结构与算法——第3章-链栈及基本操作(3.3)

发表于 分类于 ， ， 阅读时长 ≈ 2 分钟

一 概述

1
2
3
4
1.什么是链栈
2.链栈元素入栈
3.链栈元素出栈
4.C语言完整代码

二 什么是链栈

2.1 概念

1
2
3
4
链栈，即用链表实现栈存储结构。

链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；
链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底，如图 1 所示：

图示1

2.3 说明

1
2
3
4
5
6
7
将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：
1.在实现数据"入栈"操作时，需要将数据从链表的头部插入；
2.在实现数据"出栈"操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表

三 链栈元素入栈

3.1 说明

1
2
例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，
每个数据元素的添加过程如图 2 所示：

图示2

3.3 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//链表中的节点结构
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
//stack为当前的链栈，a表示入栈元素
lineStack* push(lineStack * stack,int a){
    //创建存储新元素的节点
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新节点与头节点建立逻辑关系
    line->next=stack;
    //更新头指针的指向
    stack=line;
    return stack;
}

四 链栈元素出栈

4.1 说明

1
2
例如，图 2e) 所示的链栈中，若要将元素 3 出栈，
根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 3 所示

图示3

4.2 示例代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * stack){
    if (stack) {
        //声明一个新指针指向栈顶节点
        lineStack * p=stack;
        //更新头指针
        stack=stack->next;
        printf("出栈元素：%d ",p->data);
        if (stack) {
            printf("新栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

五 C语言完整代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
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;
        printf("弹栈元素：%d ",p->data);
        if (stack) {
            printf("栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        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;
}

程序运行结果为

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

六 参考

  • C语言中文网—链栈及基本操作（包含入栈和出栈）详解