数据结构——LinkedQueue的实现

队列是一种先进先出(FIFO)的数据结构,LinkedQueue是用链表实现的,另外还可以用回环数组的方式实现。

LinkedQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.NoSuchElementException;
/**
* 用单链表的形式实现链式队列
* 该实现包含有一个指向尾部节点的引用,方便入队列操作的实现
* @author Bingo
*
* @param <T>
*/
public class LinkedQueue<T> {
private int size;
private Node<T> head;
private Node<T> tail;
public LinkedQueue(){
size = 0;
tail = head = new Node<T>(null, null);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size() == 0;
//return head == tail;
}
/**
* 进队列,在链表的尾部添加新的元素
* @param ele
*/
public void enqueue(T ele){
Node<T> newNode = new Node<T>(ele, null);
tail.next = newNode;
tail = newNode;
size++;
}
/**
* 出队列,在链表的头部取出元素
* @return
*/
public T dequeue(){
if(isEmpty())
throw new NoSuchElementException("queue is empty.");
T oldElement = head.next.element;
head.next = head.next.next;
size--;
return oldElement;
}
/**
* 私有节点类,保存节点元素值和指向下一个节点的引用
* @author Bingo
*
* @param <T>
*/
private static class Node<T>{
public T element;
public Node<T> next;
public Node(T element, Node<T> next){
this.element = element;
this.next = next;
}
}
@Override
public String toString() {
return "size = " + size();
}
}