X Tutup
Skip to content

Commit b635475

Browse files
shinezejianshinezejian
committed
Queue源码更新
1 parent 1a59a46 commit b635475

File tree

9 files changed

+668
-6
lines changed

9 files changed

+668
-6
lines changed

‎src/com/zejian/structures/LinkedList/MyCollection/MylinkeList.java‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -15,22 +15,22 @@ public class MylinkeList<T> implements Serializable,IList<T>, Iterable<T>{
1515
/**
1616
* 链表size,优化计算过程,无需遍历链表
1717
*/
18-
private int size = 0;
18+
protected int size = 0;
1919

2020
/**
2121
* 修改的记录符
2222
*/
23-
private int modCount=0;
23+
protected int modCount=0;
2424

2525
/**
2626
* 头部指向结点,不带数据,排除特殊情况,优化代码量
2727
*/
28-
private Node<T> first;
28+
protected Node<T> first;
2929

3030
/**
3131
* 尾部指向结点,不带数据,排除特殊情况,优化代码量
3232
*/
33-
private Node<T> last;
33+
protected Node<T> last;
3434

3535
/**
3636
* 初始化链表
@@ -501,7 +501,7 @@ final void checkForComodification() {
501501
* Blog : http://blog.csdn.net/javazejian
502502
* @param <T>
503503
*/
504-
private static class Node<T> {
504+
protected static class Node<T> {
505505
T data;
506506
Node<T> next;
507507
Node<T> prev;

‎src/com/zejian/structures/LinkedList/MyCollection/SortMyLinkedList.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.zejian.structures.LinkedList.MyCollection;
2+
3+
import java.io.Serializable;
4+
import java.util.Iterator;
5+
import java.util.ListIterator;
6+
7+
/**
8+
* Created by zejian on 2016/12/3.
9+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
10+
* 排序list的简单实现
11+
*/
12+
public class SortMyLinkedList<T extends Comparable<? extends T>> extends MylinkeList<T> implements Serializable {
13+
14+
private static final long serialVersionUID = -4783131709270334156L;
15+
16+
@Override
17+
public boolean add(T data) {
18+
if(data==null)
19+
throw new NullPointerException("data can\'t be null");
20+
21+
Comparable cmp =data;//这里需要转一下类型,否则idea编辑器上检验不通过.
22+
23+
if(this.isEmpty() || cmp.compareTo(this.last.prev.data) > 0){
24+
return super.add(data);//直接尾部添加,last不带数据的尾结点
25+
}
26+
27+
Node<T> p=this.first.next;
28+
//查找插入点
29+
while (p!=null&&cmp.compareTo(p.data)>0)
30+
p=p.next;
31+
32+
Node<T> q=new Node<>(p.prev,data,p);
33+
p.prev.next=q;
34+
p.prev=q;
35+
36+
size++;
37+
//记录修改
38+
modCount++;
39+
40+
return true;
41+
}
42+
43+
/**
44+
* 不根据下标插入,只根据比较大小插入
45+
* @param index
46+
* @param data
47+
*/
48+
@Override
49+
public void add(int index, T data) {
50+
this.add(data);
51+
}
52+
53+
54+
/**
55+
* 未实现
56+
* @param index
57+
* @return
58+
*/
59+
@Override
60+
public ListIterator<T> listIterator(int index) {
61+
return null;
62+
}
63+
64+
/**
65+
* 未实现
66+
* @return
67+
*/
68+
@Override
69+
public Iterator<T> iterator() {
70+
return null;
71+
}
72+
73+
//测试
74+
public static void main(String[] args){
75+
SortMyLinkedList<Integer> list=new SortMyLinkedList<>();
76+
list.add(50);
77+
list.add(40);
78+
list.add(80);
79+
list.add(20);
80+
print(list);
81+
}
82+
83+
public static void print(SortMyLinkedList mylinkeList){
84+
for (int i=0;i<mylinkeList.size();i++) {
85+
System.out.println("i->"+mylinkeList.get(i));
86+
}
87+
}
88+
}

‎src/com/zejian/structures/LinkedList/doubleLinked/LoopHeadDILinkedList.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*/
99
public class LoopHeadDILinkedList<T> implements ILinkedList<T> {
1010

11-
protected DNode<T> head; //不带数据的头结点
11+
public DNode<T> head; //不带数据的头结点
1212
// protected DNode<T> tail; //指向尾部的指针
1313

1414
public LoopHeadDILinkedList(){

‎src/com/zejian/structures/LinkedList/doubleLinked/SortLoopHeadDIlinkedList.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@ public boolean add(T data) {
3636
return true;
3737
}
3838

39+
3940
public static void main(String[] args){
4041
SortLoopHeadDIlinkedList<Integer> list=new SortLoopHeadDIlinkedList<>();
4142
list.add(50);

‎src/com/zejian/structures/Queue/LinkedQueue.java‎

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
package com.zejian.structures.Queue;
2+
3+
import com.zejian.structures.LinkedList.singleLinked.Node;
4+
5+
import java.io.Serializable;
6+
import java.util.*;
7+
8+
/**
9+
* Created by zejian on 2016/11/28.
10+
* Blog : http://blog.csdn.net/javazejian/article/details/53375004 [原文地址,请尊重原创]
11+
* 链式队列的实现
12+
*/
13+
public class LinkedQueue<T> implements Queue<T> ,Serializable{
14+
private static final long serialVersionUID = 1406881264853111039L;
15+
/**
16+
* 指向队头和队尾的结点
17+
* front==null&&rear==null时,队列为空
18+
*/
19+
private Node<T> front,rear;
20+
21+
private int size;
22+
/**
23+
* 用于控制最大容量,默认128,offer方法使用
24+
*/
25+
private int maxSize=128;
26+
27+
public LinkedQueue(){
28+
//初始化队列
29+
this.front=this.rear=null;
30+
}
31+
32+
@Override
33+
public int size() {
34+
return size;
35+
}
36+
37+
public void setMaxSize(int maxSize){
38+
this.maxSize=maxSize;
39+
}
40+
41+
@Override
42+
public boolean isEmpty() {
43+
return front==null&&rear==null;
44+
}
45+
46+
/**
47+
* data 入队,添加成功返回true,否则返回false,可扩容
48+
* @param data
49+
* @return
50+
*/
51+
@Override
52+
public boolean add(T data) {
53+
Node<T> q=new Node<>(data,null);
54+
if (this.front==null) {//空队列插入
55+
this.front = q;
56+
} else {//非空队列,尾部插入
57+
this.rear.next=q;
58+
}
59+
this.rear=q;
60+
size++;
61+
return true;
62+
}
63+
64+
/**
65+
* offer 方法可插入一个元素,这与add 方法不同，
66+
* 该方法只能通过抛出未经检查的异常使添加元素失败。
67+
* 而不是出现异常的情况，例如在容量固定（有界）的队列中
68+
* NullPointerException:data==null时抛出
69+
* IllegalArgumentException:队满,使用该方法可以使Queue的容量固定
70+
* @param data
71+
* @return
72+
*/
73+
@Override
74+
public boolean offer(T data) {
75+
if (data==null)
76+
throw new NullPointerException("The data can\'t be null");
77+
if (size>=maxSize)
78+
throw new IllegalArgumentException("The capacity of LinkedQueue has reached its maxSize:128");
79+
80+
Node<T> q=new Node<>(data,null);
81+
if (this.front==null) {//空队列插入
82+
this.front = q;
83+
} else {//非空队列,尾部插入
84+
this.rear.next=q;
85+
}
86+
this.rear=q;
87+
size++;
88+
return false;
89+
}
90+
91+
/**
92+
* 返回队头元素,不执行删除操作,若队列为空,返回null
93+
* @return
94+
*/
95+
@Override
96+
public T peek() {
97+
return this.isEmpty()? null:this.front.data;
98+
}
99+
100+
/**
101+
* 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
102+
* @return
103+
*/
104+
@Override
105+
public T element() {
106+
if(isEmpty()){
107+
throw new NoSuchElementException("The LinkedQueue is empty");
108+
}
109+
return this.front.data;
110+
}
111+
112+
/**
113+
* 出队,执行删除操作,返回队头元素,若队列为空,返回null
114+
* @return
115+
*/
116+
@Override
117+
public T poll() {
118+
if (this.isEmpty())
119+
return null;
120+
T x=this.front.data;
121+
this.front=this.front.next;
122+
if (this.front==null)
123+
this.rear=null;
124+
size--;
125+
return x;
126+
}
127+
128+
/**
129+
* 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
130+
* @return
131+
*/
132+
@Override
133+
public T remove() {
134+
if (isEmpty()){
135+
throw new NoSuchElementException("The LinkedQueue is empty");
136+
}
137+
T x=this.front.data;
138+
this.front=this.front.next;
139+
if (this.front==null)
140+
this.rear=null;
141+
size--;
142+
return x;
143+
}
144+
145+
@Override
146+
public void clearQueue() {
147+
this.front= this.rear=null;
148+
size=0;
149+
}
150+
}

0 commit comments

Comments
 (0)
X Tutup