栈中特定范围整数的高效排序：基于计数排序的线性时间算法

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class StackSorter {

    /**
     * 使用数组实现计数排序，对栈中特定范围的整数进行排序。
     * 推荐使用 ArrayDeque 代替 legacy 的 java.util.Stack。
     *
     * @param stack 待排序的栈
     * @param min 目标范围的最小值
     * @param max 目标范围的最大值
     * @return 排序后的栈，只包含指定范围内的元素，且按升序排列（栈底到栈顶）
     */
    public static Deque<Integer> sortStackWithCountingSort(Deque<Integer> stack, int min, int max) {
        // 步骤一：构建频率直方图
        // freq 数组的索引对应 (值 - min)，例如 freq[0] 存储 min 的频率
        int[] freq = new int[max - min + 1]; 

        while (!stack.isEmpty()) {
            int next = stack.pop(); // 弹出栈顶元素
            // 检查元素是否在目标范围内
            if (next >= min && next <= max) {
                freq[next - min]++; // 对应值的频率加一
            }
        }

        // 步骤二：按序重建栈
        // 从目标范围的最大值开始，逆序推入，以确保栈底是最小值，栈顶是最大值
        for (int i = freq.length - 1; i >= 0; i--) {
            int valueToPush = i + min; // 将索引转换回实际值
            while (freq[i] > 0) {
                stack.push(valueToPush); // 推入元素
                freq[i]--; // 对应频率减一
            }
        }
        return stack;
    }

    /**
     * 另一种实现方式：使用 HashMap 作为频率存储。
     * 功能相同，但对于小范围整数，数组通常更高效。
     */
    public static Deque<Integer> sortStackWithCountingSortHashMap(Deque<Integer> stack, int min, int max) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        while (!stack.isEmpty()) {
            int next = stack.pop();
            if (next >= min && next <= max) {
                freqMap.merge(next, 1, Integer::sum); // 计算频率
            }
        }

        for (int i = max; i >= min; i--) {
            int count = freqMap.getOrDefault(i, 0); // 获取频率，若无则为0
            while (count > 0) {
                stack.push(i);
                count--;
            }
        }
        return stack;
    }

    public static void main(String[] args) {
        // 示例用法
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(5);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(3);
        stack.push(5);
        stack.push(3);
        stack.push(1);
        stack.push(4);
        stack.push(7);

        System.out.println("Original Stack (top to bottom): " + stack);

        // 使用数组实现的计数排序
        Deque<Integer> sortedStackArray = sortStackWithCountingSort(stack, 1, 4);
        System.out.println("Sorted Stack (Array Impl, top to bottom): " + sortedStackArray);
        // 验证排序结果（从栈顶弹出）
        System.out.print("Popping elements (Array Impl): ");
        while (!sortedStackArray.isEmpty()) {
            System.out.print(sortedStackArray.pop() + " ");
        }
        System.out.println("\n");

        // 重置栈用于HashMap示例
        stack.push(5); stack.push(3); stack.push(2); stack.push(1); stack.push(3);
        stack.push(5); stack.push(3); stack.push(1); stack.push(4); stack.push(7);

        // 使用HashMap实现的计数排序
        Deque<Integer> sortedStackHashMap = sortStackWithCountingSortHashMap(stack, 1, 4);
        System.out.println("Sorted Stack (HashMap Impl, top to bottom): " + sortedStackHashMap);
        // 验证排序结果（从栈顶弹出）
        System.out.print("Popping elements (HashMap Impl): ");
        while (!sortedStackHashMap.isEmpty()) {
            System.out.print(sortedStackHashMap.pop() + " ");
        }
        System.out.println();
    }
}