专题整理：数据结构（1）

本博客包含：栈、队列、链表、堆、单调栈、单调队列等

一、引入概念：

什么是数据结构？

Pascal语言之父曾说过：算法+数据结构=程序，由此可以看出，在构建程序的过程中，数据结构和算法处于同等重要的位置。

那么什么是数据结构呢？

简单来说，数据结构就是计算机存储、组织数据的方式，这样说可能比较抽象，让我们先来认识最简单的两种数据结构

二、栈和队列：

2-1、栈----后进先出的数据结构

2-1-1、题目链接：https://www.luogu.com.cn/problem/P1739

2-1-2、题目描述：

假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。

2-1-3：思路：

这是一道比较简单的数据结构题，我们可以设置一个数组，每当找到一个“(”的时候，就将其放入数组中，然后每当找到一个")"的时候，查看数组中是否有“(”，有的话就删除最后放入的那个"("，否则的话就会产生一个不匹配的“)”，最后结束的时候，查看数组是否为空，不为空的话就存在不匹配的“(”。

像这样子将后放入的先取出的数据结构，我们称之为“栈(stack)“。

或者作个实际一点的比方：栈就相当于我们打羽毛球的球筒，它只有一个出入口，最晚放进球筒的羽毛球是最先被取出来使用的，如果不将上面的先行取出的话，就不可能将下面的拿出来。

2-1-4、数组模拟栈&&STL栈

我们可以用数组来模拟栈，模拟的时候显然需要一个top指针来指向数组末端，当取出的时候，就找到该指针对应的位置，删除的时候，就让指针前移一位，添加元素的时候就让指针后移一位，不过多赘述。

我们也可以用C++的STL直接使用栈。

STL（Standard Template Library）俗称标准模板库，它利用模板将各种数据结构都实现了一遍，在编程的时候可以直接使用，非常方便，本题题解对其使用方法进行了注释。

2-1-5、题解

#include 
#include
#include
#include
#include 
#include     //首先要包含栈的头文件 
#include  
using namespace std;
int main()
{
      stack<char> s;    //STL栈的声明方式，<>内是该栈存的数据类型。 
      char name;
      while(1)
      {
          cin>>name;
          if(name=='@') break;
          else if(name=='(') s.push(name);    //push()操作，即将元素压入栈顶 
          else if(name==')')
          {
              if(!s.empty())       //empty()操作,判断某栈是否为空，为空则返回1 
              {
                  s.pop();       //pop()操作，将栈顶元素弹出。 
              }
              else if(s.empty())   // 另外还有s.size()操作，返回的是栈的元素个数 
              {
                  cout<<"NO";
                  return 0;
              }
          }
      }
      if(!s.empty())
      {
          cout<<"NO";
      }
      else if(s.empty())  cout<<"YES";
      return 0;
}

2-2、队列----先进先出的数据结构

2-2-1、题目链接:https://www.luogu.com.cn/problem/P1540

2-2-2、题目描述:

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有

假设一篇英语文章的长度为

#include 
#include
#include
#include  
#include
#include 
#include 
#define N 1101
using namespace std;
int q[N];
bool vis[N];
int m,n,ans;
int head=0,tail=0;     //栈模拟需要一个位置（只有一个出入口）,而队列模拟就显然需要两个位置了。 
inline void read(int &p)
{
    p=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') p=p*10+(ch-'0'),ch=getchar();
}
int main()
{
    memset(vis,false,sizeof(vis));
    read(m);read(n);
    for(int i=1;i<=n;i++)
    {
        int a1;
        read(a1);
        if(false==vis[a1])
        {
            vis[a1]=true;
            q[++tail]=a1;
            ans++;
            if(tail-head>m) vis[q[++head]]=false;
        }
        else continue;
    }
    
    printf("%d",ans);
    return 0;
    
}

有一个长为

例如：

The array is

当场暴毙。

那么有没有什么更快的办法呢？

使用线段树的陈独秀同学你先坐下，让我们介绍一种基于队列的数据结构，单调队列。

所谓单调队列，有两个重要的性质：

1、队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

2、队列中元素的大小必须以某种方式单调。

有同学会说，老师老师，队列不能做到单调啊，毕竟做人要厚道，不能插队啊。

没错，做人确实不能够插队，但是不满足条件的我们可以不让他进队啊。

假如我们要求队列单调递增，那么最后一个同学要是比前一个矮的话，我们就把他请出队列。

这就是单调队列：可以支持从队首和队尾出队操作的数据结构。

那么这题我们就有了思路，我们维护两个单调队列（一大一小），队列中存放数字的下标。然后从前往后遍历，表示当前窗口末端的位置（将要判断的数字），如果符合单调性，就将其进队，然后判断队列中第一个数字的下标是否已经过期（窗口滑走）。

我们可以使用数组进行队列的模拟，这里我使用了STL中的双向链表(list)完成这题。

3-1-4、题解：

#include 
#include
#include
#include 
#include 
#include     //list一定要带上这个头文件
#include 
#define N 1000050
using namespace std;
int a[N];
int n,k;
int place;
list <int>lisma,lismi;

void read()
{
    int lib;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&lib);
        a[i]=lib;
                }
}

void bigg()
{
        for(int i=1;i<=n;i++)
    {
        if(lisma.empty())
        {
                    lisma.push_front(i);
                    continue;
            }
                        if(lisma.front()<=i-k)
            {
                lisma.pop_front();
                }
            while((!lisma.empty())&&(a[lisma.back()]<=a[i]))
            {
                lisma.pop_back();
                }
                lisma.push_back(i);
                    if(i>=k) printf("%d ",a[lisma.front()]);
        }
        
}

void samll()
{
            for(int i=1;i<=n;i++)
    {
        if(lismi.empty())
        {
        lismi.push_front(i);
        continue;
            }
            if((!lismi.empty())&&(lismi.front()<=i-k))
            {
                lismi.pop_front();
                }
            while((!lismi.empty())&&(a[lismi.back()]>=a[i]))
            {
                lismi.pop_back();
                }
                lismi.push_back(i);
                if(i>=k) printf("%d ",a[lismi.front()]);
        }
}
void wtf()
{
    for(int i=1;i<=n;i++)
    printf("%d ",a[i]);
}
int main()
{
    scanf("%d%d",&n,&k);
    read();
    if(k==1)
    {
        wtf();
        printf("\n");
        wtf();    
        return 0;
                }
    samll();
    printf("\n");
    bigg();
    return 0;
}

3-2、单调栈

3-2-1、题目链接：https://vjudge.net/contest/424167#problem/F

3-2-2、题目简介：

我之前写过一篇关于单调栈的基础题的博客，这里将连接贴出来，不再对这题过多赘述。

所谓单调栈，就是保证栈内元素单调性的一个栈，和单调队列不一样，单调栈是在原来栈的基础上增加了一个维护单调性的性质而已。

四、链表

4-1、题目简介

4-2、概念引入:

既然刚刚我们使用了双向链表(list)，我们就是趁热打铁来讲一讲链表。

假如我们要储存一组数据，我们应该怎么进行存储？

我们可以想到使用一个数组进行储存，但是假如我们要在数组的某一位插入某个元素呢？要是使用数组的话，就会造成从该位之后每一位都向后移动一位，同样，如果删除某一位的话，也会造成之后每一位都向前移动一位，这会造成极大的不方便。

而链表则是一种不连续的存储方式，每一个位置除了存储自身的数值，还保存了下一个位置的指针，这样每当进行插入操作的时候，只需要将上一个位置保存的指针指向当前插入的数值的位置，再将当前数值的位置指向下一个位置。

同理可以知道删除的操作方式。

4-3、题解：

#include 
#include
#include<string>
#include
#include
#include
#define N 1000510
using namespace std;
struct node{
    int pos,val,next;
};

node s1[N];//原始 
node change[N];//排列 
node che[N],del[N];//确定 删除 
int first,n;
bool vis[N];
int main()
{
    first,n;
    scanf("%d%d",&first,&n);
    for(int i=0;i)
    {
        int a;
        scanf("%d",&a);
        scanf("%d%d",&s1[a].val,&s1[a].next);
        s1[a].pos=a;
    }
    //排列 
    int indechange=0;
    while(first!=-1)
    {
         change[++indechange]=s1[first];
         first=s1[first].next;
    }
    
    int indeche=0,indexdel=0;
    for(int i=1;i<=indechange;i++)
    {
        if(!vis[abs(change[i].val)])
        {
            vis[abs(change[i].val)]=true;
            che[++indeche]=change[i];
        }
        else
        {
            del[++indexdel]=change[i];
        }
    }
    
    for(int i=1;i<=indeche;i++)
    {
        if(i==indeche) printf("%05d %d -1\n",che[i].pos,che[i].val);
        else printf("%05d %d %05d\n",che[i].pos,che[i].val,che[i+1].pos);
    }
    
    for(int i=1;i<=indexdel;i++)
    {
        if(i==indexdel) printf("%05d %d -1\n",del[i].pos,del[i].val);
        else printf("%05d %d %05d\n",del[i].pos,del[i].val,del[i+1].pos);
    }
    return 0;
}

4-4、STL之list和vector

STL中也用链表相应的数据结构，list是双向链表，实现方式是记录两个指针，分别指向上一个位置和下一个位置。

而vector(向量)，也可以视为一种可变化大小的动态数组，因此vector内部使用的是一整串的连续空间，所以vector可以使用下标对内部元素进行访问，而list如果想要访问第n个元素则需要使用迭代器。

五、堆

5-1、题目链接：https://www.luogu.com.cn/problem/P3378

5-2、题目简介：

5-3、思路&&引入概念

一个很简单的思路，就是每当数组尾部插入一个数字的时候，就不断将其前移，维护数组的单调递增的性质，显然这样子是十分繁琐复杂的，尽管我们可以使用二分法进行一点优化，但本质上还是没有什么太大的变化，我们引入堆的概念。

堆，本质上是一棵完全二叉树。堆的根部一定是优先级最大（或最小）（优先级可以是传统意义的大小，也可以是重载之后的优先级）的，而每一个节点的优先级都比其父节点要优先级更低。

树的相关知识在图论总结中讲过，不再赘述。

当我们插入某个节点到堆的末尾的时候，将其和父节点作比较，若优先级更高，就将其和父节点进行交换，以此维护堆的性质。

当我们删除根节点的时候（删除优先级最大或最小的元素），将根节点和最后一个叶子节点交换位置，然后不断下移根节点，将根节点和叶节点中优先级最大（最小）的进行交换，直到没有叶节点为止。

5-4、代码：

int main()
{
    read(n);
    while(n--)
    {
        read(p);
        switch(p)
        {
            case 1:
            {
                read(x);
                heap[++tot]=x;
                int pos=tot;
                while(pos>1)
                {
                    int posnext=pos/2;
                    if(heap[pos]>=heap[posnext]) break;
                    swap(heap[pos],heap[posnext]);
                    pos=posnext;
                }
                break;
            }
            case 2:
                {
                    printf("%d\n",heap[1]);
                    break;
                }
            case 3:
            {
                int lim=heap[1];
                heap[1]=heap[tot--];
                int pos=1;
                while(pos*2<=tot)
                {
                    if(heap[pos]<=heap[pos*2]&&heap[pos]<=heap[pos*2+1]) break;  //无法下沉 
                    int posnext=pos*2;
                    if(posnext1];
                    if(heap[pos]>heap[posnext]) swap(heap[pos],heap[posnext]);
                    pos=posnext;
                }
                break;
            }
        }
    }
    return 0;
 }

5-5、STL 的堆---优先队列

实际上，我们万能的STL中也有堆，在STL中，我们称为优先队列(priority queue)。

STL中的优先队列内部用堆来实现，其顶部就是优先值最大的元素，当我们插入某个元素的时候，他还会自动进行二叉树的下沉操作，十分便利。

还记得之前说过的堆的大小相对的是优先级别的大小吗？使用优先队列的时候，通过对大小于号的重载，可以做到对结构体等进行排序的效果，掌握之后可以让程序事半功倍。

代码：

#include 
#include
#include<string>
#include
#include
#include
#include
#include
#include    //这个头文件不能丢掉 
#include
#define N 10001
#define ll long long
using namespace std;
priority_queue<int,vector<int>,greater<int> >que;//这个是完全写法，greater是小根堆，less是大根堆。最后两个>中间一定要有个空格 
priority_queue<int>que1;//不写全默认是大根堆
int n,p,x;
inline void read(int &p)
{
    p=0;
    int f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') p=p*10+(ch-'0'),ch=getchar();
    p*=f;
}

//重载
struct node{
    int num1;
    int num2;
    friend bool operator<(node a,node b)
    {
        return a.num1//将小于号重载为比较a与b的num1的大小 
    }
}ed[N];
priority_queueque2;    //这个优先队列可以保存结构体，并且排序依据(优先级依据)是num1的大小 


int main()
{
    read(n);
    while(n--)
    {
        read(p);
        switch(p)
        {
            case 1:
            {
                read(x);
                que.push(x);
                break;
            }
            case 2:
                {
                    int lim=que.top();
                    printf("%d\n",lim);
                    break;
                }
            case 3:
            {
                que.pop();
                break;
            }
        }
    }
    return 0;    
}

专题数据结构 ACM