【算法竞赛】栈

栈的特点是"先进后出"。

栈在生活中的原型有:坐电梯,先进电梯的被挤在最里面,只能最后出来；一管泡腾片,最先放进管子的药片位于最底层，最后被拿出来。
栈只有唯一的出入口,从这个口进入,也从这个口弹出,这是它与队列最大的区别。
队列有一个入口和一个出口,所以手写栈比手写队列更简单。

编程中常用的递归就是用栈来实现的。栈需要用空间存储,如果栈的深度太大,或者存进栈的数组太大,那么总数会超过系统为栈分配的空间,就会爆栈导致栈溢出。这是递归的主要问题,递归深度要注意。

编码时通常直接用STL stack,或者自己手写找。为避免爆栈,需要控制栈的大小。

STL stack（栈）

STL stack的有关操作如表1.2所示.

下面用一道例题说明栈的应用：

代码如下,其中用到了栈的多个操作

#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int n;
    scanf("%d", &n);
    getchar();
    while (n--) 
    {
        stack<char> s;
        while (true) 
        {
            char ch = getchar();
            if (ch == ' ' || ch == '\n' || ch == EOF) 
            {
                while (!s.empty()) 
                {
                    printf("%c", s.top());
                    s.pop();
                }
                printf("");
                
                if (ch == '\n' || ch == EOF) 
                break;
            } 
            
            else
            {
                s.push(ch);
            }
            printf("\n");
        }
    }
    return 0;
}

手写栈

手写栈代码简单且节省空间.
下面针对例题,自己写一个简单的栈.代码中包括栈的基本操作:push()、pop()、top()、empty().用t指向栈顶.

#include<bits/stdc++.h>
const int N = 100100;

struct mystack
{
    char a[N];
    int t = 0;
    
    void push(char x){a[++t]=x;}
    char top() { return a[t];}
    void pop() {t--; }
    int empty() { return t==0?1:0;}
}st;

int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    while(n--)
    {
        while(true) 
        {
            char ch = getchar();
if(ch=='.' || ch=='\n' || ch==EOF) 
{
    while(!st.empty())
    {
        printf("%c", st.top());
        st.pop();
    }
    if(ch=='\n' || ch==EOF) break;
    printf("");
}
else st.push(ch);
printf("\n");
}
    }
    return 0;
}

单调栈

单调栈不是一种新的栈结构,它在结构上仍然是一个普通的栈,它是栈的一种使用方式。

单调栈内的元素是单调递增或递减的,有单调递增栈、单调递减栈。单调栈可以用来处
理比较问题。

单调栈实际上就是普通的栈,只是使用时始终保持栈内的元素是单调的。例如,单调递
减栈从栈顶到栈底是从小到大的顺序。当一个数入栈时,与栈顶比较,若比栈顶小,则入栈;若比栈顶大,则弹出栈顶,直到这个数能入栈为止。注意,每个数都一定入栈。

单调栈比单调队列简单,因为栈只有一个出入口。
用下面的例题说明单调栈的简单应用。

例1.6

题解：
从后向前遍历奶牛,并用一个栈保存从低到高的奶牛,栈顶的奶牛最矮,栈底的最高。

具体操作:遍历到奶牛i时,将栈顶的奶牛与其进行比较,如果不比奶牛i高,就弹出栈顶,直到栈顶的奶牛比奶牛i高,这就是奶牛i的仰望对象;然后把i放进栈顶,找中的奶牛仍然保持从低到高。
每头奶牛只进出栈一次,所以复杂度为O(n)。

STL stack代码如下：

#include <iostream>
#include <stack>
using namespace std;

int main() 
{
    int n;
scanf("%d", &n);
    
    int h[1005];
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
   
    stack<int> st;
    int ans[1005];
    for (int i = n; i >= 1; i--) 
    {
        while (!st.empty() && h[st.top()] <= h[i]) 
        {
            if (!st.empty()) 
            st.pop();
        }
        ans[i] = st.empty()? 0 : st.top();
        st.push(i);
    }
    
    for (int i = 1; i <= n; i++) 
    printf("%d ", ans[i]);
    return 0;
}

原文地址：https://blog.csdn.net/Sakura_ding/article/details/142391791

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！