题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是o(1)。
分析：这是google的一道面试题。
看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被pop出去，如何才能得到下一个最小元素？因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素push到辅助栈中（考虑到元素可能是复杂的数据类型，用位置将能减少空间消耗）；每次pop一个元素出栈的时候，同时pop辅助栈。
参考代码：
步骤 数据栈 辅助栈 最小值
1.push 3 3 0 3
2.push 4 3,4 0,0 3
3.push 2 3,4,2 0,0,2 2
4.push 1 3,4,2,1 0,0,2,3 1
5.pop 3,4,2 0,0,2 2
6.pop 3,4 0,0 3
7.push 0 3,4,0 0,0,2 0
另一道题目：用两个栈实现一个队列的功能。
要求给出算法和思路！
答：设2个栈为a,b, 一开始均为空.
入队:
若a有空间，将新元素push入栈a;
若a满则判断b是否有元素，有则无法进队列；若无则将栈a中所有元素依次pop出并push到栈b，将新元素push进a
出队:
(1)判断栈b是否为空；
(2)如果不空，则b的栈顶元素出栈；如果为空，则将栈a中所有元素依次pop出并push到栈b；
(3)将栈b的栈顶元素pop出；
两个栈都是空时队列为空
这样实现的队列入队和出队的平摊复杂度都还是o(1)。
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
http://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622673.html