栈

数组模拟

用一个指针维护数组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() 来访问栈顶元素。

示例如下：

#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)。

示例如下∶

#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)。

示例如下：

#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)。

示例如下：

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

题目：

更多题目：

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

栈

数组模拟

stack

题目：

💬 评论