题目
用一个栈来实现另一个栈的排序
将一个栈从顶到底按从大到小的顺序排序, 过程通过一个辅助栈来实现
思路分析
要使栈A从顶到底按照从大到小的顺序, 那么如果栈B中是从顶到底按照从小到大的顺序, 这样将栈B的数据依次弹出并压入栈A, 就实现了栈A中数据的排序.
那么如果将栈A中的数据按照从大到小的顺序依次压入栈B呢? 栈B中的数据一定是上边的要小于等于下边的, 将栈A中的数据弹出后, 将其插入到栈B适当的位置, 如此即可.
数据压入栈B的具体规则如下:
- 从栈A中弹出数据num
- 若栈B为空, 则直接入栈
- 若栈B不为空, 将num与栈B的栈顶元素max比较
- 若num <= max, 则num入栈B
- 若num > max, 则将栈B的元素逐一出栈并压入栈A, 直到num小于或等于栈B的栈顶元素, 此时将num入栈B
经过以上过程, 即可将栈A中的元素按照从小到大的顺序依次入栈B, 此时将栈B依次出栈并入栈A即可. Java代码的简单实现如下:
分享到:
閱讀更多 牛牛的編程之路 的文章
