【注意】本文档存在大量的不规范，不标准言论以及大量臆想，请勿作为学术参考

有关栈数据处理和布尔代数的探索

这段时间的数据结构学习，使我对栈这一数据结构类型产生了兴趣。

从栈的本质出发，他是一个先进后出的特殊的数据结构类型。这个先进后出的思想使得很多操作变得极为便利且可行，就如由栈实现的简单计算器的计算优先级逻辑。

先进后出的栈

先进后出，简单的理解就是先进栈的数据后出栈

仔细观察这张图，我们可以发现什么呢？

没错，他对这串数字进行了逆序输出，更为准确的说，是

对于一个数据块，经理了一次完整的进栈出栈后，栈对其进行了逆序的操作

数据块是我自己的叫法，他应该被解释为，一次性依次压入栈中的一整个线性表，对于一个已经确定的数据块，我们不对其进行进一步的分割，同时也应当注意，只有一个元素线性表也被称为数据块，不过因为数据块中只有一个元素，所以其逆序输出是其本身。数据块应该作为待入栈最小单元来对待。

OK，那么我们就得到了定理一（请原谅我这么称呼）

逻辑的混乱

在数据结构作业中，我遇到了这样一个问题

请列出线性表abcd经过栈处理以后所有的可能序列

这道题本身并不难，套用课本给出的公式
$$
\LARGE C_{2n}^{n}-C_{2n}^{n-1}
$$
可得
$$
\LARGE C_{24}^{4}-C_{24}^{4-1}=14
$$
共计14种情况

可当我准备按顺序依次把他们写在我的作业本上时，我发现内部的逻辑已经复杂到难以以一种排列组合的形式优雅的快速得出了，我们要处理的不只有数据块进栈后立即出栈的情况，还有进栈后暂不处理，让后续的数据块进栈再出栈的情况，甚至对后续的数据块置之不理，处理更后面入栈的数据块……

这简直没完没了了！

要解决这种情况，我们需要再次强化之前对进栈数据的定义——数据块。以数据块作为最小进栈单元，我们可以轻松的划分出4种情况

单数据块进栈
双数据块进栈
3数据块进栈
4数据块进栈

根据栈结构先进后出的逆序原理，我们可以得到以下结果

类型	数据	结果
单数据块	`abcd`	`dcba`
双数据块	`abd` `d` \ `a` `bcd` \ `ab` `cd`	`cbad`\ `ab` `cd`\ `badc`
3数据块	`ab` `c` `d` \ `a` `bc` `d` \ `a` `b` `cd`	`a` `bc` `d` \ `bacd` \ `abdc`
4数据块	`a` `b` `c` `d`	`dcba`

怪事，数来数去也只有8种结果，剩下的6种结果去哪里了呢？这正是我们接下去所要讨论的。

于迷雾中出现的布尔代数

正当我冥思苦想之际，一个字符跳入我的脑海中

非号，来源于布尔代数的一种运算符，其含义是取反运算，例如在C语言中，0 == 1，这是一种逻辑运算

视线回到数据结构中的栈，根据定理一，栈对数据块的操作有单一结果，即逆序输出，输入和输出都只有一个，这和布尔代数的取非运算简直一模一样！而且对于不再进行分割而作为最小入栈单元的数据块，我们可以很轻松的得出其结果。

这太棒了！那么不妨将这一步逻辑操作抽象出来，定义为
$$
\LARGE
\overline{ab} = ba
$$
而作为最小数据单元的数据块，我们统一加上非号以方便区分

单数据块
$$
\LARGE
\overline{abcd}
dcba
$$
双数据块
$$
\LARGE
\overline{a}
,
\overline{bcd}
adcb
$$
3数据块
$$
\LARGE
\overline{a}
,
\overline{bc}
,
\overline{d}
acbd
$$
4数据块
$$
\LARGE
\overline{a}
,
\overline{b}
,
\overline{c}
,
\overline{d}
,
abcd
$$
如此一来，进栈出栈的数据运算被我们抽象为了逻辑运算，栈结构的数据操作，奇迹般的和布尔代数联系到了一起！实际上这一步抽象是对栈结构的二元性的抽象应用。这让我不禁回想起了某个开发者朋友和我说过的一句话

计算机科学的尽头就是数学

好，现在来冷静一下激动的心情，回顾一下，在例题中的计算我犯了怎么样的一个错误呢？很简单，在双数据块和单数据块的结构中，我忽视了存在3个元素的数据块进行进一步“分割”的可能。例如
$$
\LARGE\overline{\overline{ab}c}\overline{d}
$$
等一下，有人可能会有疑问，这不是和你之前的数据块的定义相违背了吗

实际上数据块的定义并没有出现漏洞，这里的“分割”并没有真的把数据块切分开来，更确切的说，是一种嵌套的关系，我称其为`数据块的嵌套“，那么以此可以完善对数据块的定义

数据块是一次性依次压入栈中的一整个线性表的统称，是一次性入栈的最小单元，数据块不可分，但是存在3个以上元素的数据块可以进行嵌套

有了这个完善的数据块定义，我们再来进一步探究布尔代数和栈结构的联系

不同寻常的逻辑门

提到具有二元性的问题，基本的逻辑运算是绕不开的，那么逻辑运算又与栈有什么关联呢？我们再来看一看这个表达式
$$
\LARGE\overline{a},\overline{b} = ab
$$
我们也可以表达为
$$
\LARGE\overline{a}\wedge\overline{b} = ab
$$
其中，逻辑与表达为顺序连接，而或逻辑可以表示为与逻辑的对立，那么不妨令
$$
\LARGE\overline{a}\vee\overline{b} = ba
$$
再次归纳一下

$\wedge$ 连接的两个数据块顺序输出，$\vee$ 连接的两个数据块逆序输出

那么由此我们可以得出
$$
\LARGE\overline{\overline{ab}c}\overline{d}=\overline{\overline{a\wedge b}\wedge c}\wedge \overline{d}
$$
这一切都显得那么的合理，那么赶紧来看看这个式子怎么求解吧

神奇的德摩根定律

一路探索下来，栈结构的特殊性质在某些方面简直和布尔代数一模一样，我们也总结出来了一套代数计算的工具，而布尔代数有一个很著名的定律，德摩根定律，他可以被表示为
$$
\LARGE\overline{a\wedge b}=\LARGE\overline{a}\vee\overline{b}
$$
那么它可以用于我们前面所总结出来的代数计算工具上吗？

答案是肯定的。
$$
\LARGE\overline{\overline{ab}c}\overline{d}=\overline{\overline{a\wedge b}\wedge c}\wedge \overline{d}=\overline{(a\vee b)\wedge c}\wedge\overline{d}=(a\wedge b)\vee c\wedge d=cabd
$$
至此，我们终于拿到了最后一块拼图，并成功得出了嵌套数据块情况下的结果，而这不正是我们苦苦追寻已久的8种结果之外的答案吗？使用德摩根定律我们可以通过布尔代数的形式计算出栈的所有可能情况，在熟练的情况下，你甚至可以直接得出答案
$$
\LARGE\overline{\overline{ab},\overline{cd}}=cdab
$$
例题的元素只有4个，而这种计算方式同样适用于元素更多，嵌套更复杂的场景，并且能抛去多余的逻辑思考用简单直白的代数计算替代，这着实使人激动不已。

综上所述，丢失的6种情况应该是

类型	数据	结果
双数据块	$\large\overline{\overline{ab}c}\overline{d}\quad\overline{a\overline{bc}},\overline{d}\quad\overline{a},\overline{\overline{bc}d}\quad\overline{a},\overline{b\overline{cd}}$	$\large cabd\quad bcad\quad adbc\quad acdb$
3数据块	$\large\overline{\overline{ab},\overline{cd}}\quad\overline{a\overline{bc}d}$	$\large cdab\quad dbca$