# \[面试题 03.05]\[中等] 栈排序

## 题目描述

[面试题 03.05. 栈排序](https://leetcode-cn.com/problems/sort-of-stacks-lcci/)

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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]范围内。

## 解题思路

由于最小的元素要位于栈顶, 相当于栈内的元素是有顺序的. 因此在压入一个新元素时, 需要将这个元素与栈顶元素依次比较, 将小于这个元素的栈顶元素依次弹出, 然后放入一个辅助栈中, 压入这个新元素后再将辅助栈的元素压回.

因为栈的性质, 反复调整两次, 元素的顺序仍然是不变得.

这样除了push操作的时间复杂度是$$O(n)$$, 其他操作的时间复杂度都是$$O(1)$$.

```python
class SortedStack:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, val: int) -> None:
        while self.stack1 and self.stack1[-1] < val:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(val)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self) -> None:
        return self.stack1.pop() if self.stack1 else None

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

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


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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/03.05-zhan-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.