当前位置:   article > 正文

栈文档之链栈

链栈

链栈

定义

概念

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

在这里插入图片描述

结构体

链栈的结构体定义如下:

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

特点

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

基本操作

注,完整代码请参考:

概述

链栈的常见操作如下:

  • 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

练习题

关于链栈的练习题如下:

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/905933
推荐阅读
相关标签
  

闽ICP备14008679号