栈（Stack)_栈的时间复杂度

栈

---

栈是一种线性存储数据的数据结构，以后进先出的顺序存储数据。在某些需要对数据按照一定顺序使用的情况下，栈是非常有用的。

可以将栈视作为放在桌子上的一堆盘子，在任何时刻，用户都只能访问最顶部的盘子。用户取盘子或者是放盘子，都只能从盘子的顶部进行操作。

栈的一些运算形式

---

栈的运算形式主要有两个：入栈（Push）和出栈(Pop)

入栈操作

---

向栈中添加元素。对应元素被添加到栈顶。

Peek操作

---

Peek操作用于返回栈中的第一个元素，用于跟踪栈当前的运算位置。不会对栈元素实行删除。

栈上溢和下溢的条件

---

根据栈的实现方式不同，栈的内存空间可能有限。在进行入栈和出栈操作时，我们必须实现关于栈空间的条件检测，确保不超出当前栈所支持的最大操作范围。

下溢条件检查栈操作弹出元素之前栈中中是否存在元素，如果栈为空，则不能继续弹出元素：

if (top==-1){
    //下溢条件
}
1
2
3

上溢条件检查栈是否为满栈（或者是否还有内存空间）。

if (top==sizeOfStack){
    //上溢条件
}
1
2
3

栈顶指针

---

为了能够方便的从栈中添加和删除数据。需要一个特殊的指针来跟踪插入和删除之后，栈中最后一个元素的位置。

栈创建

---

栈的创建主要有两种方式：使用数组或者使用链表。我们首先以数组创建一个简单的栈。

1. 创建一个一维数组，并固定数组的大小（int stack[SIZE],SIZE使用预处理器定义#define SIZE 10
2. 定义一个int类型变量作为top，并初始化为-1(int top=-1)

#define SIZE 10
int stack[SIZE];
int top=-1;
1
2
3

属性

---

1. 遵循后进先出，元素的插入删除均在栈顶进行
2. top指针始终指向栈顶元素

入栈

---

入栈过程

1. 检查栈是否为空（top==SIZE-1)
2. 如果为空，异常并退出
3. 如果不为空，增加top值（top++),并设置stack[top]=value

void push(int value){
    if (top==SIZE-1){
        printf("溢出，栈满");
    }else{
        top++;
        stack[top]=value;
        printf("插入成功);
    }
}
1
2
3
4
5
6
7
8
9

出栈

---

出栈过程

1. 检查栈是否为空（top==-1)
2. 如果为空，异常并退出
3. 如果不为空，删除stack[top]并使top减少(top–)

void pop(){
    if (top==-1){
        printf("栈为空);
    }else{
        printf("删除成功：%d",stack[pop]);
        top--;
    }
}
1
2
3
4
5
6
7
8

访问栈顶

---

访问过程

1. 检查栈是否为空(top==-1)
2. 如果栈为空，异常并退出
3. 如果栈不为空，返回stack[top]

void peek(){
    if (top==-1){
        printf("栈为空");
        break;
    }else{
        printf("%d",stack[top]);
    }
}
1
2
3
4
5
6
7
8

栈运算时间复杂度

---

访问栈元素

要想在栈中查找某个指定的元素，需要连续移除栈顶部的元素直到找打目标元素为止。所以栈的访问时间复杂度为O(n)

查找

查找类似于访问栈元素，需要不断的将元素弹出栈，直到找到目标元素，因此其时间复杂度为O(n)

插入

由于从栈中插入元素仅能从栈顶插入，不需要对栈元素进行迭代，因此栈中插入元素的时间复杂度为O(1)

删除

删除类似于插入，栈操作仅限于栈顶，其时间复杂度为O(1)

空间复杂度

栈仅存储指定数据类的元素的空间，这意味着，要存储n个元素，其空间复杂度为O(n)

使用场景

1. 编辑器的撤销功能 我们编辑文档时，每执行一个操作都会被压如栈中，当我们想要撤回操作时，执行出栈还原操作
2. 表达式解析 通过使用堆栈有助于使用后缀和前缀表示法解析表达式

更多内容，欢迎关注：