算法大全（2）中，栈与队列的原理和应用有哪些？

本文共计2953个文字，预计阅读时间需要12分钟。

声明，本文涉及9道算法题目，涵盖了基本栈/队列问题，全部使用C语言实现。

　　声明，本文所有9道算法题目，覆盖了基本上所有常见的栈/队列问题，全都用C#实现，并测试通过，代码下载：StackAndQueue.zip

目录：

1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。

2.设计含min函数的栈的另解

3.用两个栈实现队列

4.用两个队列实现栈

5.栈的push、pop序列是否一致

6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1)

7.给栈排个序

8..如何用一个数组实现两个栈

9..如何用一个数组实现三个栈

1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。

　　算法思想：需要设计一个辅助栈，用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置，虽然能节省空间，这其实是不对的，因为我在调用Min函数的时候，只能得到位置，还要对存储元素的栈不断的pop，才能得到最小值——时间复杂度o(1)。

　　所以，还是在辅助栈中存储元素吧。

　　此外，还要额外注意Push操作，第一个元素不用比较，自动成为最小值入栈。其它元素每次都要和栈顶元素比较，小的那个放到栈顶。