博客

唔…这道题如果要强行用数组做也很简单…不过既然要小伙伴们练一练

栈

这货怎么用，那就老老实实地

栈

着吧……

广告一枚…第一次尝试边

边写代码…感觉还可以……

回归正题，关于栈的定义，不外乎这些元素：数据存储空间，栈内元素标记以及操作函数。一个比较简明的定义如下面：

template <class T>
class myStack
{
public:
    myStack(int x);
    T push(T x);
    T pop();
    bool isEmpty();
    ~myStack();
private:
    T* data;
    int num;
};

有了栈我们就好办啦！按照输入不断地Push、Pop就可以。


注意这一点


：如果栈下溢出了，不要直接Break掉循环，因为下面还会有输入，我们应该做的是继续读入下面的命令而不去执行它，这样就可以避免一次又一次不知原因的WA……

AC代码在下面：

#include <iostream>
#include <string.h>

using namespace std;

template <class T>
class myStack
{
public:
    myStack(int x)
    {
        data = new T[x];
        num = 0;
    }
    T push(T x)
    {
        data[num] = x;
        num++;
        return x;
    }
    T pop()
    {
        if(num > 0)
            num--;
        return data[num];
    }
    bool isEmpty()
    {
        return num == 0;
    }
    bool show()
    {
        int i;
        if(num == 0)
            return false;
        for(i = 0 ;i < num - 1; i++)
        {
            cout << data[i] << " ";
        }
        cout << data[num - 1] << endl;
        return true;
    }
    ~myStack()
    {
        delete data;
    }
private:
    T* data;
    int num;
};

int main()
{
    int i, j;
    int m;
    cin >> m;
    for(i = 0; i < m; i++)
    {
        int n, num;
        char op[16];
        bool flag = true;
        myStack<int> obj(128);
        cin >> n;
        for(j = 0; j < n; j++)
        {
            cin >> op;
            if(strcmp(op, "pop") == 0)
            {
                if(obj.isEmpty())
                {
                    flag = false;
                    continue;
                }
                else
                {
                    obj.pop();
                }
            }
            else
            {
                cin >> num;
                obj.push(num);
            }
        }
        if(flag)
            obj.show();
        else
            cout << "error" << endl;
    }
    return 0;
}

原谅我吧我懒了不想写注释……下面是惯例君带来的原题：

总时间限制:
    1000ms
内存限制:
    1000kB

描述

    栈是一种重要的数据结构，它具有push k和pop操作。push k是将数字k加入到栈中，pop则是从栈中取一个数出来。

        栈是后进先出的：把栈也看成横向的一个通道，则push k是将k放到栈的最右边，而pop也是从栈的最右边取出一个数。

        假设栈当前从左至右含有1和2两个数，则执行push 5和pop操作示例图如下：

                  push 5          pop

        栈   1 2  ------->  1 2 5 ------>  1 2

        现在，假设栈是空的。给定一系列push k和pop操作之后，输出栈中存储的数字。若栈已经空了，仍然接收到pop操作，

        则输出error。

输入
    第一行为m，表示有m组测试输入，m<100。
    每组第一行为n，表示下列有n行push k或pop操作。（n<150）
    接下来n行，每行是push k或者pop，其中k是一个整数。
    （输入保证同时在栈中的数不会超过100个）
输出
    对每组测试数据输出一行。该行内容在正常情况下，是栈中从左到右存储的数字，数字直接以一个空格分隔，如果栈空，则不作输出；但若操作过程中出现栈已空仍然收到pop，则输出error。
样例输入

    2
    4
    push 1
    push 3
    pop
    push 5
    1
    pop

样例输出

    1 5
    error