普及组Day3教案

栈：栈就是先进后出，比如我把数字3、5、2放入栈中，然后第一次从栈中取出来的数字是2，然后取出来的数字是5，这时如果再向栈中放入数字9，下一次取出来的数字是9，再下次取出来的数字是3，这时候栈空了。栈可以想象成一个大坑，先放进去的东西在下面，后放进去的东西在上面，取东西时上面的东西先被取出来。

用数组模拟栈：

int stack[100], t;
void push(int x) {
    stack[t++] = x;
}
int pop() {
    return stack[--t];
}

队列：队列就是先进后出，就像排队一样，先到的人先出来。比如把3、5、2放入队列中，第一次出队的数是3，然后是5，接下来让9入队，下一个出队的数是2，再下一个出队的数是9，然后队列空。

用数组模拟队列：

int queue[100], head, tail;
void push(int x) {
    queue[tail++] = x;
}
int front() {
    return queue[head];
}
void pop() {
    head++;
}

链表：Luogu P1160 队列安排

#include<cstdio>
#include<cstring>
int a[100010][3],n,m;
//a[i][2]表示学号为i的同学右边同学的学号
//a[i][3]表示学号为i的同学左边同学的学号
int main()
{
    scanf("%d",&n); int j=1;
    memset(a,0,sizeof(a)); a[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        int x,y; scanf("%d %d",&x,&y);
        a[i][1]=i;
        if(y==0)
        //插入左边
        { 
            a[a[x][3]][2]=i; a[i][2]=x;
            a[i][3]=a[x][3]; a[x][3]=i;
            if(x==j) j=i;
            //比较麻烦，要改链表
        }
        else
        //插入右边
        {
            a[i][2]=a[x][2]; a[a[x][2]][3]=i;
            a[x][2]=i; a[i][3]=x;
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x; scanf("%d",&x);
        if(a[x][1]!=0)
        //该同学还在 
        {
            a[x][1]=0;
            //踢掉……(好可怜) 
            a[a[x][3]][2]=a[x][2];
            a[a[x][2]][3]=a[x][3];
            n--;
            if(x==j) j=a[x][3];
        }
    }
    int i=1,x=j;
    while(i<=n)
    {
        printf("%d ",a[x][1]);
        x=a[x][2]; i++;
    }
    return 0;
}