Discussion and legitimacy of the order of entering and leaving the stack

The characteristic of stack is first in first out . However, it should be noted that this feature is only established under normal conditions and normal operation , What is normal and what is abnormal ？

 

The so-called normal operation ： Pressing all data into the stack in strict order and then pressing it out of the stack in turn is normal routine operation . For example, we bring a set of data ：1,2,3,4,5; After they are put into the stack, the order of getting out of the stack is naturally 5,4,3,2,1.

Then what will happen 4,5,3,2,1 Out of stack order ？ Most people who are exposed to this kind of situation for the first time may think there is a problem , Problems like mistakes , Then you have to think , Is it strict input stack operation ？ In other words, whether it is in order out of the stack into the stack ？ The problem is solved ！

analysis ： Let's put... First in the normal order 1,2,3,4 Push to stack , Then the key steps came , At this time, put 4 Press out stack ,4 Is the first one out of the stack ; And then put 5 Push , Finally, stack in order , Then the final stack order we get is 4,5,3,2,1.

Do an exercise ：

---

The stack sequence of a stack is a,b,c,d,e Then the impossible output sequence of the stack is ：（）
 
A edcba         B decba           C dceab            D abcde 

---

  I put the answer analysis at the end .

Look at the following question

---

Stack and queue 7 of data structure experiment ： Stack sequence determination

Description

Give an initial stack sequence , The second order is the stacking order of elements , The top element of the stack can be out of the stack at any time , Each element can only be put on the stack . Enter a stack sequence , Then enter multiple sequences in turn , Please judge whether these sequences are legal stack sequences for the given stack sequence .

For example, the sequence 1,2,3,4,5 Is the push order of a stack , Sequence 4,5,3,2,1 It is a stack out sequence corresponding to the stack pressing sequence , but 4,3,5,1,2 It can't be the out of stack sequence of the sequence . Suppose that all the Numbers pushed are not equal .

Input

Enter the integer in the first line n(1<=n<=10000), Represents the length of the sequence .

Second line input n It's an integer , Indicates the pressing order of the stack .

In the third line, enter the integer t（1<=t<=10）.

Input in sequence t That's ok , Each row n It's an integer , Represents each out of stack sequence to be judged .

Output

Output one line for each test case , If the initial stack sequence can be obtained, the stack sequence , The output yes, Otherwise output no.

Sample

Input 

5
1 2 3 4 5
2
4 5 3 2 1
4 3 5 1 2

Output 

yes
no

Code ：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,m,a[10001],b[10001];
    cin>>n;
    for(i=0; i<n; i++)
        cin>>a[i];
    cin>>m;
    while(m--)
    {
        stack<int> st;
        for(i=0; i<n; i++)
            cin>>b[i];
        int key_a=0,key_b=0;
        while(key_b<n)
        {
            if(st.empty())
                st.push(a[key_a++]);
            else
            {
                if(st.top()!=b[key_b])
                {
                    if(key_a<n)
                        st.push(a[key_a++]);
                    else
                        break;
                }
                else
                {
                    st.pop();
                    key_b++;
                }
            }
        }
        if(st.empty())
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

C 

Analyze the answers one by one ,A Options are the result of the normal order in and out of the stack as we mentioned above ;B We have also analyzed the options, which are the examples at the beginning of the article ;D The result of the option is to press in one and pop up one ;C Options , Let's analyze ab The order after , Out of the stack for dce We can understand it as pressing d Pop up after d, In the pop-up c, Then press e eject e, No problem, we can guarantee cde Stack order of , that b stay a Then put on the stack , It's impossible to compare a Post stack so error .