[数据结构与算法]2021/12/15学习总结

文章目录

1.知识点学习

2.代码编写

一.知识点学习

今日学习了栈、队列、链表的相关知识点，由于栈和队列的内容相对较少，目前对栈和队列的掌握较为牢固，但链表的知识仍有所欠缺。

栈:一种后进先出的数据结构，栈限定为只能在一段进行插入和删除操作，将数据放入栈中的操作称为“入栈”（push)，将数据从栈中取出的操作称为“出栈”（pop）。

队列：一种先进先出的数据结构，一般使用head来记录队列的队首，tail记录队尾的下一位。

二.题目练习

由于今天满课，选修课也有个结业考试，今天实在没有太多时间刷题了。。。

G

给出一个由1到n组成的无序数列，如果我们把这个序列看成是数字1~n出栈的顺序，并且入栈顺序是1, 2, 3, ..., n，请问操作时，栈内最多能有多少个元素？

Input

输入有多组数据。

每组数据的第一行为一个整数n代表由1到n的序列。 1<= n ?<=100。

第二行为n个用空格隔开的整数，范围是[1,n]。

Output

若此序列能由进栈，出栈得到，输出所使用的最小栈容，否则输出-1

Sample Input

5
1 2 3 4 5
4
3 2 1 4
6
6 5 4 1 3 2

Sample Output

1
3
-1

#include <stdio.h>
int main ()
{
    int n,a[100],stack[100];
    while(~scanf("%d",&n))
    {
        int max=0,top=0,k=1;  //定义最大次数，栈顶，标记数 
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(int i=0; i<n; i++)
        {
            while(k<=a[i])//将小于等于a[i]的自然数都入栈 push
            {
                stack[top++]=k;
                k++;
            }
            if(top>max)
                max=top;
            if(a[i]==stack[top-1])//将a[i]出栈 pop
            {
                top--;  //栈顶降为前一个数 
            }
        }
        if(top==0)  //即次序列能由进栈，出栈得到 
            printf("%d\n",max);
        else
            printf("-1\n");
    }
    return 0;
}