本文主要是介绍栈混洗概念、甄别（栈的应用一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//最近听邓俊辉老师的课学数据结构，在这里对学到的知识做一些比较详细易懂的整理、梳理。
栈混洗 stack shuffle/stack permutation
概念：将栈A的顶元素弹出并压入栈S，或将栈S的顶元素弹出并压入栈B中，经过一系列的操作后，A中元素全部转入B中，则称之为A的一个栈混洗。这里标记 尖括号<：栈顶，方括号 ] ：栈底 ，两个栈的弹出与压入次序不一样由此产生了在B栈的不同排序方式。
栈混洗的计数:
例如A:1 2 3的混洗结果可能有 123，132，213，231，321，不可能出现312 (原因如下图右上角）
经观察，任意三个元素出现的排序方式与其他元素无关，如果出现了 k i j 的排序方式，必定不是栈混洗的结果——充要条件
如果不出现312 的模式（ j+1,i,j ）那必然是栈混洗的结果,312模式称之为禁形。
栈混洗的甄别
甄别方法有三种思路：
-
不断枚举i,j,k的组合 复杂度 O（n^3&
这篇关于栈混洗概念、甄别（栈的应用一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
