6--Pop Sequence

 题目大意：

        第一行输入M(栈的最大容量)\N(数字序列的最大数)\K(列出下面K行需要判断的情况)

        剩下K行输入1-7的排列组合(每个数字进一次),判断每行对于这个栈push和pop随机组合,能否出现本次的排列组合。能->YES  ,否->NO 

样例输入:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出：

YES
NO
NO
YES
NO

 思路分析:

        看能否出现此组合,暴力列出所有情况实属下策。正解--->模拟栈可能的操作.

       

        对于第一个数字(待测的序列p,以5 6 4 3 7 2 1为例)即5,那么栈肯定是依次压入了1、2、3、4、5然后pop出5。

        此后依次判断p[i-1]和p[i-1]的大小

        ①若前者小，说明肯定进行了相应的压入,比如对于6，5<6,那么栈的操作就是压入6(前面1-5已经使用过了,这里使用point依次++定位)，然后pop 6即可。

        ②若前者大，比如对于4，此时的栈中5和6已经pop了，那直接pop出一个num,看num是否等于p[i]即可。

注意：

        边界条件:栈不能超过M！！！，注意push之后判断一下是否越界

AC代码:

#include
#define ERROR -1
using namespace std;
 
class Stack
{
public:
    Stack(int c) :Capcity(c)
    {
        top = -1;
        Arr = new int[c];
    }
    int pop()
    {
        if (top == -1)return ERROR;
        return Arr[top--];
    }
    int GetTop()
    {
        return Arr[top];
    }
    void push(int data)
    {
        if (top == Capcity - 1)return;
        Arr[++top] = data;
    }
    bool isEmpty() { return top == -1; }
    int GetCapcity() { return Capcity; }
private:
    int* Arr;
    int Capcity;
    int top;
};
bool Judge(Stack stack, int* p, int len)
{
    int MaxLen = stack.GetCapcity();
    int count = 0;//看是否越
    int point = 1;//指针d,0-9从0-9按顺序push
 
 
    for (int i = 0; i < len; i++)
    {
        if (i != 0 && p[i] < p[i - 1])
        {
            int c = stack.pop();
            count--;
            if (c != p[i])return 0;
        }
        else
        {
            for (; point <= p[i]; point++)
            {
                stack.push(point);
                count++;
                if (count == MaxLen + 1)return 0;
            }
            stack.pop(); count--;
        }
    }
    return 1;
}
int main()
{
    int M, N, K;
    cin >> M >> N >> K;
    Stack stack(M);
    int* pArr = new int[N];
    for (int i = 0; i < K; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> pArr[j];
        }
        if (Judge(stack, pArr, N))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}