当前位置:   article > 正文

【数据结构】线性表----栈详解

【数据结构】线性表----栈详解

栈(Stack)是一种常见的数据结构,它具有**后进先出(Last In, First Out, LIFO)**的特点。栈的运作类似于物理世界中的叠盘子:最新放上去的盘子最先被拿走,而最底部的盘子最后才能被取出。

如果你先拿底下的盘子,那么就有可能出现整个盘子组全部倒塌碎落一地——这也就是所谓的栈出错。

出栈和入栈

栈有着先进后出的特点。所以它的出栈和入栈也遵循着这个特点。
我们在存取元素的时候,一般是在栈顶进行——也就是所谓的盘子顶;
而另一端称为栈底,一般就是数据结构的头结点。

入栈出栈的顺序只需记住:顺序必须有规律,例如

入栈:1234

出栈可以是:

1 432

234 1

但不能是:

3 1 4 2

在这里插入图片描述

栈的实现

栈既可以用数组也可以用链表形式实现,但由于栈本来就是连续的数据结构,所以使用数组刚好。如果非要使用链表,那么就使用单链表。(单链表可以解决的问题没必要使用双链表)

在这里插入图片描述

栈的基本操作

栈的主要操作包括:

  1. 入栈(Push): 将一个元素放入栈顶。
  2. 出栈(Pop): 移除并返回栈顶的元素。
  3. 查看栈顶元素(Peek/Top): 返回栈顶的元素但不移除它。
  4. 判断栈是否为空(IsEmpty): 检查栈中是否有元素。
  5. 获取栈的大小(Size): 返回栈中元素的数量。

接下来对其进行具体介绍和代码实现。

1.初始化和前期准备

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100  // 栈的最大容量,根据情况设置

typedef struct {
    int items[MAX];//容量
    int top;//栈顶元素
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;栈顶指针指向-1的位置
}

// 检查栈是否为空
bool isEmpty(Stack* s) {
    return s->top == -1;
}

// 检查栈是否已满
bool isFull(Stack* s) {
    return s->top == MAX - 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

2.入栈

// 入栈
void push(Stack* s, int item) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++(s->top)] = item;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3.出栈

// 出栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->items[(s->top)--];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

在这里插入图片描述

4.删除和插入元素

// 删除栈中的元素(第n个位置)
void deleteElement(Stack* s, int position) {
    if (isEmpty(s) || position < 0 || position > s->top)//不在栈中无法进行删除 
    {
        printf("Invalid position\n");
        return;
    }

    for (int i = position; i < s->top; i++)//进行遍历寻找要删除的元素
    {
        s->items[i] = s->items[i + 1];
    }
    s->top--;
}

// 在栈中插入元素(第n个位置)
void insertElement(Stack* s, int position, int item) {
    if (isFull(s))//栈溢出
    {
        printf("Stack overflow\n");
        return;
    }
    if (position < 0 || position > s->top + 1) {
        printf("Invalid position\n");
        return;
    }

    for (int i = s->top; i >= position; i--) {
        s->items[i + 1] = s->items[i];
    }
    s->items[position] = item;
    s->top++;
}
  • 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

栈的使用场景

栈在计算机科学和编程中有广泛的应用,如:

  • 函数调用管理: 编译器使用栈来管理函数调用和返回地址。
  • 表达式求值: 中缀表达式转换为后缀表达式,以及后缀表达式求值。
  • 撤销操作: 许多软件中的撤销(Undo)功能基于栈实现。

栈的注意事项

  1. 溢出问题: 在某些编程语言或环境中,栈的大小是有限的。如果不断入栈而不出栈,可能会导致栈溢出(Stack Overflow)。
  2. 访问限制: 栈只允许对栈顶进行操作,这意味着在栈中间的元素无法直接访问或修改。
  3. 异常处理: 在出栈或查看栈顶元素时,需要处理栈为空的情况,否则会引发错误。

另一种栈

实际上,以上都是栈在计算机科学以及数据结构中的解释,而在另一个计算机领域——计算机系统中,栈实际上是另一种事物。接下来对其进行简单的介绍。

在计算机系统中,栈(堆栈,Stack)是一种用于管理函数调用和局部变量的内存区域。它是计算机内存的一部分,负责存储函数调用过程中的临时数据,包括函数的参数、局部变量、返回地址等。

工作原理

  1. 栈帧(Stack Frame)

    • 每次函数调用时,都会在栈上分配一个新的栈帧。栈帧包含该函数的局部变量、参数和一些控制信息(如返回地址)。
    • 函数执行完毕后,其对应的栈帧会被弹出,返回控制权给调用它的函数。
  2. 入栈(Push)和出栈(Pop)

    • 入栈:当一个函数被调用时,相关数据(如参数和返回地址)会被推入栈中。
    • 出栈:当函数执行完毕后,其栈帧会被弹出,恢复之前的状态。
  3. 栈指针(Stack Pointer, SP)

    • 栈指针是一个寄存器,用于指向当前栈的顶端。每次入栈和出栈操作都会更新栈指针。
  4. 调用约定(Calling Convention)

    • 调用约定定义了函数如何传递参数、如何返回值以及如何维护堆栈。常见的调用约定有Cdecl、Stdcall、Fastcall等。

栈的用途

  1. 函数调用管理

    • 栈用于管理函数调用和返回,确保函数可以正确地调用其他函数,并在完成后返回调用点。
  2. 局部变量存储

    • 函数的局部变量通常存储在栈帧中,便于管理和清理。
  3. 递归支持

    • 栈结构天然支持递归调用,每次递归调用都会在栈上创建新的栈帧。

栈溢出(Stack Overflow)

栈的空间是有限的,如果函数调用层次过深(如递归调用过多),可能会导致栈空间耗尽,发生栈溢出。这种情况下,程序通常会崩溃或抛出异常。

这种栈的机制确保了函数调用的有序进行和局部变量的有效管理。

通过以上的介绍和代码示例,相信你对栈这种数据结构有了一个基本的了解。栈作为一种基础而重要的数据结构,我们会经常使用到它,所以需要熟练掌握。
ck Overflow)**

栈的空间是有限的,如果函数调用层次过深(如递归调用过多),可能会导致栈空间耗尽,发生栈溢出。这种情况下,程序通常会崩溃或抛出异常。

这种栈的机制确保了函数调用的有序进行和局部变量的有效管理。

通过以上的介绍和代码示例,相信你对栈这种数据结构有了一个基本的了解。栈作为一种基础而重要的数据结构,我们会经常使用到它,所以需要熟练掌握。

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

闽ICP备14008679号