单链表实现有序队列

插入、删除功能实现

/*
 * 使用单链表；每次插入大约需要比较N/2次；
 * 插入效率是O(N),删除表头元素效率是O(1)
 */
public class MySortQueue {

    // 使用单链表实现
    private Entry root;
    private static class Entry {
        int value;
        Entry after;
        public Entry (int mumber) {
            this.value = mumber;
        }
    }
    // 对外暴躁的插入方法，主要处理root元素的相关操作
    public void insert(int mumber) {
        Entry insert = new Entry(mumber);
        if (root == null) {
            root = insert;
            return;
        }
        if (insert.value < root.value) {
            insert.after =root;
            root = insert;
        } else {
            // 调用 insertSort方法
            insertSort(insert, root);
        }
    }
    // 受保护的插入方法
    private void insertSort(Entry inset, Entry entry) {
        if (entry.after == null) {
            entry.after = inset;
            return;
        }
        if (inset.value < entry.after.value) {
            inset.after = entry.after;
            entry.after = inset;
        } else {
            insertSort(inset, entry.after);
        }
    }
    // 队列的删除方法
    public int pop () {
        int value = root.value;
        root = root.after;
        return value;
    }
}
// 测试类
class Test {
    public static void main(String[] args) {
        MySortQueue mySortQueue = new MySortQueue();
        mySortQueue.insert(8);
        mySortQueue.insert(800);
        mySortQueue.insert(2);
        mySortQueue.insert(50);

        int pop = mySortQueue.pop();
        System.out.print(pop + "    ");
        int pop2 = mySortQueue.pop();
        System.out.print(pop2 + "    ");
        int pop3 = mySortQueue.pop();
        System.out.print(pop3 + "    ");
        int pop4 = mySortQueue.pop();
        System.out.print(pop4 + "    ");

        // 输出结果：2    8    50    800
    }
}