首页 > 代码库 > 简单的数据结构5.1--------(没整理完)

简单的数据结构5.1--------(没整理完)

1、栈

(1)栈的模拟

特点:先进后出

eg1:火车进站

实际就是模拟一个栈

技术分享
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int Stack[maxn],a[maxn],stack[maxn],n,l=1;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n;i++)
    {
        while(a[i]>=l)
        {
            Stack[++n]=l;
            l++;
        }
        if(Stack[n]==a[i])
        {
            n--;
        }
        else
        {
            printf("Wrong!");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
 } 
火车进栈

(2)单调栈

是栈的一个特殊用法 只是栈中的元素是单调即有序的 当加入一个新元素时,如果在栈顶加入这个元素不满足单调 就弹出栈顶元素 直至加入这个元素满足单调

eg1:noip2008 双栈排序

技术分享
 1 #include<cstdio> 
 2 #include<iostream>   
 3 #include<algorithm> 
 4 using namespace std;
 5 
 6 int p [1010],col[1010],Min[1010],pai[3][1010],l[3]; //p存进栈顺序  ,col为颜色,Min下文有说;
 7                                                      //pai为两个单栈,l 为两个单栈内的个点数;
 8                                                      
 9 int wei[10010],las[10010],too[10010];               //哈希表:wei:点在表中最后记录位置;
10                                                      //        las:某位置在表中上一记录位置;
11                                                      //        too:存冲突对象;
12                                                      
13 int n,should=1;                                      //should为该出栈的点;
14 
15 void line(int x,int y) {                             //将冲突点连起来
16   las[++t] = wei[x]; wei[x] = t; too[t] = y;         //记录上一记录位置,再更新位置,存取冲突点
17   las[++t] = wei[y]; wei[y] = t; too[t] = x;
18 }
19 
20 void draw(int x,int c) {                             //将x 染成颜色 c(1~2)
21   if (!col[x]   )  col[x]=c;             else
22   if ( col[x]!=c) {printf("0");exit(0);} else return;//如果x 有颜色且不为 c那么就无解
23   for (int i=wei[x]; i; i=las[i]) draw(too[i],3-c);     //将与它冲突的点,染上另一个颜色
24 }
25 
26 int main() {
27   scanf("%d",&n);  
28   for (int i=1  ; i<=n; i++) scanf("%d",&p[i]);
29   
30   Min[n] =  p[n];                             //求第 i ~ n 点中最小的点Min[i] 
31   for (int i=n-1; i>=1; i--) 
32    Min[i]=min(Min[i+1],p[i]); 
33                    
34   pai[1][0]=1002;  col[n+1]=1 ;               //初始化栈顶边界、栈底边界
35   pai[2][0]=1002;  p[n+1]=1001;               //对最后一位元素之后那位处理以便最后把所有元素压出栈
36                    
37   for (int i=1  ; i<=n-2; i++)
38   for (int j=i+1; j<=n-1; j++) 
39   if  (p[i]<p[j]&&Min[j+1]<p[i]) line(i,j);   //枚举每对点,如果有冲突,则连线(代表冲突) 
40   
41   for (int i=1  ; i<=n  ; i++)                //进行染色,即分成两个客栈,然后同时进行单栈排序
42   if  ( !col[ i ] )  draw(i,1);
43   
44   //科学的打法是进行abcd优先判定的贪心模拟,以下是伤心病况的不科学打法— —!
45   for (int i=1  ; i<=n+1; i++) {              //模拟单栈排序,两个同时进行,到n+1是为了所有元素出栈
46     while (1)                                 //能出就出
47     if ( pai[1][l[1]] == should ) {should++; l[1]--; printf("b ");} else
48     if ( pai[2][l[2]] == should ) {should++; l[2]--; printf("d ");} else break;
49     pai[ col[i] ][ ++l[ col[i] ] ]=p[i];      //进栈(就是这行!!!!发现了吗!!!!!!)
50     if (i<n+1) printf("%c ", char(2*col[i]+95) );
51   }  
52 }
网上摘的

思路过程:双栈排序与一栈排序(火车进站)的区别

eg2:usaco乱头发节

统计每头牛被看到的次数。维护一个递减的栈。那样加入一个新元素,比他小的元素都被从栈中弹出。栈中剩下的元素个数就是能看到当前牛的牛的个数。

技术分享
#include<cstdio>
const int N=80000;
int n,x,s[N],top;
long long ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        while(top&&s[top]<=x)top--;
        ans+=top;//栈底从1开始,这样top就是元素,很方便
        s[++top]=x;
    }
    printf("%lld",ans);
    return 0;
}
AC

2、队列

(1)单调队列

滑动的窗户

技术分享
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}
    return x*f;
}
int n,K;
int a[1000005];
int q1[1000005],q2[1000005];
int ans1[1000005],ans2[1000005];
int l1=1,l2=1,r1,r2;
int main()
{
    //freopen("window.in","r",stdin);
    //freopen("window.out","w",stdout);
    n=read();K=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)
    {
        while(l1<=r1&&q1[l1]<=i-K)l1++;
        while(l2<=r2&&q2[l2]<=i-K)l2++;
        while(l1<=r1&&a[i]<a[q1[r1]])r1--;
        q1[++r1]=i;
        while(l2<=r2&&a[i]>a[q2[r2]])r2--;
        q2[++r2]=i;
        ans1[i]=a[q1[l1]];
        ans2[i]=a[q2[l2]];
    }
    for(int i=K;i<=n;i++)printf("%d ",ans1[i]);
    puts("");
    for(int i=K;i<=n;i++)printf("%d ",ans2[i]);
    return 0;
}
黄学长的code

(2)堆

闵梓轩学长今天讲的数据结构

讲题的特点:

先想暴力 后优化

先有需求 后有数据结构 数据结构是通过处理数据来优化算法的

简单的数据结构5.1--------(没整理完)