动态循环数组构造队列结构

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
 * 动态循环数组构造队列结构
 * @author Administrator@2018年12月12日 下午8:30:47
 */
public class DynamicArrayQueue {

	public int capacity;
	public int initcapacity;
	public int[] arrayQueue;
	public int front;
	public int rear;
	
	public DynamicArrayQueue(int size) {
		initcapacity = capacity = size;
		arrayQueue = new int[size];
		front = -1;
		rear = -1;
	}
	
	/**
	 * 队列是否为空
	 * @return
	 * @author Administrator@2018年12月12日 下午8:33:59
	 */
	public boolean isEmpty() {
		return (front == -1);
	}
	
	/**
	 * 判断队列是否已经满了
	 * @return
	 * @author Administrator@2018年12月12日 下午8:35:02
	 */
	public boolean isFull() {
		return ((rear + 1)%capacity == front);
	}
	
	/**
	 * 当队列满的时候，队列扩容 变为原来的2倍。
	 * 
	 * @author Administrator@2018年12月12日 下午9:22:18
	 */
	public int resize() {
		capacity = capacity*2;
		return capacity;
	}

	/**
	 * 删除队列首元素
	 * @return
	 * @author Administrator@2018年12月12日 下午8:36:33
	 */
	public int arrayPoll() {
		if(isEmpty()) {
			throw new NullPointerException("队列已经空了！");
		}
		int data = arrayQueue[front];
		if(front == rear) {
			front = rear = -1;
		}else {
			front = (front + 1) % capacity;
		}
		return data;
	}
	
	/**
	 * 元素入队
	 * @param element
	 * @return
	 * @author Administrator@2018年12月12日 下午8:37:09
	 */
	public int arrayOffer(int element) {
		if(isFull()) {
			capacity = resize();
			int oldArray[] = arrayQueue;
			arrayQueue = new int[capacity];
			for(int i = 0; i < oldArray.length; i++) {
				arrayQueue[i] = oldArray[i];
			}
			if(front > rear) {
				//把front 后面这一部分元素向后迁移
				for(int i = front; i < initcapacity; i++) {
					arrayQueue[i + initcapacity] = arrayQueue[i];
				}
				front = front + initcapacity;//修改front的位置
				initcapacity = capacity;//修改初始容量为当前容量，以便于下次扩容
			}
		}
		rear = (rear + 1) % capacity;
		arrayQueue[rear] = element;
		if(front == -1) {
			front = rear;
		}
		return arrayQueue[front];
	}
	
	/**
	 * 获取队首元素
	 * @return
	 * @author Administrator@2018年12月12日 下午8:37:53
	 */
	public int arrayPeek() {
		if(isEmpty()) {
			throw new NullPointerException("队列已经空了！");
		}
		return arrayQueue[front];
	}
	
	/**
	 * 获取队列元素的个数
	 * @return
	 * @author Administrator@2018年12月12日 下午8:48:18
	 */
	public int arrayQueueCapicity() {
		return (rear - front + 1 + capacity) % capacity;
	}
}