学习记录队列数据结构 队列
TONG HUI队列特点
- 只允许在一端进行插入操作，在另一端进行删除操作的线性表
- 允许插入的一端称为队尾（rear），允许删除的一端称为队头(front)
- “先进先出”原则
定义队列
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
| class QueueArray<T>{
private T[] queue;
private int front=-1,rear=-1;
public QueueArray(int stack_size){
this.queue = new T[stack_size];
}
public boolean isEmpty(){}
public void add(T data){}
public T delete(){}
}
class QueueByLink<T>{
private Node<T> front;
private Node<T> rear;
public QueueLink(){
this.front = null;
this.rear = null;
}
public boolean isEmpty(){}
public void add(T data){}
public T delete(){}
}
class Node<T>{
T data;
Node next;
public Node(T data){
this.data = data;
this.next = null;
}
}
|
顺序队列
数组
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
| public boolean isEmpty(){
if(this.front == -1){return true;}
return false;
}
public boolean add(Object data){
if(this.rear >= (this.queue.length-1)){
System.out.println("已满");
return false;
}
this.queue[++this.rear] = data;
if(this.front == -1){
this.front = 0;
}
return true;
}
public Object delete(){
if(isEmpty()){
System.out.println("堆栈为空");
return null;
}
Object data = this.queue[this.front];
if(this.rear > 0){
Object[] newArr = new Object[this.queue.length];
for (int i = 1; i <= this.rear; i++) {
newArr[i-1] = this.queue[i];
}
this.queue = newArr;
this.rear--;
}else{
this.front = this.rear = -1;
}
return data;
}
|
链表
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
| public boolean isEmpty(){
if(this.front == null){return true;}
return false;
}
public boolean add(T data){
Node<T> node = new Node(data);
if (this.front == null){
this.front = node;
}else {
this.rear.next = node;
}
this.rear = node;
return true;
}
public T delete(){
if(isEmpty()){
System.out.println("堆栈为空");
return null;
}
T data = this.front.data;
if(this.rear != this.front){
this.front = this.front.next;
}else{
this.front = this.rear = null;
}
return data;
}
|
双向队列
双向链表实现
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
| class Node<T>{
Node prev;
T data;
Node next;
public Node(T data){
this.data = data;
this.next = null;
this.prev = null;
}
}
public boolean isEmpty(){
if(this.front == null){return true;}
return false;
}
public boolean addFront(T data){
Node<T> node = new Node(data);
if (this.front == null){
this.rear = node;
}else {
this.front.prev = node;
node.next = this.front;
}
this.front = node;
return true;
}
public boolean addRear(T data){
Node<T> node = new Node(data);
if (this.front == null){
this.front = node;
}else {
node.prev = this.rear;
this.rear.next = node;
}
this.rear = node;
return true;
}
public T deleteFront(){
if(isEmpty()){
System.out.println("堆栈为空");
return null;
}
T data = this.front.data;
if(this.rear != this.front){
this.front = this.front.next;
this.front.prev = null;
}else{
this.front = this.rear = null;
}
return data;
}
public T deleteRear(){
if(isEmpty()){
System.out.println("堆栈为空");
return null;
}
T data = this.rear.data;
if(this.rear != this.front){
this.rear = this.rear.prev;
this.rear.next = null;
}else{
this.front = this.rear = null;
}
return data;
}
|
环形队列
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
| private Object[] queue;
private int front=-1,rear=-1;
public RingQueue(int stack_size){
this.queue = new Object[stack_size];
}
public boolean isEmpty(){
if(this.front == this.rear){return true;}
return false;
}
public boolean add(Object data){
if(this.rear+1 == this.front || this.rear == this.queue.length-1 && this.front==0){
System.out.println("已满");
return false;
}
this.rear++;
if (this.rear == this.queue.length){
this.rear = 0;
}
if (this.front == -1){
this.front = 0;
}
this.queue[this.rear] = data;
return true;
}
public Object delete(){
if(isEmpty()){
System.out.println("堆栈为空");
return null;
}
Object data = this.queue[this.front];
this.queue[this.front] = null;
this.front++;
if (this.front == this.queue.length){
this.front = 0;
}
return data;
}
|
优先队列
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就可以使用一种特殊的队列来完成这种需求，优先队列。
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
| public class priorityQueue<T> {
private T[] items;
private int N;
public priorityQueue(int capacity) {
items = (T[]) new Comparable[capacity+1];
N = 0;
}
public void insert(T t) {
items[++N] = t;
swim(N);
}
public T delete() {
T max = items[1];
exch(1, N);
items[N] = null;
N--;
sink(1);
return max;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
private void exch(int i, int j) {}
private void swim(int k) {
while (k > 1) {
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
private void sink(int k) {
while (2 * k <= N) {
int max = 2 * k;
if (2 * k + 1 <= N) {
if (less(2 * k, 2 * k + 1)) {
max = 2 * k + 1;
}
}
if (!less(k, max)) {
break;
}
exch(k, max);
k = max;
}
}
}
|
