关于混合栈操作的问题？

Question

假设某个用列程序会进行一系列入栈和出栈的混合栈操作。入栈操作会将整数0到9按顺序压入栈；出栈操作会打印出返回值。下面哪种序列是不可能产生的？

• A: 4 3 2 1 0 9 8 7 6 5

• B: 4 6 8 7 5 3 2 9 0 1

• C: 2 5 6 7 4 8 9 3 1 0

• D: 4 3 2 1 0 5 6 7 8 9

• E: 1 2 3 4 5 6 9 8 7 0

• F: 0 4 6 5 3 8 1 7 2 9

• G: 1 4 7 9 8 6 5 3 0 2

• H: 2 1 4 3 6 5 8 7 9 0

先谈谈我自己的思路吧：
栈是个先进后出的数据结构，其次入栈时会将这些整数按照顺序压入，那么出栈时必定也是按照顺序出来的。因此E and A and D可以直接排除了。
接下来我就楞B了..因为我觉得都不可能产生的。但又觉得题目应该没这么简单..
我是一枚刚学算法的菜鸟，还望各位大牛不吝指教。先在此谢过！

Answer 1

这应该是个程序题而非心算题。写个程序，两个参数，一个是0-9序列，一个是结果序列。然后按照结果序列把出入栈操作推演一遍

Answer 2

谢邀，这题是可以心算的

一个评判标准: 某数 a 右侧所有比 a 小的数构成的子列必须严格降序。

Answer 3

解决了
先说思路【相当于两个数组，A是你要测试是否合法范例，B是0到9的顺序排列。从B的第一个和A的第一个相比，不同的话就将B入栈，然后B++，再和A比，比到相同为止。我是先入栈了之后再比，这样会有一个出栈的过程。出栈之后A++，B--，然后A和B再次相比，重复上面的步骤】
【说的还是很混乱...欸...】
贴一下代码
c语言的

#include<stdio.h>  
#include <stdlib.h>
 
#define StackSize 1000  
typedef struct{  
    int data[StackSize];  
    // 用于指向栈顶元素  
    int top;  
}SeqStack,*Stack;  
  
void Push(Stack Ptr,int item)
{
    Ptr->data[++(Ptr->top)] = item;
} 

int Pop(Stack Ptr)
{
    if(Ptr->top == -1)
    {
        printf("栈空");
        return 0;
    }
    else
    {
        return    Ptr->data[(Ptr->top)--];
    }

} 
  
int main()  
{  
    int n,i,input,count=0,tag=1,out;  
    Stack S =  (Stack)malloc(sizeof(SeqStack));  
    scanf("%d",&n);  
    S->top = -1;
    for(i=0;i<n;i++)  
    {  
        if(S->top >  n)
        {
            break;
        }
    
        if(tag == 1)
        {
            Push(S,++count);
        }

        scanf("%d",&input);  

        while(S->data[S->top] != input)
        {
            if(S->top >  n)
            {
            
                break;
            }

            tag =1;
            Push(S,++count);
        }
        if(S->data[S->top] == input)
        {
            out = Pop(S);
            tag = 0;
            continue;
        }
        
    }  

    if(S->top == -1)
    {
        printf("Yes");
        
    }else
        printf("No");
}  

我的写的比较繁琐，思路还不是很清晰
贴一下同学的

#include<stdio.h>
int train1[1000], train2[1000];
int main()
{
    int i, n, p=0, top = 0;
    scanf("%d",&n);
    for (i = 0; i < n; i++)
    {
        scanf("%d",&train2[i]);
        train1[top++] = i+1;
        while (train2[p] == train1[top-1])
        {
            p++;
            top--;
            if (top == 0){
                break;
            }
        }
    }
    if (top == 0)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

Answer 4

思路：根据打印出的序列，逆向推出栈中原本的出入栈顺序。根据值小的元素必然比值大的元素先入栈，若推到出的结果与此相反则该打印序列是错误的。

#! /usr/bin/env python

# -*- coding:utf-8 -*-

from queue import Queue


class Stack:
    """模拟栈"""
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items)==0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        if not self.isEmpty():
            return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

def init_queue():
    l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    q = Queue(10)

    for n in l:
        q.put(n)

    return q


def do(_list):
    out_stack = Stack()
    in_queue = init_queue()

    x = 0
    for num in test_list:
        if num >= x:
            while True:
                y = in_queue.get(block=False)
                x += 1
                out_stack.push(y)
                if y == num:
                    out_stack.pop()
                    break
        else:
            if out_stack.isEmpty() or out_stack.peek() != num:
                print 'wrong list'
                exit(0)
            else:
                out_stack.pop()

    print 'good list'




if __name__ == '__main__':

    # test_list = map(int, '0 4 6 5 3 8 1 7 2 9'.split())
    test_list = map(int, '4 3 2 1 0 9 8 7 6 5'.split())
    # test_list = map(int, '4 6 8 7 5 3 2 9 0 1'.split())
    # test_list = map(int, '2 5 6 7 4 8 9 3 1 0'.split())
    # test_list = map(int, '4 3 2 1 0 5 6 7 8 9'.split())
    # test_list = map(int, '1 2 3 4 5 6 9 8 7 0'.split())
    # test_list = map(int, '0 4 6 5 3 8 1 7 2 9'.split())
    # test_list = map(int, '1 4 7 9 8 6 5 3 0 2'.split())
    # test_list = map(int, '2 1 4 3 6 5 8 7 9 0'.split())

    do(test_list)