面试题 03.05. 栈排序

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

示例1:

输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]

示例2:

输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]

说明:

• 栈中的元素数目在[0, 5000]范围内。

Python 解答：
1.常规思路

class SortedStack:

    def __init__(self):
        self.a = []
        self.b = []

    def push(self, val: int) -> None:
        if not self.a:
            self.a.append(val)
        elif val <= self.a[-1]:
            self.a.append(val)
        else:
            while self.a and self.a[-1] < val:
                self.b.append(self.a.pop())
            self.a.append(val)
            while self.b:
                self.a.append(self.b.pop())

    def pop(self) -> None:
        if self.a:
            self.a.pop()

    def peek(self) -> int:
        if self.a:
            return self.a[-1]
        else:
            return -1

    def isEmpty(self) -> bool:
        return not self.a

# 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()

2.优化

class SortedStack:

    def __init__(self):
        self.a = []
        self.b = []

    def push(self, val: int) -> None:
        if not self.a and not self.b:
            self.a.append(val)
        elif self.a and self.a[-1] <= val:
            while self.a and self.a[-1] <= val:
                self.b.append(self.a.pop())
            self.a.append(val)
        elif self.b and self.b[-1] > val:
            while self.b and self.b[-1] > val:
                self.a.append(self.b.pop())
            self.b.append(val)
        else:
            self.a.append(val)

    def pop(self) -> None:
        while self.b:
            self.a.append(self.b.pop())
        if self.a:
            self.a.pop()

    def peek(self) -> int:
        while self.b:
            self.a.append(self.b.pop())
        if self.a:
            return self.a[-1]
        else:
            return -1

    def isEmpty(self) -> bool:
        return not self.a and not self.b

# 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()