---
title: "栈"
created: 2025-11-28
tags:
  - 算法
---

# 栈

## 数组模拟

用一个指针维护数组st的一段区间即可

插入删除操作只能在这个指针处进行

该指针初始在-1处表示空 `top=-1`

添加操作为：`st[++top]=x`

删除就直接`top--` 把指针往左移就行了 不需要真的删除 后面要加新元素自然会把当前元素覆盖

返回栈顶即`st[top]`

用`top==-1?"yes":"no"`判空

## stack

1、stack的定义

要使用 stack，应先添加头文件 `#include <stack>`，并在头文件下面加上 `using namespace std;` ，然后就可以使用了。

其定义的写法和其他 STL 容器相同，typename 可以任意基本数据类型或容器：

`stack< typename > name;`

2、stack 容器内元素的访问

由于栈（stack）本身就是一种后进先出的数据结构，在 STL 的 stack 中只能通过 top() 来访问栈顶元素。

示例如下：

```cpp
#include <stdio.h>
#include <stack>
using namespace std;
int main()
{
    stack<int> st;
    for(int i=1;i<=5;i++)
    {
        st.push(i); //push(i) 用以把 i 压入栈，故此处依次入栈 1 2 3 4 5
    }
    printf("%d\n",st.top());    //top()取栈顶元素
    return 0;
}
```

输出结果：

> 5

3、stack 常用函数实例解析

（1）push( )

push(x) 将 x 入栈，时间复杂度为 O(1)。

（2）top( )

top( ) 获得栈顶元素，时间复杂度为 O(1)。

（3）pop( )

pop( ) 用以弹出栈顶元素，时间复杂度为 O(1)。

示例如下∶

```cpp
#include <stdio.h>
#include <stack>
using namespace std;
int main()
{
    stack<int> st;
    for(int i=1;i<=5;i++)
    {
        st.push(i);		//	将1 2 3 4 5依次入栈
    }
    for(int i=1;i<=3;i++)
    {
        st.pop(); //连续三次将栈顶元素出栈，即将5 4 3 依次出栈
    }
    printf("%d\n",st.top());
    return 0;
}
```

输出结果：

>  2

（4）empty( )

empty( ) 可以检测 stack 内是否为空，返回 true 为空，返回 false 为非空，时间复杂度为 O(1)。

示例如下：

```cpp
#include <stdio.h>
#include <stack>
using namespace std;
int main()
{
    stack<int> st;
    if(st.empty()==true)
    {
        //一开始栈内没有元素，因此栈空
        printf ("Empty\n");
    }
    else
    {
        printf("Not Empty\n");
    }
    st.push(1);
    if(st.empty()== true)
    {
       //入栈"1"后，栈非空
        printf("Empty\n");
    }
    else
    {
        printf("Not Empty\n");
    }
    return 0;
}
```

输出结果：

> Empty
>
> Not Empty

（5）size()

size() 返回 stack 内元素的个数，时间复杂度为 O(1)。

示例如下：

```cpp
#include <stdio.h>
#include <stack>
using namespace std;
int main()
{
    stack<int> st;
    for(int i= 1;i<= 5;i++)
    {
        st.push(i); //push(i)用以将i压入栈
    }
    printf("%d\n",st.size());//栈内有5个元素
    return 0;
}
```

输出结果：

> 5

4、stack 的常见用途

stack 用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。一般来说，程序的栈内存空间很小，对有些题目来说，如果用普通的函数来进行递归，一旦递归层数过深（不同机器不同，约几千至几万层），则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题（不过这种应用出现较少）。

## 题目：

- [[奶牛慢跑|奶牛慢跑]]
- [[字符串|字符串]]

- [[栈的压入、弹出序列|栈的压入、弹出序列]]
- [[弹出序列|弹出序列]]
- [[（待做）火车进出栈问题|（待做）火车进出栈问题]]

- [[括号匹配|括号匹配]]
- [[括号的匹配|括号的匹配]]
- [[括号画家|括号画家]]
- [[最长合法括号子串|最长合法括号子串]]

- [[插松枝|插松枝]]
- [[包装机|包装机]]

**更多题目：**

- [包装机](https://www.acwing.com/problem/content/description/3467/)
- [删减](https://www.acwing.com/problem/content/1885/)
- [字符串消除](https://www.acwing.com/problem/content/description/4507/)

  **表达式系列**
- [表达式求值](https://www.acwing.com/problem/content/description/3305/)
- [表达式计算4](https://www.acwing.com/problem/content/153/)
- [表达式求值](https://www.acwing.com/problem/content/description/456/)
- [剑指 Offer 06. 从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)
- [反转链表](http://leetcode-cn.com/problems/reverse-linked-list/)
- [括号的最大嵌套深度](https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses/)
- [有效的括号](https://leetcode.cn/problems/valid-parentheses/)
- [最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/)
- [剑指 Offer II 027. 回文链表](https://leetcode-cn.com/problems/baseball-game/)
- [回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
- [回文链表](https://leetcode-cn.com/problems/aMhZSa/)
- [棒球比赛](https://leetcode-cn.com/problems/baseball-game/)
- [剑指 Offer II 036. 后缀表达式](https://leetcode-cn.com/problems/8Zf90G/)
- [比较含退格的字符](https://leetcode.cn/problems/backspace-string-compare/)
- [三合一](https://leetcode-cn.com/problems/three-in-one-lcci/)
- [验证栈序列](https://leetcode-cn.com/problems/validate-stack-sequences/)
- [剑指 Offer 31. 栈的压入、弹出序列](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/)
- [从先序遍历还原二叉树](https://blog.csdn.net/WhereIsHeroFrom/article/details/124240461)

---
⬅️ [[滑动窗口的最大值|滑动窗口的最大值]] 🏠 [[00-刷题理模型]] ➡️ [[包装机|包装机]]