LintCode 229 [Stack Sorting]

原题

请设计一种方法将一个栈进行升序排列 （最大的数在最上面）。

你可以使用另外一个栈来辅助操作，但不可将这些数复制到另外一个数据结构中 （如，数组）。

样例
给一个栈：

| |
|3|
|1|
|2|
|4|
 -

排序之后：

| |
|4|
|3|
|2|
|1|
 -

栈会被序列化为[4,2,1,3]，也就是说最右边是栈顶。

解题思路

• 首先，把所有元素从原stack倒进临时stack，然后每次从临时stack拿出一个元素放入current中：
• 若该current大于原stack中最上面的元素，则直接加入原stack
• 若该current小于原stack中的元素，就把原stack中的元素放回临时stack，直到原stack顶上的元素小于current或者原stack为空，则将current放入原stack
• 从而，保证了原stack中的元素从底到上是按有小到大排序的

完整代码

#Your can use Stack class in your solution.
#class Stack:
#  def __init__(self, stk=[])
#    # use stk to initialize the stack
#  def isEmpty(self)
#    # return true is stack is empty or false/
#  def push(self, item)
#    # push a element into stack and return nothing
#  def pop(self)
#    # pop a element from stack
#  def peek(self):
#    # return the top element if stack is not empty or nothing
#  def size(self):
#    # return the size of stack
class Solution:
    # @param {Stack} stk an integer Stack
    # @return {int} void
    def stackSorting(self, stk):
        # Write your code here
        tempStk = Stack()
        while not stk.isEmpty():
            tempStk.push(stk.pop())

        while not tempStk.isEmpty():
            current = tempStk.pop()
            while not stk.isEmpty() and stk.peek() > current:
                tempStk.push(stk.peek())
                stk.pop()
            stk.push(current)