如何实现基于Comparable接口定义优先级的PriorityStack？

要实现仅通过Comparable接口定义优先级、且同优先级元素遵循后进先出（LIFO）规则的PriorityStack，可以基于Java的PriorityQueue扩展，通过包装元素并加入插入顺序的比较逻辑来满足需求。

核心思路 #

Java自带的PriorityQueue会根据元素的Comparable实现排序，但同优先级元素的顺序是队列式的先进先出（FIFO）。要实现同优先级LIFO，我们需要：

1. 为每个元素绑定一个递增的插入序号，标记元素的插入顺序；
2. 重写比较逻辑：先按元素自身的Comparable规则比较优先级，若优先级相同，则让后插入的元素（序号更大）拥有更高优先级，确保出栈时先取出后插入的同优先级元素。

代码实现 #

1. 完善的Dog类（已实现Comparable）

public class Dog implements Comparable<Dog> {
    private String name;
    private int age;

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Dog other) {
        if (other == null) {
            return -1;
        }
        // 年龄小的狗优先级更高
        return this.age - other.age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return name + " (age: " + age + ")";
    }
}

2. PriorityStack实现

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityStack<T extends Comparable<T>> {
    // 内部包装类：保存元素和插入顺序序号
    private static class StackElement<E> implements Comparable<StackElement<E>> {
        private final E element;
        private final long insertionOrder;
        // 全局递增序号，保证每个元素的插入顺序唯一
        private static long sequence = 0;

        public StackElement(E element) {
            this.element = element;
            this.insertionOrder = sequence++;
        }

        @Override
        @SuppressWarnings("unchecked")
        public int compareTo(StackElement<E> other) {
            if (other == null) {
                return -1;
            }
            // 第一步：按元素自身的Comparable规则比较优先级
            int elementCompare = ((Comparable<? super E>) this.element).compareTo(other.element);
            if (elementCompare != 0) {
                return elementCompare;
            }
            // 第二步：优先级相同时，后插入的元素（序号大）优先级更高
            // 用other的序号减当前序号，让序号大的元素排在队列前面
            return Long.compare(other.insertionOrder, this.insertionOrder);
        }

        public E getElement() {
            return element;
        }
    }

    private final Queue<StackElement<T>> priorityQueue;

    public PriorityStack() {
        this.priorityQueue = new PriorityQueue<>();
    }

    // 入栈：添加元素并绑定插入序号
    public void push(T element) {
        priorityQueue.add(new StackElement<>(element));
    }

    // 出栈：取出优先级最高的元素，同优先级取最后插入的
    public T pop() {
        StackElement<T> top = priorityQueue.poll();
        return top != null ? top.getElement() : null;
    }

    // 查看栈顶元素
    public T peek() {
        StackElement<T> top = priorityQueue.peek();
        return top != null ? top.getElement() : null;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return priorityQueue.isEmpty();
    }

    // 测试验证
    public static void main(String[] args) {
        PriorityStack<Dog> dogStack = new PriorityStack<>();
        dogStack.push(new Dog("Skip", 4));
        dogStack.push(new Dog("Gregory", 3));
        dogStack.push(new Dog("Ziggy", 4));

        // 预期输出顺序：Gregory → Ziggy → Skip
        while (!dogStack.isEmpty()) {
            System.out.println(dogStack.pop());
        }
    }
}

关键逻辑说明 #

• 插入序号：通过静态变量sequence为每个插入的元素分配唯一递增序号，确保后插入的元素序号更大。
• 比较规则：
  • 优先使用元素自身的compareTo方法（比如Dog的年龄比较），年龄小的元素优先级更高；
  • 当元素优先级相同时，通过比较插入序号，让后插入的元素在PriorityQueue中排在前面，出栈时先被取出，实现同优先级的LIFO。
• 测试结果：运行main方法会输出：

  Gregory (age: 3)
  Ziggy (age: 4)
  Skip (age: 4)
  

  完全符合预期：最年幼的狗先出栈，同年龄的Ziggy后插入，比Skip先出栈。

内容的提问来源于stack exchange，提问作者JDausyd