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

Skrrapper

发布于 2024-07-09 08:38:01

820

发布于 2024-07-09 08:38:01

文章被收录于专栏：技术分享

栈

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

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

出栈和入栈

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

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

入栈：1234

出栈可以是：

1 432

234 1

但不能是：

3 1 4 2

栈的实现

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

栈的基本操作

栈的主要操作包括：

入栈（Push）： 将一个元素放入栈顶。
出栈（Pop）： 移除并返回栈顶的元素。
查看栈顶元素（Peek/Top）： 返回栈顶的元素但不移除它。
判断栈是否为空（IsEmpty）： 检查栈中是否有元素。
获取栈的大小（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;
}

2.入栈

// 入栈
void push(Stack* s, int item) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++(s->top)] = item;
}

3.出栈

// 出栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->items[(s->top)--];
}

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++;
}

栈的使用场景

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

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

栈的注意事项

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

另一种栈

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

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

工作原理

栈帧（Stack Frame）：
- 每次函数调用时，都会在栈上分配一个新的栈帧。栈帧包含该函数的局部变量、参数和一些控制信息（如返回地址）。
- 函数执行完毕后，其对应的栈帧会被弹出，返回控制权给调用它的函数。
入栈（Push）和出栈（Pop）：
- 入栈：当一个函数被调用时，相关数据（如参数和返回地址）会被推入栈中。
- 出栈：当函数执行完毕后，其栈帧会被弹出，恢复之前的状态。
栈指针（Stack Pointer, SP）：
- 栈指针是一个寄存器，用于指向当前栈的顶端。每次入栈和出栈操作都会更新栈指针。
调用约定（Calling Convention）：
- 调用约定定义了函数如何传递参数、如何返回值以及如何维护堆栈。常见的调用约定有Cdecl、Stdcall、Fastcall等。