Skip to content

13012: 【原3012】Stack Overflow?

题目

题目描述

author: pigoneand 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3012

Description

这是最好的代码,这是最差的代码。二哥望着眼前得到的国家浮云计算中心内核代码叹息不已。 你知道国家浮云计算中心内核代码最后一页写着什么吗? } } … … }

都是}。 二哥心碎了,他决定出一道简单题考考这帮程序员,看看他们究竟有多少实力。

这道题目很简单,二哥请你模拟一个堆栈的运行。

Input Format

Line 1: 一个整数N,表示有N个操作。(1 <= N <= 1,000)

Lines 2..N+1: 每行两个整数,op, num。 op表示操作符,op = 1表示在堆栈中压入一个新的整数num。 op = 2表示在堆栈中弹出最上面存储的整数,并与num进行比较。(1 <= num <= 1,000)

Output Format

N行。每行一个字符串,表示对应N个操作的运行结果。

如果 op = 1,则直接输出一行OK 如果 op = 2,如果堆栈中此时没有元素,输出ERROR,并忽略这次操作。如果有元素,弹出最上面元素,并返回与num比较之后的结果。 如果相等,输出YES,反之输出NO

Sample Input

5
1 100
1 200
2 200
2 300
2 100

Sample Output

OK
OK
YES
NO
ERROR

Pangbo13's solution

#include<iostream>
using namespace std;

template <class elemType>
class stack{
    public:
        virtual bool isEmpty() const = 0; //判栈空
        virtual void push(const elemType&x) = 0; // 进栈
        virtual elemType pop() = 0; // 出栈
        virtual elemType top() const = 0; // 取栈顶元素
        virtual ~stack() {} //虚析构函数
};
template <class elemType>
class seqStack: public stack<elemType>{
    private:
        elemType *elem;
        int top_p;
        int maxSize;
        void doubleSpace();
    public:
        seqStack(int initSize = 10);
        ~seqStack();
        bool isEmpty() const;
        void push(const elemType &x);
        elemType pop();
        elemType top() const;
};

template <class elemType>
seqStack<elemType>::seqStack(int initSize){
    elem = new elemType[initSize];
    maxSize = initSize ;
    top_p = -1;
}
template <class elemType>
seqStack<elemType>::~seqStack(){
    delete[] elem;
}
template <class elemType>
bool seqStack<elemType>::isEmpty() const{
    return top_p == -1;
}
template <class elemType>
void seqStack<elemType>::push(const elemType &x){
    if(top_p == maxSize -1) doubleSpace();
    elem[++top_p] = x;
}
template <class elemType>
elemType seqStack<elemType>::pop(){
    return elem[top_p--];
}
template <class elemType>
elemType seqStack<elemType>::top() const{
    return elem[top_p];
}
template <class elemType>
void seqStack<elemType>::doubleSpace(){
    elemType *tmp = elem;
    elem = new elemType[2 * maxSize ];
    for (int i = 0; i < maxSize; ++i) elem[i] = tmp[i];
    maxSize *= 2;
    delete [] tmp;
}
int main(){
    int N,op,num;
    seqStack<int> s;
    cin>>N;
    for(int i = 0;i<N;i++){
        cin>>op>>num;
        switch(op){
            case 1:
                s.push(num);
                cout<<"OK"<<endl;
                break;
            case 2:
                if(s.isEmpty()) cout<<"ERROR"<<endl;
                else{
                    if(s.pop() == num) cout<<"YES"<<endl;
                    else cout<<"NO"<<endl;
                }
        }
    }
}

satgo1546's solution

#include <stdio.h>

int a[1005];
int i = 0;

int main(int argc, char *argv[]) {
    scanf("%d", &argc);
    while (argc--) {
        int op, b;
        scanf("%d%d", &op, &b);
        puts(op == 1 ? a[i++] = b, "OK" : i ? a[--i] == b ? "YES" : "NO" : "ERROR");
    }
    return 0;
}