Python面试算法指南：栈中元素排序技巧详解

在Python编程中，栈是一种常用的数据结构，用于存储和管理数据项。本文将探讨一个常见的面试问题：如何对栈中的元素进行排序，使栈顶到栈底的元素按从小到大的顺序排列。

例如，给定一个栈 {1, 3, 2}（其中2位于栈顶），排序后应变为 {3, 2, 1}（1位于栈顶）。实现这一目标的主要思想是利用递归技术，将栈底的元素移动到栈顶，再将其弹出，并对剩余的子栈进行相同操作，最后将弹出的元素按正确顺序重新插入栈中。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("pop from an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from an empty stack")

    def size(self):
        return len(self.items)

# 递归函数，将栈底元素移至栈顶
def move_bottom_to_top(stack):
    if stack.is_empty():
        return
    top1 = stack.pop()
    if not stack.is_empty():
        move_bottom_to_top(stack)
        top2 = stack.pop()
        if top1             stack.push(top2)
            stack.push(top1)
        else:
            stack.push(top1)
            stack.push(top2)
    else:
        stack.push(top1)

# 主排序函数
def sort_stack(stack):
    if stack.is_empty():
        return
    move_bottom_to_top(stack)
    top = stack.pop()
    sort_stack(stack)
    insert_sorted(stack, top)

# 辅助函数，将元素按正确顺序插入已排序的栈中
def insert_sorted(stack, value):
    if stack.is_empty() or (not stack.is_empty() and value > stack.peek()):
        stack.push(value)
    else:
        temp = stack.pop()
        insert_sorted(stack, value)
        stack.push(temp)

# 测试代码
if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(3)
    s.push(2)
    sort_stack(s)
    while not s.is_empty():
        print(s.pop(), end=' ')

上述代码首先定义了一个简单的栈类，包括基本的栈操作如入栈、出栈、检查栈是否为空等。接着，我们实现了两个关键函数：`move_bottom_to_top` 和 `sort_stack`。`move_bottom_to_top` 函数负责将栈底的元素移动到栈顶，而 `sort_stack` 函数则负责整体的排序逻辑。最后，我们通过一个测试实例验证了算法的有效性。