c++ 栈的基本应用

时间:2022-10-04 19:18:06

c++ 栈的基本应用

题目描述

记忆力大考验

小哼和小哈是一对兄妹,爸妈不在家的时候,小哼自然而然就担负起了照顾妹妹的责任。可别看小哼年纪小,他哄妹妹可有一手呢。今天,小哼就发明了一个小游戏来和小哈玩:
家里有一个长长的网球筒,还有一堆的网球,网球筒的直径很小,每次只能放进一个网球。小哼把每个网球都编了号(所有网球编号不一样),小哼有两种选择:第一种,拿一个小球放进球筒里;第二种,小哼会从球筒里拿出一个网球。而小哈要做的,就是每次小哼从球筒里拿出网球之前,凭记忆力猜出拿出来的网球编号是多少。

c++ 栈的基本应用

输入

输入包括多行,每行描述一条操作信息:
1.输入字母’I’,后面紧跟着一个整数x(1<=x<=100),表示当前要在球筒中放入编号为x的球;
2.输入字母’O’,表示当前要从球筒里拿出一个球。

输出

输出拿出网球的顺序,每个编号占一行,如果在取球的时候,球筒中已经没有球,请输出” Empty!”。

样例输入

O
I 6
I 4
O
I 7
I 1
O
I 8
O
O
O
O

样例输出

Empty!
4
1
8
7
6
Empty!

提示

c++ 栈的基本应用

代码

#include <bits/stdc++.h>
using namespace std;
long long q[10000000];
char tmp[10];
int f;
int main()
{
    memset(q,0,sizeof(q));
    char c;
    while (scanf("%c",&c) != EOF)
    {
        long long x;
        if (c == 'I')
        {
            printf("输入 : ");
            cin >> x;
            f ++;//f是栈里球的个数  
            q[f] = x;
        }
        else
        {
            if (f != 0)
            {
                printf("输出 : ");
                printf("%lld\n",q[f]);
                f --;//拿出最后放入的那个球 
            }
            else
            {
                printf("输出 : ");
                printf("Empty!\n");
            }
        }
        gets(tmp);
    }
} 

记忆力大考验升级版

题目描述

游戏进行到一半,小(贱)哈(人)突然有了一个想法:不能老是让小哼考自己呀,现在让我来考考他吧……于是,游戏有了下面这个版本:
小哈会给出一个放球的顺序,和一个拿球的顺序,小哼需要快速地实现。但是,玩着玩着,小哼发现问题没这么简单,有些序列根本就没有办法做到。现在,把两个序列都告诉你,请你先帮小哼预判一下他能不能做到。
c++ 栈的基本应用

输入

输入数据有多组(不会超过100组):
第一行输出一个整数n,表示现在有n个球(1<=n<=100);
接下来输入两行,每行n个数(所有的数不超过int范围),分别表示放球的顺序和拿球的顺序。

输出

对于每组数据,如果可以实现,输出:”YES!”,否则输出:”NO!”。

样例输入

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

样例输出

YES!
NO!

提示

c++ 栈的基本应用

Code

#include <bits/stdc++.h>
using namespace std;
int a[101],b[101],s[101],n;
int p,e;
int main()
{
    bool flag = 0;
    while (scanf("%d",&n)!= EOF)//一直读到文件末尾 
    {
        for (int i = 1;i <= n;i ++)//输入 
        {
            cin >> a[i];
        }
        for (int i = 1;i <= n;i ++)//输入 
        {
            cin >> b[i];
        }
        p = 1;e = 0;//e是栈的下标   p是从a[]中拿的顺序   
        for (int i = 1;i <= n;i ++)
        {
            int key = b[i];//key 是现在要 取得数字 
            while (s[e] != key && p <= n)//如果 正在放入的数字 等于你要取出的数字(key) 
            {
///////////把数字放到栈里面/////////////////// 
                e ++; 
                s[e] = a[p];
                p ++;
///////////把数字放到栈里面完毕/////////////////// 
            }
            if (s[e] == key)//把这个数字从栈里面删掉 
            {
                e --;//删除 
            }
            else
            {
                flag = 1;//发现不可行 
                break;
            }
        }
        if (flag == 1)
        {
            cout << "NO!" << endl;
        }
        else
        {
            cout << "YES!" << endl;
        }
    }
}