当前位置： 面试刷题>> 栈排序 (经典算法题500道)
### 题目描述补充
题目：栈排序
**题目描述**：
给定一个整数数组 `arr`，以及一个辅助栈 `stack`，不使用任何其他数据结构（如队列、堆等），仅通过栈的基本操作（push, pop, peek, isEmpty）来对数组中的元素进行排序（升序）。请实现一个函数 `sortStack`，该函数接受数组 `arr` 和栈 `stack` 作为参数，并返回排序后的栈（或等效地，将排序后的元素压入栈中）。
**要求**：
- 栈的基本操作包括：
- `push(x)`: 将元素 `x` 压入栈顶。
- `pop()`: 移除栈顶元素并返回它。
- `peek()`: 返回栈顶元素但不移除它。
- `isEmpty()`: 检查栈是否为空，返回布尔值。
- 不能使用其他排序算法（如快速排序、归并排序等）的直接实现，只能通过栈操作来完成排序。
- 考虑到性能和空间复杂度，尽可能优化算法。
### 示例代码
以下是使用PHP、Python和JavaScript编写的示例代码，实现了上述要求的栈排序算法。
#### PHP 示例
```php
class Stack {
private $items = [];
public function push($item) {
$this->items[] = $item;
}
public function pop() {
return array_pop($this->items);
}
public function peek() {
return end($this->items);
}
public function isEmpty() {
return empty($this->items);
}
}
function sortStack($arr) {
$stack = new Stack();
$tempStack = new Stack();
foreach ($arr as $num) {
$stack->push($num);
}
while (!$stack->isEmpty()) {
$tempNum = $stack->pop();
while (!$tempStack->isEmpty() && $tempStack->peek() > $tempNum) {
$stack->push($tempStack->pop());
}
$tempStack->push($tempNum);
}
// 将排序后的元素重新压回原栈
while (!$tempStack->isEmpty()) {
$stack->push($tempStack->pop());
}
return $stack; // 注意：实际返回栈对象，在PHP中可能需要其他方式展示结果
}
// 示例用法
$arr = [3, 1, 4, 1, 5, 9, 2, 6];
$sortedStack = sortStack($arr);
// 示例：展示排序后的栈内容（PHP中直接展示栈对象可能不直观，这里省略具体展示方式）
```
#### Python 示例
```python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def isEmpty(self):
return len(self.items) == 0
def sortStack(arr):
stack = Stack()
tempStack = Stack()
for num in arr:
stack.push(num)
while not stack.isEmpty():
tempNum = stack.pop()
while not tempStack.isEmpty() and tempStack.peek() > tempNum:
stack.push(tempStack.pop())
tempStack.push(tempNum)
# 将排序后的元素移回原栈
while not tempStack.isEmpty():
stack.push(tempStack.pop())
return stack # Python中可以直接返回栈对象
# 示例用法
arr = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_stack = sortStack(arr)
# 示例：展示排序后的栈内容
print(sorted_stack.items)
```
#### JavaScript 示例
```javascript
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
function sortStack(arr) {
let stack = new Stack();
let tempStack = new Stack();
arr.forEach(num => stack.push(num));
while (!stack.isEmpty()) {
let tempNum = stack.pop();
while (!tempStack.isEmpty() && tempStack.peek() > tempNum) {
stack.push(tempStack.pop());
}
tempStack.push(tempNum);
}
// 将排序后的元素移回原栈
while (!tempStack.isEmpty()) {
stack.push(tempStack.pop());
}
return stack; // JavaScript中返回栈对象
}
// 示例用法
let arr = [3, 1, 4, 1, 5, 9, 2, 6];
let sortedStack = sortStack(arr);
// 示例：展示排序后的栈内容
console.log(sortedStack.items);
```
**码小课**网站中有更多相关内容分享给大家学习，包括更深入的算法解析、实战项目等，欢迎访问。