hdoj 1022 Train problem 1【栈的理解】

深碍√TFBOYSˉ_ 2022-08-04 10:46 101阅读 0赞

栈 的理解

栈，又名堆栈，最鲜明的特点就是其先进后出的方式（Last-In First-Out,LIFO）。

相信各位都知道枪这种神奇的东西吧！其实吧，那个栈和枪械的部分原理很相似，就比如把子弹往弹匣里添；![Center][]![Center 1][]![Center 2][]

这就如同元素入栈，最早进去到在最底部，最晚进去的在最顶部；弹匣填满后就可以上枪击发了（没添满也可以上枪击发，若想打一枪，再往弹匣里添子弹，那也是可以滴）

![Center 3][]![Center 4][]

正如我们所看到的，在弹匣顶部的子弹先被击发，就如同栈顶元素出栈一般。

具体介绍：  
    栈是限定仅在表位进行插入和删除的线性表。需要注意的是，首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继的关系只不过它是一个特殊的线性表而已。它的特殊之处就在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行（就像枪的撞针，只击发弹匣顶部的子弹）。这也就使得：栈底是固定的，最先进站的只能被压在栈底。从而导致了栈的基本特点是“先进后出（FILO）”。  
相应的操作：  
   STL的栈定义在头文件<stack>中，故使用前得写 \#include<stack>  
 stack<int>s;  //定义一个整型的栈  
 s.pop()；   //删除栈顶元素（就如同枪的撞针击发弹匣顶部的子弹的过程）  
 s.push(i);   //添加元素i（如同往弹匣里压子弹）  
 s.top();    //指向栈顶元素

今天来道题

# Train Problem I #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 26460    Accepted Submission(s): 9996**

Problem Description

略  
![1022-1.jpg][] ![1022-2.jpg][] ![1022-3.jpg][]

Input

略

Output

略

Sample Input

3 123 321
    3 123 312

Sample Output

Yes.
    in
    in
    in
    out
    out
    out
    FINISH
    No.
    FINISH

题目大意：给你一个整数n，空格，给两个n元素数列，问能不能利用栈把第一数列变成第二数列；

下面为Accept的代码

改代码是用栈和数组做的

#include<cstdio>
    #include<stack>
    #include<cstring>
    using namespace std;
    int n,i,j,k;
    int f[30];
    char in[20],out[20];
    int main(){
        stack<char>s;
        while(scanf("%d %s%s",&n,in,out)!=EOF){
            while(!s.empty()) s.pop();               //注意初始化
            memset(f,-1,sizeof(f));
            k=0;
            j=0;
            for(i=0;i<n;i++){
                s.push(in[i]);
                f[k++]=1;
                while(!s.empty()&&s.top()==out[j]){
                    f[k++]=0;
                    s.pop();
                    ++j;
                }
            }
            if(j==n){
                printf("Yes.\n");
                for(i=0;i<k;i++){
                    if(f[i]==1)
                        printf("in\n");
                    else
                        printf("out\n");
                }
            }
            else
                printf("No.\n");
            printf("FINISH\n");
        }
        return 0;
    }

闲来没事，又用栈加队列做了一遍\{  
下面为Accept代码

#include<cstdio>
    #include<cstring>
    #include<stack>
    #include<queue>
    using namespace std;
    char act[25][5];
    char in[25],out[25];
    
    int main(){
        stack<int>s;
        queue<int>q;
        int n;
        while(scanf("%d",&n)!=EOF){
            while(!s.empty()) s.pop();                    //
            while(!q.empty()) q.pop();                    //在这两个地方wa了一次，之前用的是if，所以错了，都怪自己心太粗了
            scanf("%s",in);
            scanf("%s",out);
            for(int i=0;i<n;i++){
                int x=in[i]-'0';
                q.push(x);
            }
            int i,t=0,k=0;
            for(i=0;i<n;i++){
                if(!s.empty()){
                    int x=s.top();
                    if((out[i]-'0')!=x){
                        if(q.empty()) break;
                        s.push(q.front());
                        q.pop();
                        strcpy(act[k++],"in");
                        i--;
                    }
                    else{
                        strcpy(act[k++],"out");
                        s.pop();
                    }
                }
                else{
                    if(q.empty()) break;
                    s.push(q.front());
                    q.pop();
                    strcpy(act[k++],"in");
                    i--;
                }        
            }
            if(i==n){
                printf("Yes.\n");
                for(int j=0;j<k;j++)
                    printf("%s\n",act[j]);
            }
            else
                printf("No.\n");
            printf("FINISH\n");
            
        }
        return 0;
    }

用的是Dev C++ 5.8.3编译的

欢迎评论

读者如有意见或建议，可联系博主

qq：1328705994

[Center]: https://img-blog.csdn.net/20150822231251883?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20150822231312523?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20220731/c993bd13b07d429fbcec27a259a830cc.png
[Center 3]: https://img-blog.csdn.net/20150822231703673?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: /images/20220731/e52f05629c414745a2a9f0aa4bb5559c.png
[1022-1.jpg]: http://acm.hdu.edu.cn/data/images/1022-1.jpg
[1022-2.jpg]: http://acm.hdu.edu.cn/data/images/1022-2.jpg
[1022-3.jpg]: /images/20220731/60b473bb30b244158022337ffd7574e9.png