• 【数据结构】栈的知识点总结--关于栈的定义和基本操作；C语言实现栈；顺序栈；链栈；共享栈；栈的易错点的总结

    欢迎各位看官^_^

    目录

    1.栈的定义

    2.栈的基本操作

    2.1创建

    2.2销毁

    2.3插入Push

    2.4删除Pop

    2.5获得栈顶元素GetTop

    2.6判空

    2.7清空栈

    3.C语言实现栈

    4.顺序栈

    4.1数组实现顺序栈

    4.2链表实现顺序栈

    5.链栈

    5.1入栈操作

    5.2出栈操作

    5.3初始化

    6.共享栈

     7.栈的易错点

    1.栈的定义

            栈（stack）是一种线性数据结构，采用后进先出（Last In First Out）的原则，即最后一个进入栈的元素最先被取出。栈的常用操作有：push（入栈），pop（出栈），isEmpty（判断栈是否为空），peek（查看栈顶元素）。它具有“先进后出”的特点。栈通过顶部进行操作，只能在栈顶进行插入和删除操作，因此也被称为“后进先出（LIFO）”的结构。

            栈的应用非常广泛，比如在编程中可以用来实现函数调用、表达式求值、括号匹配等；在计算机系统中可以用来实现系统调用、内存分配等。

            常见的栈实现方式有数组和链表两种，其中数组实现的栈又称为顺序栈，链表实现的栈称为链式栈。

    2.栈的基本操作

    2.1创建

    1. void InitStack(SqStack *S)
    2. {
    3.     S->top = -1; // 栈顶指针初始化为-1，表示栈为空
    4. }

    2.2销毁

    1. void DestroyStack(SqStack *S)
    2. {
    3.     free(S); // 释放栈空间
    4. }

    2.3插入Push

            在 push 操作时，将元素插入数组中，并将栈顶指针加一；在 pop 操作时，将栈顶指针减一并返回栈顶元素。

    1. bool Push(SqStack *S, int x)
    2. {
    3.     if (S->top == MAX_SIZE-1) // 栈满，无法插入新元素
    4.         return false;
    5.     S->top++; // 栈顶指针+1
    6.     S->data[S->top] = x; // 新元素入栈
    7.     return true;
    8. }

    2.4删除Pop

            栈的删除操作指的是从栈中弹出元素的操作。由于栈是一种“后进先出”的数据结构，因此删除的元素总是栈顶元素。

            栈的删除操作可以使用 pop() 方法来实现。pop() 方法会弹出并返回栈顶元素，同时将栈顶指针指向下一个元素。如果栈为空，则弹出操作会抛出异常。

    1. bool Pop(SqStack *S, int *x)
    2. {
    3.     if (S->top == -1) // 栈为空，无法弹出栈顶元素
    4.         return false;
    5.     *x = S->data[S->top]; // 栈顶元素出栈
    6.     S->top--; // 栈顶指针-1
    7.     return true;
    8. }

    2.5获得栈顶元素GetTop

            在C语言中通过数组实现栈的操作，我们可以通过下标来获取栈顶元素。假设我们定义了一个栈数组stack和一个栈顶指针top，那么获得栈顶元素的方法如下： 

    1. bool GetTop(SqStack S, int *x)
    2. {
    3.     if (S.top == -1) // 栈为空，无法获取栈顶元素
    4.         return false;
    5.     *x = S.data[S.top]; // 获取栈顶元素
    6.     return true;
    7. }

            这个函数接收栈数组和栈顶指针作为参数，如果栈为空则输出提示信息并返回-1，否则返回栈顶元素。 

    2.6判空

    1. bool StackEmpty(SqStack S)
    2. {
    3.     return S.top == -1; // 栈顶指针为-1表示栈为空
    4. }

    2.7清空栈

    1. void ClearStack(SqStack *S)
    2. {
    3.     S->top = -1; // 栈顶指针初始化为-1，表示栈为空
    4. }

    3.C语言实现栈

            在使用 C 语言实现栈时，我们可以使用数组来存储栈中元素，并使用一个变量来记录栈顶指针。栈顶指针指向栈顶元素的下标。在 push 操作时，将元素插入数组中，并将栈顶指针加一；在 pop 操作时，将栈顶指针减一并返回栈顶元素。

            我们使用结构体定义了一个 Stack 类型，包含一个数组和一个整数类型的栈顶指针 top。在 createStack 函数中，我们分配了一个 Stack 结构体的内存，并将 top 初始化为 -1。isEmpty 函数用于判断栈是否为空。push 函数用于将元素入栈，如果栈已满则打印出错信息并退出程序，否则将元素插入数组中并将 top 加一。pop 函数用于弹出栈顶元素，如果栈为空则打印出错信息并退出程序，否则返回栈顶元素并将 top 减一。在主函数中，我们创建了一个新栈并调用了 push 和 pop 操作，最后释放了所分配的内存。

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. #define MAX_SIZE 100
    5.  
    6. struct Stack {
    7.     int data[MAX_SIZE]; // 数组存储元素
    8.     int top; // 栈顶指针
    9. };
    10.  
    11. struct Stack* createStack() {
    12.     struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    13.     stack->top = -1;
    14.     return stack;
    15. }
    16.  
    17. int isEmpty(struct Stack* stack) {
    18.     return stack->top == -1;
    19. }
    20.  
    21. void push(struct Stack* stack, int x) {
    22.     if (stack->top == MAX_SIZE - 1) {
    23.         printf("Stack Overflow\n");
    24.         exit(1);
    25.     }
    26.     stack->data[++stack->top] = x;
    27. }
    28.  
    29. int pop(struct Stack* stack) {
    30.     if (isEmpty(stack)) {
    31.         printf("Stack Underflow\n");
    32.         exit(1);
    33.     }
    34.     return stack->data[stack->top--];
    35. }
    36.  
    37. int main() {
    38.     struct Stack* stack = createStack();
    39.  
    40.     push(stack, 1);
    41.     push(stack, 2);
    42.     push(stack, 3);
    43.  
    44.     printf("%d\n", pop(stack)); // 输出 3
    45.     printf("%d\n", pop(stack)); // 输出 2
    46.     printf("%d\n", pop(stack)); // 输出 1
    47.  
    48.     free(stack);
    49.     return 0;
    50. }

    4.顺序栈

    4.1数组实现顺序栈

            在这个示例代码中，我们定义了一个栈数组 stack 和一个指针 top，用于跟踪栈顶元素的位置。push() 函数用于将元素推入栈，如果栈满了，就会返回一个错误信息。pop() 函数用于弹出栈顶元素，如果栈为空，则返回一个错误信息。peek() 函数用于返回栈顶元素的值，如果栈为空，则返回 -1。print() 函数用于打印整个栈的内容。

            在主函数中，我们演示了如何使用这些函数。我们先将元素 1、2 和 3 推入栈中，然后打印整个栈。接着我们弹出栈顶元素，再次打印栈内容，最后打印栈顶元素的值。

    1. #include <stdio.h>
    2. #define MAX_SIZE 100
    3.  
    4. int stack[MAX_SIZE];
    5. int top = -1;
    6.  
    7. void push(int x) {
    8.     if (top == MAX_SIZE - 1) {
    9.         printf("Error: Stack overflow\n");
    10.         return;
    11.     }
    12.     stack[++top] = x;
    13. }
    14.  
    15. void pop() {
    16.     if (top == -1) {
    17.         printf("Error: Stack is empty\n");
    18.         return;
    19.     }
    20.     top--;
    21. }
    22.  
    23. int peek() {
    24.     if (top == -1) {
    25.         printf("Error: Stack is empty\n");
    26.         return -1;
    27.     }
    28.     return stack[top];
    29. }
    30.  
    31. void print() {
    32.     if (top == -1) {
    33.         printf("Stack is empty\n");
    34.         return;
    35.     }
    36.     printf("Stack: ");
    37.     for (int i = 0; i <= top; i++) {
    38.         printf("%d ", stack[i]);
    39.     }
    40.     printf("\n");
    41. }
    42.  
    43. int main() {
    44.     push(1);
    45.     push(2);
    46.     push(3);
    47.     print(); // Stack: 1 2 3
    48.     pop();
    49.     print(); // Stack: 1 2
    50.     printf("Top element: %d\n", peek()); // Top element: 2
    51.     return 0;
    52. }

    4.2链表实现顺序栈

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. // 定义链表节点结构体
    5. struct node {
    6.     int data;
    7.     struct node *next;
    8. };
    9.  
    10. // 定义顺序栈结构体
    11. struct stack {
    12.     struct node *top;
    13. };
    14.  
    15. // 初始化栈
    16. void init_stack(struct stack *s) {
    17.     s->top = NULL;
    18. }
    19.  
    20. // 入栈
    21. void push(struct stack *s, int data) {
    22.     struct node *new_node = (struct node *)malloc(sizeof(struct node));
    23.     new_node->data = data;
    24.     new_node->next = s->top;
    25.     s->top = new_node;
    26. }
    27.  
    28. // 出栈
    29. int pop(struct stack *s) {
    30.     if (s->top == NULL) {
    31.         printf("Error: stack is empty.\n");
    32.         return -1;
    33.     }
    34.     int data = s->top->data;
    35.     struct node *temp = s->top;
    36.     s->top = s->top->next;
    37.     free(temp);
    38.     return data;
    39. }
    40.  
    41. // 打印栈中元素
    42. void print_stack(struct stack *s) {
    43.     struct node *current = s->top;
    44.     printf("Stack: ");
    45.     while (current != NULL) {
    46.         printf("%d ", current->data);
    47.         current = current->next;
    48.     }
    49.     printf("\n");
    50. }
    51.  
    52. int main() {
    53.     struct stack s;
    54.     init_stack(&s);
    55.     push(&s, 1);
    56.     push(&s, 2);
    57.     push(&s, 3);
    58.     print_stack(&s);
    59.     printf("Popped: %d\n", pop(&s));
    60.     printf("Popped: %d\n", pop(&s));
    61.     print_stack(&s);
    62.     push(&s, 4);
    63.     push(&s, 5);
    64.     print_stack(&s);
    65.     return 0;
    66. }

    输出结果： 

    Stack: 3 2 1
    Popped: 3
    Popped: 2
    Stack: 1
    Stack: 5 4 1

    5.链栈

    链栈是一种使用链表结构实现的栈，入栈和出栈操作与普通栈的操作相似。

    5.1入栈操作

    在链栈的顶部插入一个新节点即可，也可以说是将新元素作为链表的表头。具体步骤如下：

            1. 创建一个新的节点，并给节点赋值。
            2. 如果链栈为空，将新的节点设为栈顶，即链栈的头节点。
            3. 如果链栈不为空，将新的节点插入到链栈的头节点之前，然后将新节点设为栈顶。

    5.2出栈操作

    从链栈的顶部删除一个节点即可，也可以说是删除链表的表头。具体步骤如下：

            1. 如果链栈为空，直接返回空。
            2. 如果链栈不为空，将栈顶节点删除，然后将栈顶指针指向下一个节点。

    5.3初始化

            链栈是基于链表实现的栈，其初始化需要创建一个头节点，头节点的指针域指向空。初始化后的链栈拥有一个头节点，top指针指向头节点的下一个节点，count为0表示栈为空。

    1. typedef struct StackNode {
    2.     int data; // 数据域
    3.     struct StackNode *next; // 指针域
    4. } StackNode, *LinkStackPtr;
    5.  
    6. typedef struct {
    7.     LinkStackPtr top; // 栈顶指针
    8.     int count; // 栈元素个数
    9. } LinkStack;
    10.  
    11. void InitStack(LinkStack *S)
    12. {
    13.     S->top = (LinkStackPtr)malloc(sizeof(StackNode)); // 创建头节点
    14.     S->top->next = NULL; // 头节点的指针域指向空
    15.     S->count = 0; // 栈元素个数为0
    16. }

    6.共享栈

            共享栈是一种特殊的栈数据结构，它是两个栈共用同一块内存空间。这种栈可以实现两个栈在同一块空间上进行操作，节约了内存空间。共享栈的实现可以通过两种方式：静态分配和动态分配。

            静态分配的共享栈是在程序开始时预先定义它的大小，而动态分配的共享栈则是在程序运行时动态地分配内存。静态分配的共享栈适用于事先知道栈大小的情况，而动态分配的共享栈则更加灵活，可以根据实际需要进行分配。

            共享栈的常规操作包括push、pop和isEmpty等。当两个栈都没有满时，可以同时向两个栈中push元素。当其中一个栈满时，另一个栈可以继续使用剩余空间。同样地，当其中一个栈为空时，另一个栈可以继续使用整个空间。

            共享栈常用于多个程序共用同一块内存空间的情况。在嵌入式系统中，共享栈可以用于操作系统内核和应用程序之间共享内存的情况。

    以下是用C语言实现共享栈的示例代码，其中使用静态分配的方式：

    1.  
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4.  
    5. #define MAX_SIZE 100 // 共享栈的最大大小
    6.  
    7. typedef struct {
    8.     int data[MAX_SIZE];
    9.     int top1;
    10.     int top2;
    11. } ShareStack;
    12.  
    13. // 初始化共享栈
    14. void initShareStack(ShareStack *stack) {
    15.     stack -> top1 = -1;
    16.     stack -> top2 = MAX_SIZE;
    17. }
    18.  
    19. // 判断共享栈是否为空
    20. int isShareStackEmpty(ShareStack *stack) {
    21.     return stack -> top1 == -1 && stack -> top2 == MAX_SIZE;
    22. }
    23.  
    24. // 将元素压入栈1
    25. void pushToStack1(ShareStack *stack, int x) {
    26.     if (stack -> top1 + 1 == stack -> top2) { // 栈1和栈2的分界点
    27.         printf("Stack overflow.\n");
    28.         return;
    29.     }
    30.     stack -> top1++;
    31.     stack -> data[stack -> top1] = x;
    32. }
    33.  
    34. // 将元素压入栈2
    35. void pushToStack2(ShareStack *stack, int x) {
    36.     if (stack -> top1 + 1 == stack -> top2) { // 栈1和栈2的分界点
    37.         printf("Stack overflow.\n");
    38.         return;
    39.     }
    40.     stack -> top2--;
    41.     stack -> data[stack -> top2] = x;
    42. }
    43.  
    44. // 从栈1中弹出元素
    45. int popFromStack1(ShareStack *stack) {
    46.     if (stack -> top1 == -1) {
    47.         printf("Stack underflow.\n");
    48.         return -1;
    49.     }
    50.     int x = stack -> data[stack -> top1];
    51.     stack -> top1--;
    52.     return x;
    53. }
    54.  
    55. // 从栈2中弹出元素
    56. int popFromStack2(ShareStack *stack) {
    57.     if (stack -> top2 == MAX_SIZE) {
    58.         printf("Stack underflow.\n");
    59.         return -1;
    60.     }
    61.     int x = stack -> data[stack -> top2];
    62.     stack -> top2++;
    63.     return x;
    64. }
    65.  
    66. int main() {
    67.     ShareStack stack;
    68.     initShareStack(&stack);
    69.     pushToStack1(&stack, 1);
    70.     pushToStack1(&stack, 2);
    71.     pushToStack2(&stack, 3);
    72.     pushToStack2(&stack, 4);
    73.     printf("pop from stack1: %d\n", popFromStack1(&stack));
    74.     printf("pop from stack2: %d\n", popFromStack2(&stack));
    75.     return 0;
    76. }

            在上述示例代码中，共享栈的最大大小为100，定义了一个结构体ShareStack来表示共享栈。其中，top1表示栈1的栈顶指针，top2表示栈2的栈顶指针。静态分配的共享栈在程序开始时预先定义了它的大小，并使用结构体中的data数组来存储共享栈的元素。

            在初始化共享栈时，将栈1和栈2的栈顶指针都初始化为-1和MAX_SIZE，表示栈为空。isShareStackEmpty函数用于判断共享栈是否为空。

            共享栈的push和pop操作分别对两个栈进行处理。当栈1和栈2的分界点相遇时，说明两个栈都满了，此时再push元素会导致栈溢出。因此，在push操作前需要检查是否已经满了。

            在pop操作中，如果栈1或栈2为空，则会出现栈下溢的情况，需要进行处理。

            最后，在测试代码中，我们向栈1和栈2中各压入两个元素，然后依次从栈1和栈2中弹出元素。

     7.栈的易错点

    栈是一种常见的数据结构，易错点包括以下几个方面：

    1. 栈空间溢出：当栈中存储的数据量超过了栈的大小时，将会发生栈溢出错误。

    2. 函数调用不当：函数调用时，参数、返回值、局部变量等数据都存储在栈中。如果函数调用不当，例如递归函数调用深度太深，会导致栈空间快速耗尽，从而引发栈溢出错误。

    3. 栈中数据类型不匹配：栈数据结构中只能存储一种数据类型，如果在栈中存储了不同类型的数据，会导致数据类型不匹配错误。

    4. 栈的访问越界：当访问栈中的数据时，注意不能超出栈的范围，否则会引发栈访问越界错误。

    5. 栈的空间过小：栈的大小限制了存储在其中的数据量，如果栈的空间过小，容易发生栈溢出错误。

    6. 栈中数据处理不当：栈中的数据应该按照先进后出的顺序处理，如果处理顺序错乱，会导致结果错误。

            综上所述，栈的易错点主要包括栈空间溢出、函数调用不当、栈中数据类型不匹配、栈的访问越界、栈的空间过小和栈中数据处理不当等方面。要避免这些错误，应该注意栈的使用规范和限制。

    🤞❤️🤞❤️🤞❤️栈的知识点总结就到这里啦，如果对博文还满意的话，劳烦各位看官动动“发财的小手”留下您对博文的赞和对博主的关注吧🤞❤️🤞❤️🤞❤️

  • 相关阅读:
    arch linux 安装 vsftpd 配置虚拟用户
    【文件格式_XML_HTML_】XML、HTML文件
    windows操作系统双网卡问题处理办法
    qt 使用单例模式操作数据库
    GO语言基础
    [附源码]SSM计算机毕业设计疫情背景下社区公共卫生服务系统JAVA
    MLOps：模型监控
    前端性能优化方法与实战02 性能瓶颈点：从 URL 输入到页面加载整过程分析
    Golang实现一个一维结构体，根据某个字段排序
    阿里云服务器上安装redis
  • 原文地址：https://blog.csdn.net/qq_52442214/article/details/132774540