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!”。

样例输入

样例输出

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;
        }
    }
}

秒客网

c++ 栈的基本应用