题解 | #火车进站#

#解法1:

import sys
#res:记录输出结果,nums:要进站的火车,stack:站里的火车.quit:出站的队列
def dfs(res, nums, stack, quit):
    # 要进站的火车和站里的火车都清空,就得出结果
    if len(nums) == 0 and len(stack) == 0:
        res.append(" ".join(quit))
        return
    #进站
    if len(nums) > 0:
        stack.append(nums.pop(0))
        dfs(res, nums, stack, quit)
        nums.insert(0, stack.pop())
    #出站
    if len(stack) > 0:
        quit.append(stack.pop())
        dfs(res, nums, stack, quit)
        stack.append(quit.pop())


while True:
    try:
        n = int(input())
        nums = input().split()
        res = []
        stack = []
        quit = []
        dfs(res, nums, stack, quit)
        res.sort()
        for i in res:
            print(i)
    except:
#         print(sys.exc_info())
        break


#解法2
# # 深度遍历，模拟出栈入栈
# # 递归时分三种情况：
# # 1.进站不出
# # 2.进站之后马上出站
# # 3.栈里的车出来
# # 当全部火车出站，算一种结果，最后用set去重,list排序。。。

# import sys
# #res:记录输出结果集合,nums:要进站的火车,stack:站里的火车.quit:出站的队列,k当前处理的第几辆车
# def dfs(res, nums, stack, quit, k):
#     # 车全部出站，记录一种结果.  返回
#     if len(quit) == len(nums):
#         res.add(" ".join(quit))
#         return
#     for i in range(3):
#         #有三种情况
#         #进站,马上出站
#         if k < len(nums) and i == 0:
#             quit.append(nums[k])
#             k += 1
#             dfs(res, nums, stack, quit, k)
#             quit.pop()
#             k -= 1
#         #进站后不出站
#         elif k < len(nums) - 1 and i == 1:
#             stack.append(nums[k])
#             k += 1
#             dfs(res, nums, stack, quit, k)
#             stack.pop()
#             k -= 1
#         #车从站里出来
#         elif i == 2 and len(stack) > 0:
#             quit.append(stack[-1])
#             stack.pop()
#             dfs(res, nums, stack, quit, k)
#             stack.append(quit[-1])
#             quit.pop()


# while True:
#     try:
#         n = int(input())
#         nums = input().split()
#         res = set()#用集合去重结果
#         stack = []
#         quit = []
#         dfs(res, nums, stack, quit, 0)
#         res = list(res)
#         res.sort()
#         for i in res:
#             print(i)
#     except:
# #         print(sys.exc_info())
#         break