题目描述补充

题目：栈排序

题目描述： 给定一个整数数组 arr，以及一个辅助栈 stack，不使用任何其他数据结构（如队列、堆等），仅通过栈的基本操作（push, pop, peek, isEmpty）来对数组中的元素进行排序（升序）。请实现一个函数 sortStack，该函数接受数组 arr 和栈 stack 作为参数，并返回排序后的栈（或等效地，将排序后的元素压入栈中）。

要求：

• 栈的基本操作包括：
  • push(x): 将元素 x 压入栈顶。
  • pop(): 移除栈顶元素并返回它。
  • peek(): 返回栈顶元素但不移除它。
  • isEmpty(): 检查栈是否为空，返回布尔值。
• 不能使用其他排序算法（如快速排序、归并排序等）的直接实现，只能通过栈操作来完成排序。
• 考虑到性能和空间复杂度，尽可能优化算法。

示例代码

以下是使用PHP、Python和JavaScript编写的示例代码，实现了上述要求的栈排序算法。

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 示例

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 示例

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);

码小课网站中有更多相关内容分享给大家学习，包括更深入的算法解析、实战项目等，欢迎访问。