当前位置：首页>前端>正文

链栈的基本操作（链表实现）

前端2024-04-27 20:50:19

定义

栈（Stack）是一种遵循后进先出（LIFO，Last In First Out）原则的数据结构，即最后一个被放入栈中的元素总是第一个被拿出来。栈的基本操作包括入栈（push，将元素添加到栈顶）、出栈（pop，从栈顶移除元素）以及查看栈顶元素（peek或getTop，查看栈顶元素但不移除）。

链栈的基本操作（链表实现）,第1张

栈的实现方式主要有两种：基于数组的栈和基于链表的栈。

基于数组的栈：
- 在基于数组的栈中，通常使用一个固定大小的数组来存储栈的元素，同时用一个变量来记录栈顶的位置。当进行入栈操作时，将元素放在数组的末尾；当进行出栈操作时，移除数组的末尾元素。如果数组已满，则栈为满栈；如果数组为空，则栈为空。
- 基于数组的栈具有空间利用率高的优点，因为它避免了链表中的指针开销。但是，如果事先不确定栈的大小，可能需要动态地调整数组的大小，这可能会带来额外的开销。
基于链表的栈：
- 在基于链表的栈中，使用链表结构来存储栈的元素。每个链表节点包含一个数据域和一个指向下一个节点的指针。栈顶元素对应链表的头节点。入栈操作相当于在链表头部插入新节点；出栈操作则是移除链表头节点。
- 基于链表的栈的优点是动态性强，可以根据需要动态地分配和释放内存。但是，由于每个节点都需要额外的空间来存储指针，因此空间利用率可能稍低。

除了这两种基本的实现方式外，还可以根据具体的应用场景和需求，使用其他数据结构或技术来实现栈，比如使用双向链表、静态数组等。在选择栈的实现方式时，需要权衡空间利用率、时间复杂度、动态性等因素。

我们这篇文章讲的是链栈的实现

链栈的基本操作

定义链栈

typedef struct StackNode {  
    int data;           // 数据域  
    struct StackNode *next;  // 指针域  
} StackNode, *LinkStack;

初始化栈

// 初始化栈  
void InitStack(LinkStack *s) {  
    *s = NULL; // 初始时栈顶指针指向NULL  
}

判断栈是否为空

// 判断栈是否为空  
int StackEmpty(LinkStack s) {  
    return s == NULL;  
}

入栈

// 入栈  
void Push(LinkStack *s, int e) {  
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));  
    if (newNode==NULL) {
    perror("malloc fail;);  
        exit(1); // 分配内存失败  
    }  
    newNode->data = e;  
    newNode->next = *s; // 新节点指向当前栈顶  
    *s = newNode; // 更新栈顶指针  
}

出栈

// 出栈  
int Pop(LinkStack *s) {  
    if (StackEmpty(*s)) {  
    perror("Stack empty");    
    return -1; // 栈空，返回错误码  
    }  
    StackNode *top = *s;  
    int e = top->data;  
    *s = top->next; // 更新栈顶指针  
    free(top); // 释放原栈顶节点  
    return e;  
}

获取栈顶元素

// 获取栈顶元素  
int GetTop(LinkStack s) {  
    if (StackEmpty(s)) {  
            perror("Stack empty");  
    return -1; // 栈空，返回错误码  
    }  
    return s->data;  
}

销毁栈

// 销毁栈  
void DestroyStack(LinkStack *s) {  
    StackNode *temp;  
    while (*s != NULL) {  
        temp = *s;  
        *s = (*s)->next;  
        free(temp);  
    }  
}

测试+完整代码

#include <stdio.h>  
#include <stdlib.h>  
  
typedef struct StackNode {  
    int data;           // 数据域  
    struct StackNode *next;  // 指针域  
} StackNode, *LinkStack;  
  
// 初始化栈  
void InitStack(LinkStack *s) {  
    *s = NULL; // 初始时栈顶指针指向NULL  
}  
  
// 判断栈是否为空  
int StackEmpty(LinkStack s) {  
    return s == NULL;  
}  
  
// 入栈  
void Push(LinkStack *s, int e) {  
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));  
    if (!newNode) {  
        exit(1); // 分配内存失败  
    }  
    newNode->data = e;  
    newNode->next = *s; // 新节点指向当前栈顶  
    *s = newNode; // 更新栈顶指针  
}  
  
// 出栈  
int Pop(LinkStack *s) {  
    if (StackEmpty(*s)) {  
        return -1; // 栈空，返回错误码  
    }  
    StackNode *top = *s;  
    int e = top->data;  
    *s = top->next; // 更新栈顶指针  
    free(top); // 释放原栈顶节点  
    return e;  
}  
  
// 获取栈顶元素  
int GetTop(LinkStack s) {  
    if (StackEmpty(s)) {  
        return -1; // 栈空，返回错误码  
    }  
    return s->data;  
}  
  
// 销毁栈  
void DestroyStack(LinkStack *s) {  
    StackNode *temp;  
    while (*s != NULL) {  
        temp = *s;  
        *s = (*s)->next;  
        free(temp);  
    }  
}  
  
// 测试代码  
int main() {  
    LinkStack s;  
    InitStack(&s);  
  
    Push(&s, 1);  
    Push(&s, 2);  
    Push(&s, 3);  
  
    printf("栈顶元素：%d\n", GetTop(s));  
  
    printf("出栈元素：%d\n", Pop(&s));  
    printf("出栈元素：%d\n", Pop(&s));  
  
    printf("栈顶元素：%d\n", GetTop(s));  
  
    DestroyStack(&s);  
  
    return 0;  
}

查看全文

https://www.xamrdz.com/web/2db1936593.html

定义