原題

請(qǐng)?jiān)O(shè)計(jì)一種方法將一個(gè)棧進(jìn)行升序排列 （最大的數(shù)在最上面）。

你可以使用另外一個(gè)棧來輔助操作，但不可將這些數(shù)復(fù)制到另外一個(gè)數(shù)據(jù)結(jié)構(gòu)中 （如，數(shù)組）。

樣例
給一個(gè)棧：

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

排序之后：

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

棧會(huì)被序列化為[4,2,1,3]，也就是說最右邊是棧頂。

解題思路

• 首先，把所有元素從原stack倒進(jìn)臨時(shí)stack，然后每次從臨時(shí)stack拿出一個(gè)元素放入current中：
• 若該current大于原stack中最上面的元素，則直接加入原stack
• 若該current小于原stack中的元素，就把原stack中的元素放回臨時(shí)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)