栈排序

题目

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

利用一个辅助栈auxStack，当压入元素val时，进行调整。

调整的方法类似于插入排序，把小于val的值放入辅助栈，待val放入正确位置，再把辅助栈中的元素放入原始栈中。

代码

class SortedStack:
    def __init__(self):
        self.stack = []
        self.auxStack = []
    def push(self, val: int) -> None:
        if not self.stack or val <= self.peek():
            self.stack.append(val)
        else:
            # 利用auxStack进行插入排序
            while True:
                compareVal = self.pop()
                if val > compareVal and compareVal != -1:
                    self.auxStack.append(compareVal)
                else:
                    if compareVal != -1:
                        self.stack.append(compareVal)
                    self.stack.append(val)
                    while len(self.auxStack) != 0:
                        self.stack.append(self.auxStack.pop())
                    break
    def pop(self) -> None:
        return self.stack.pop() if self.stack else -1
    def peek(self) -> int:
        return self.stack[-1] if self.stack else -1
    def isEmpty(self) -> bool:
        return not bool(self.stack)
# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()