煮酒论队列

发表于 更新于 分类于 阅读次数：

循环队列

循环队列介绍

  • 存在front和tail指针，当front==tail时，队列为空，当添加元素时，队列末尾指针即tail+1，而元素出队列时，则队列头指针front+1。
  • 当（tail+1）%c ==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
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
public class LoopQueue<E> implements Queue<E> {
	public E[] data;
	//声明头指针和尾指针
	public int front, tail;
	public int size;

	public LoopQueue(int capicity) {
		this.data = (E[]) new Object[capicity + 1];
		front = 0;
		tail = 0;
		size = 0;
	}

	public LoopQueue() {
		this(10);
	}
	//由循环队列满的条件可知，队列元素的数量是整个队列长度-1
	public int getCapicty() {
		return data.length-1;
	}
	

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return front==tail;
	}

	//入队操作，在队列满的条件下，进行扩容操作，对tail进行取余操作。这是与数组添加元素不一样的地方。
	@Override
	public void enqueue(E e) {
		if((tail+1)%data.length==front) {
			resize(getCapicty()*2);
		}
		data[tail]=e;
		tail=(tail+1)%data.length;
		size++;

	}
	//扩容操作，声明一个新数组。
	private void resize(int capicity) {
		E[] data_new=(E[]) new Object[capicity+1];
//		for(int i=0;i < size;i++) {
//			data_new[i]=data[(i+front)%data.length];
//		}
		for(int i=front;i!=tail;i=(i+1)%data.length) {
			data_new[i-front]=data[i];
		}
		data=data_new;
		front=0;
		tail=size;
		
	}
	//出队操作，可以手动将队列头指针置为null，提醒GC进行回收，不影响最终的结果。
	@Override
	public E dequeue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空");
		}
		E val=data[front];
//		data[front]=null;
		front=(front+1)%data.length;
		size--;
		if(size==getCapicty()/4 && getCapicty()/2!=0) {
			resize(getCapicty()/2);
		}
		return  val;
	}

	@Override
	public E getFront() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空");
		}
		return data[front];
	}
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(String.format("Queue size = %d,length: %d", size, getCapicty()));
		stringBuilder.append("front [");
		for (int i = front; i != tail; i=(i+1)%data.length) {
			stringBuilder.append(data[i]);
			if ((i+1)%data.length!=tail) {
				stringBuilder.append(",");
			}
		}
		stringBuilder.append("] tail");
		return stringBuilder.toString();


	}

}

测试示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LoopQueueTest {

	public static void main(String[] args) {
		LoopQueue loopQueue=new LoopQueue<>();
		for(int i=0;i<10;i++) {
			loopQueue.enqueue(i);
			System.out.println(loopQueue);
			if(i%3==2) {
				loopQueue.dequeue();
				System.out.println(loopQueue);
			}
		}
	}

}

输出示例

1
2
3
4
5
6
7
8
9
10
11
12
13
Queue size = 1,length: 10 front [0] tail
Queue size = 2,length: 10 front [0,1] tail
Queue size = 3,length: 10 front [0,1,2] tail
Queue size = 2,length: 5 front [1,2] tail
Queue size = 3,length: 5 front [1,2,3] tail
Queue size = 4,length: 5 front [1,2,3,4] tail
Queue size = 5,length: 5 front [1,2,3,4,5] tail
Queue size = 4,length: 5 front [2,3,4,5] tail
Queue size = 5,length: 5 front [2,3,4,5,6] tail
Queue size = 6,length: 10 front [2,3,4,5,6,7] tail
Queue size = 7,length: 10 front [2,3,4,5,6,7,8] tail
Queue size = 6,length: 10 front [3,4,5,6,7,8] tail
Queue size = 7,length: 10 front [3,4,5,6,7,8,9] tail

链表队列

链表队列介绍

声明两个指针，一个头指针，负责删除元素，即出队操作；一个尾指针，负责添加元素，即入队操作，其中在删除元素时直接将要删除的元素指向头指针，然后将头指针的next指针重新赋给头指针。在添加元素时，需要判断尾指针为空时，需要新声明尾指针，头指针等于尾指针，而尾指针不为空的条件下，直接声明尾指针的新的next指针，再重新声明为尾指针。

基本实现

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
public class LinkListQueue<E> implements Queue<E>{
	class Node {
		private E e;
		private Node next;

		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {

			return e.toString();
		}
	}

	public int size;
	public Node head,tail;// 声明一个头结点和一个尾结点

	public LinkListQueue() {
		size = 0;
		head=null;
		tail=null;
	}
	public int getSize() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
	public void enqueue(E e) {
		if(tail==null) {
			tail=new Node(e);
			head=tail;
		}
		else {
			tail.next=new Node(e);
			tail=tail.next;
		}
		size++;
	}
	public E dequeue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("queue is Empty");
		}
		Node first=head;
		head=head.next;
		first.next=null;
		if(head==null) {
			tail=null;
		}
		size--;
		return first.e;
	}
	public E getFront() {
		if(isEmpty()) {
			throw new IllegalArgumentException("queue is Empty");
		}
		return head.e;
	}
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		Node curr = head;
		stringBuilder.append("Queue Front: ");
		for (Node i = curr; i != null; i = i.next) {
			stringBuilder.append(i + "->");
		}
		stringBuilder.append("NULL tail ");
		return stringBuilder.toString();
	}

}

测试示例

1
2
3
4
5
6
7
8
9
10
11
12
13
public class LinkListQueueTest {
	public static void main(String[] args) {
		LinkListQueue linkListQueue=new LinkListQueue<>();
		for(int i=0;i<10;i++) {
			linkListQueue.enqueue(i);
			System.out.println(linkListQueue);
			if(i%3==2) {
				linkListQueue.dequeue();
				System.out.println(linkListQueue);
			}
		}
	}
}

输出示例

1
2
3
4
5
6
7
8
9
10
11
12
13
Queue Front: 0->NULL tail 
Queue Front: 0->1->NULL tail 
Queue Front: 0->1->2->NULL tail 
Queue Front: 1->2->NULL tail 
Queue Front: 1->2->3->NULL tail 
Queue Front: 1->2->3->4->NULL tail 
Queue Front: 1->2->3->4->5->NULL tail 
Queue Front: 2->3->4->5->NULL tail 
Queue Front: 2->3->4->5->6->NULL tail 
Queue Front: 2->3->4->5->6->7->NULL tail 
Queue Front: 2->3->4->5->6->7->8->NULL tail 
Queue Front: 3->4->5->6->7->8->NULL tail 
Queue Front: 3->4->5->6->7->8->9->NULL tail

性能比较

与数组实现的队列以及链表实现的队列进行入队出队的性能比较。

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

import java.util.Random;

public class QueueTimeTest {
	public static double QueueTest(Queue q,int count) {
		long start=System.currentTimeMillis();
		Random random=new Random();
		for(int i=0;i
			q.enqueue(random.nextInt(Integer.MAX_VALUE));
		}
		for(int i=0;i
			q.dequeue();
		}
		long end=System.currentTimeMillis();
		return (end-start)/1000.0;
	}

	public static void main(String[] args) {
		int count=100000;
		double time1=QueueTest(new LoopQueue(), count);
		System.out.println("LoopQueue:"+time1+"s");
		double time2=QueueTest(new ArrayQueue(), count);
		System.out.println("ArrayQueue:"+time2+"s");
		double time3=QueueTest( new LinkListQueue(), count);
		System.out.println("LinkListQueue:"+time3+"s");

	
}

结果显示

1
2
3
LoopQueue:0.026s
ArrayQueue:4.294s
LinkListQueue:0.012s

可以看出循环队列和链表实现的队列的时间复杂度较低。

0%