插入、删除功能实现
/*
* 使用单链表;每次插入大约需要比较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
}
}