栈文档之链栈

链栈

定义

概念

采用链式存储的栈称为链栈。链栈的优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的清空。通常采用单链表实现，并且规定所有操作都是在单链表的表头进行上的（因为头结点的 next 指针指向栈的栈顶结点）。

结构体

链栈的结构体定义如下：

/**
 * 链栈结构体定义
 */
typedef struct LNode {
    /**
     * 数据域
     */
    int data;
    /**
     * 指针域，指向后继结点
     */
    struct LNode *next;
} LNode;// 链栈结点定义
1
2
3
4
5
6
7
8
9
10
11
12
13

特点

• 采用链式存储，便于结点的插入和删除，但是对于栈这种只能在一端操作的数据结构来说，顺序栈和链栈插入和删除的时间复杂度区别不大。
• 链栈的操作和顺序栈的操作类似，出栈和入栈的操作都在栈顶进行。
• 对于带头结点和不带头结点的链栈，具体实现有所不同，下面的实现代码都是以带头结点为例。

基本操作

注，完整代码请参考：

• LinkedStack.c
• LinkedStack.java
• LinkedStackTest.java

概述

链栈的常见操作如下：

• void init(LNode **stack)：初始化链栈。其中 stack 表示链栈。
• int isEmpty(LNode *stack)：判断链栈是否为空。其中 stack 表示链栈。如果链栈为空则返回 1，否则返回 0。
• void push(LNode **stack, int ele)：将元素入栈。其中 stack 表示链栈；ele 表示新元素值。
• int pop(LNode **stack, int *ele)：将元素出栈。其中 stack 表示链栈；ele 用来保存出栈元素。如果链栈为空则返回 0，否则出栈成功则返回 1。
• int getTop(LNode *stack, int *ele)：获取栈顶元素，但不出栈元素。其中 stack 表示链栈；ele 用来保存栈顶元素。如果链栈为空则返回 0，否则返回 1。
• int size(LNode *stack)：获取链栈中的元素个数。其中 stack 表示链栈。
• void print(LNode *stack)：打印链栈中所有元素。其中 stack 表示链栈。
• void clear(LNode **stack)：清空链栈中所有元素。其中 stack 表示链栈。
• void destroy(LNode **stack)：销毁链栈。其中 stack 表示链栈。

init

初始化链栈。

实现步骤如下：

• 创建链栈头结点，为其分配空间，将头结点指针域指向 null，表示是空链栈。

实现代码：

/**
 * 初始化链栈
 * @param stack 未初始化的链栈
 */
void init(LNode **stack) {
    // 即创建链栈的头结点，为其分配空间
    *stack = (LNode *) malloc(sizeof(LNode));
    // 将头结点的 next 指针指向 null，表示这是一个空栈
    (*stack)->next = NULL;
}
1
2
3
4
5
6
7
8
9
10

isEmpty

判断链栈是否为空。如果链栈为空则返回 1，否则返回 0。

实现步骤：

• 判断链栈的栈顶结点是否存在，即 stack->next==null。

实现代码如下：

/**
 * 判断链栈是否为空
 * @param stack 链栈
 * @return 如果链栈为空则返回 1，否则返回 0 表示非空链栈
 */
int isEmpty(LNode *stack) {
    // 即判断链栈的栈顶结点（即头结点的后继结点）是否存在
    if (stack->next == NULL) {
        return 1;
    } else {
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

push

将元素入栈。以 stack=[11, 22, 33]; ele=44 为例如图所示：

实现步骤：

• 创建新结点，为新结点分配空间，指定数据域为 ele，指定指针域初始指向 null，表示这是一个新结点。
• 将新结点入栈。即将新结点的 next 指针指向原栈顶结点（栈顶结点即为 stack->next），然后将链栈头结点的 next 指向新结点。

注：结点入链栈，采用的就是单链表的头插法。

实现代码如下：

/**
 * 将元素入栈
 * @param stack 链栈
 * @param ele 新元素值
 */
void push(LNode **stack, int ele) {
    // 1.创建新节点，为其初始化数据域和指针域
    // 1.1 为新结点分配空间
    LNode *newNode = (LNode *) malloc(sizeof(LNode));
    // 1.2 为新结点指定数据域
    newNode->data = ele;
    // 1.3 将新结点的指针域初始指向 null，表示没有与任何结点进行连接
    newNode->next = NULL;

    // 2.将新节点入栈，成为栈顶结点
    // 2.1 将新结点的 next 指针指向原栈顶结点，完成新结点与原栈顶结点的链接
    newNode->next = (*stack)->next;
    // 2.2将链栈头结点的 next 指针指向新结点，即新结点成为了链栈的新栈顶结点
    (*stack)->next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

pop

将元素出栈，如果是空栈则不能出栈，并且将出栈元素保存到 ele 中。以 stack=[44, 33, 22, 11] 为例如图所示：

实现步骤：

• 参数校验，如果链栈为空，则不能出栈，返回 0 表示出栈失败。
• 用 ele 保存栈顶元素。
• 然后删除栈顶结点。即用链栈的头结点的 next 指针指向原栈顶结点的后继结点。
• 释放原栈顶结点的空间。

实现代码如下：

/**
 * 将元素出栈
 * @param stack 链栈
 * @param ele 用来保存栈顶结点的数据值
 * @return 如果栈空则不能出栈返回 0 表示出栈失败，否则返回 1 表示出栈成功
 */
int pop(LNode **stack, int *ele) {
    // 0.变量，记录栈顶结点
    LNode *topNode = (*stack)->next;
    // 1.判断链栈是否为空，分情况处理
    // 1.1 如果栈空，则返回 0 表示不能出栈
    if (topNode == NULL) {
        return 0;
    }
    // 1.2 如果栈不为空，则出栈栈顶元素
    else {
        // 1.2.1 用 ele 保存栈顶元素的值
        *ele = topNode->data;
        // 1.2.2 删除栈顶结点，即将链栈的头结点的 next 指针指向原栈顶结点的后继结点
        (*stack)->next = topNode->next;
        // 1.2.3 释放栈顶结点空间
        free(topNode);
        // 1.2.4 返回 1 表示出栈成功
        return 1;
    }
}
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

getTop

获取链栈的栈顶元素。以 stack=[44, 33, 22, 11] 为例如图所示：

实现步骤：

• 参数校验，如果栈空则返回 0 表示获取失败。
• 直接返回栈顶结点的数据域。即头结点的后继结点的数据域。

实现代码如下：

/**
 * 获取栈顶元素，但并不出栈
 * @param stack 链栈
 * @param ele 用来保存栈顶元素数据值
 * @return 如果栈空则不能获取栈顶元素则返回 0 表示出栈失败，否则返回 1 表示获取栈顶元素成功
 */
int getTop(LNode *stack, int *ele) {
    // 1.判断链栈是否为空
    // 1.1 如果栈空，则返回 0 表示失败
    if (stack->next == NULL) {
        return 0;
    }
    // 1.2 如果栈非空，则用 ele 保存栈顶元素的值
    else {
        // 1.2.1 用 ele 保存栈顶元素的值，其中 stack->next 指向栈顶结点
        *ele = stack->next->data;
        // 1.2.2 返回 1 表示获取成功
        return 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

size

获取链栈中的结点个数。以 stack=[44, 33, 22, 11] 为例如图所示：

实现步骤：

• 声明变量 len 用作计数器，记录链栈结点个数。
• 从栈顶扫描结点到栈底，统计结点个数。即遍历单链表罢了。

实现代码如下：

/**
 * 获得链栈中结点个数
 * @param stack 链栈
 * @return 结点个数
 */
int size(LNode *stack) {
    // 0.变量，记录链栈的栈顶结点
    LNode *topNode = stack->next;
    // 0.变量，计数器，记录链栈中结点个数
    int len = 0;
    // 1.从栈顶扫描到栈底，统计链栈中结点个数
    while (topNode != NULL) {
        len++;
        topNode = topNode->next;
    }
    // 2.返回结点个数
    return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

print

打印链栈中所有结点。

实现步骤：

• 从栈顶到栈底，扫描栈中所有结点，打印其数据域。即遍历单链表。

实现代码如下：

/**
 * 从栈顶到栈底，打印链栈所有结点
 * @param stack 链栈
 */
void print(LNode *stack) {
    printf("[");
    LNode *topNode = stack->next;
    while (topNode != NULL) {
        printf("%d", topNode->data);
        if (topNode->next != NULL) {
            printf(", ");
        }
        topNode = topNode->next;
    }
    printf("]\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

clear

清空链栈，即将链栈的头结点的 next 指针指向 null。

实现步骤：

• 从栈顶到栈底扫描栈中所有结点，释放每一个结点的存储空间。
• 最后将头结点的 next 指针指向 null，表示是空栈。

实现代码如下：

/**
 * 清空链栈
 * @param stack 链栈
 */
void clear(LNode **stack) {
    // 变量，记录链栈的栈顶结点
    LNode *topNode = (*stack)->next;
    // 从栈顶到栈底扫描栈中所有结点
    while (topNode != NULL) {
        // 记录当前结点的后继结点
        LNode *temp = topNode->next;
        // 释放当前结点的存储空间
        free(topNode);
        // 继续栈的下一个结点
        topNode = temp;
    }
    // 最后将链栈头结点的 next 指针指向 null，表示这是一个空栈
    (*stack)->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

destroy

销毁链栈。

实现代码如下：

/**
 * 销毁链栈
 * @param stack 链栈
 */
void destroy(LNode **stack) {
    // 释放头结点空间
    free(*stack);
}
1
2
3
4
5
6
7
8

练习题

关于链栈的练习题如下：

• Example003-用不带头结点的单链表存储链栈并实现栈相关算法