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

栈

栈（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）**

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

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

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