数据结构之Deque

74 阅读 0 评论 49 点赞

我是靠谱客的博主英俊山水，这篇文章主要介绍数据结构之Deque，现在分享给大家，希望可以做个参考。

Deque的ADT定义如下：

复制代码

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
package com.dzlijian.utils.comments;

/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列ADT 
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public interface Deque<E> {
	public int size();
	public boolean  empty();
	public void  addFirst(E e);
	public void  addLast(E e);
	
	public E  removeFirst();
	public E  removeLast();
	
	public E  peekFirst();
	public E  peekLast();

}

1，数组方式实现：

复制代码

package com.dzlijian.utils.comments;

import java.util.Arrays;

import org.apache.commons.collections.list.GrowthList;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列数组实现
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class ArrayDeque<E> implements Deque<E> {
	private static final int DEFAULT_CAPACITY=10;
	private int size;
	private E[] data;
	private int head=-1;
	private int tail=-1;
	
	public ArrayDeque(int capacity){
		data=(E[])new Object[capacity];
		size=0;
	}
	public ArrayDeque(){
		this(DEFAULT_CAPACITY);
	}

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

@Override
	public boolean empty() {
		return size==0;
	}
	
	private void grow(int capacity){
		if(capacity<=0){
			throw new IllegalArgumentException("新建数组长度非法");
		}
		if(capacity<DEFAULT_CAPACITY){
			return;
		}
		if(capacity>data.length){
			data=Arrays.copyOf(data, capacity);
		}else{
			E[] newdata=(E[])new Object[capacity];
			head=0;
			tail=0;
			for(int i=0;i<data.length;i++){
				if(data[i]!=null){
					newdata[tail++]=data[i];
				}
			}
			tail--;
			data=newdata;
		}
		
		
	}

@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(head==0){
			E[] newdata=(E[])new Object[data.length];
			newdata[0]=e;
			for(int i=1;i<data.length;i++){
				newdata[i]=data[i-1];
			}
			data=newdata;
			tail++;
		}else{
			data[--head]=e;
		}
		size++;
	}

@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(tail<data.length-1){
			data[++tail]=e;
		}else{
			E[] newdata=(E[])new Object[data.length];
			newdata[tail]=e;
			for(int i=data.length-1;i>0;i--){
				newdata[i-1]=data[i];
			}
			data=newdata;
			head--;
		}
		size++;
	}

@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[head];
		data[head]=null;
		head++;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[tail];
		data[tail]=null;
		tail--;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[head];
	}

@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[tail];
	}

public static void main(String[] args) {
		Deque<Integer> test=new ArrayDeque<Integer>();
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
	}
}

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
package com.dzlijian.utils.comments;

import java.util.Arrays;

import org.apache.commons.collections.list.GrowthList;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列数组实现
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class ArrayDeque<E> implements Deque<E> {
	private static final int DEFAULT_CAPACITY=10;
	private int size;
	private E[] data;
	private int head=-1;
	private int tail=-1;
	
	public ArrayDeque(int capacity){
		data=(E[])new Object[capacity];
		size=0;
	}
	public ArrayDeque(){
		this(DEFAULT_CAPACITY);
	}

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

	@Override
	public boolean empty() {
		return size==0;
	}
	
	private void grow(int capacity){
		if(capacity<=0){
			throw new IllegalArgumentException("新建数组长度非法");
		}
		if(capacity<DEFAULT_CAPACITY){
			return;
		}
		if(capacity>data.length){
			data=Arrays.copyOf(data, capacity);
		}else{
			E[] newdata=(E[])new Object[capacity];
			head=0;
			tail=0;
			for(int i=0;i<data.length;i++){
				if(data[i]!=null){
					newdata[tail++]=data[i];
				}
			}
			tail--;
			data=newdata;
		}
		
		
	}

	@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(head==0){
			E[] newdata=(E[])new Object[data.length];
			newdata[0]=e;
			for(int i=1;i<data.length;i++){
				newdata[i]=data[i-1];
			}
			data=newdata;
			tail++;
		}else{
			data[--head]=e;
		}
		size++;
	}

	@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(tail<data.length-1){
			data[++tail]=e;
		}else{
			E[] newdata=(E[])new Object[data.length];
			newdata[tail]=e;
			for(int i=data.length-1;i>0;i--){
				newdata[i-1]=data[i];
			}
			data=newdata;
			head--;
		}
		size++;
	}

	@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[head];
		data[head]=null;
		head++;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

	@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[tail];
		data[tail]=null;
		tail--;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

	@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[head];
	}

	@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[tail];
	}

	public static void main(String[] args) {
		Deque<Integer> test=new ArrayDeque<Integer>();
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
	}
}

2，链表实现方式1：

复制代码

package com.dzlijian.utils.comments;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列链表实现1
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class LinkedDeque<E> implements Deque<E> {
	private int size;
	private Node<E> head;
	private Node<E> tail;
	
	private static class Node<E>{
		private Node<E> front;
		private E data;
		private Node<E> next;
		
		public Node(Node<E> front,E e,Node<E> next){
			this.front=front;
			this.data=e;
			this.next=next;
		}
	}
	
	public LinkedDeque(){
		size=0;
		head=null;
		tail=null;
	}

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

@Override
	public boolean empty() {
		return size==0;
	}

@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=head;
		head=new Node<E>(null,e,head);
		pre.front=head;
		size++;
	}

@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=tail;
		tail=new Node<E>(tail,e,null);
		pre.next=tail;
		size++;
	}

@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=head;
		head=result.next;
		if(head!=null){
			head.front=null;
		}
		
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=tail;
		tail=result.front;
		if(tail!=null){
			tail.next=null;
		}
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return head.data;
	}

@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return tail.data;
	}
	
	public static void main(String[] args) {
		Deque<Integer> test=new LinkedDeque<Integer>();
		
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){

test.removeFirst();
		}
		System.out.println(test.size());
		
		
	}

}

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
package com.dzlijian.utils.comments;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列链表实现1
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class LinkedDeque<E> implements Deque<E> {
	private int size;
	private Node<E> head;
	private Node<E> tail;
	
	private static class Node<E>{
		private Node<E> front;
		private E data;
		private Node<E> next;
		
		public Node(Node<E> front,E e,Node<E> next){
			this.front=front;
			this.data=e;
			this.next=next;
		}
	}
	
	public LinkedDeque(){
		size=0;
		head=null;
		tail=null;
	}

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

	@Override
	public boolean empty() {
		return size==0;
	}

	@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=head;
		head=new Node<E>(null,e,head);
		pre.front=head;
		size++;
	}

	@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=tail;
		tail=new Node<E>(tail,e,null);
		pre.next=tail;
		size++;
	}

	@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=head;
		head=result.next;
		if(head!=null){
			head.front=null;
		}
		
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

	@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=tail;
		tail=result.front;
		if(tail!=null){
			tail.next=null;
		}
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

	@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return head.data;
	}

	@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return tail.data;
	}
	
	public static void main(String[] args) {
		Deque<Integer> test=new LinkedDeque<Integer>();
		
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){

			test.removeFirst();
		}
		System.out.println(test.size());
		
		
	}

}

3，链表实现Deque2:
package com.dzlijian.utils.comments;
/**
*

@ClassName: Deque
@Description:双端队列链表实现2
@author: 长子科技
@date: 2021年7月7日下午11:03:32
@param
@Copyright: 2021 www.tydic.com Inc. All rights reserved.
*/
public class LinkedDeque2 implements Deque {
private int size;
private Node head;
private Node tail;

private static class Node{
private E data;
private Node next;
复制代码 public Node(E e,Node<E> next){ this.data=e; this.next=next; }
```
1
2
3
4
5
 public Node(E e,Node<E> next){
 	this.data=e;
 	this.next=next;
 }
```
}

public LinkedDeque2(){
size=0;
head=null;
tail=null;
}

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

@Override
public boolean empty() {
return size==0;
}

@Override
public void addFirst(E e) {
if(enull){
throw new IllegalArgumentException(“插入参数为空！！”);
}
if(size0){
head=new Node(e,null);
tail=head;
size++;
return;
}
head=new Node(e,head);
size++;
}

@Override
public void addLast(E e) {
if(enull){
throw new IllegalArgumentException(“插入参数为空！！”);
}
if(size0){
head=new Node(e,null);
tail=head;
size++;
return;
}
复制代码 Node<E> pre=tail; tail=new Node<E>(e,null); pre.next=tail; size++;
```
1
2
3
4
5
 Node<E> pre=tail;
 tail=new Node<E>(e,null);
 pre.next=tail;
 size++;
```
}

@Override
public E removeFirst() {
if(size0){
throw new RuntimeException(“空队列！”);
}
Node result=head;
head=head.next;
size–;
if(size0){
head=null;
tail=null;
}
return result.data;
}

@Override
public E removeLast() {
if(size==0){
throw new RuntimeException(“空队列！”);
}
Node result=tail;
//使用单向节点，此时需要循环查找，非常耗时。
Node i=head;
while(i.next!=tail&&i.next!=null){
i=i.next;
复制代码 } tail=i; i.next=null; size--; if(size==0){ head=null; tail=null; } return result.data;
```
1
2
3
4
5
6
7
8
9
10
 }
 tail=i;
 i.next=null;
 size--;
 if(size==0){
 	head=null;
 	tail=null;
 }
 return result.data;
```
}

@Override
public E peekFirst() {
if(size==0){
throw new RuntimeException(“空队列！”);
}
return head.data;
}

@Override
public E peekLast() {
if(size==0){
throw new RuntimeException(“空队列！”);
}
return tail.data;
}

public static void main(String[] args) {
Deque test=new LinkedDeque2();
for(int i=1;i<6;i++){
test.addFirst(i);
}
System.out.println(test.size());
for(int i=1;i<6;i++){
test.addLast(i);
}
复制代码 System.out.println(test.size()); for(int i=1;i<6;i++){ test.removeFirst(); } System.out.println(test.size()); for(int i=1;i<6;i++){ test.removeLast(); } System.out.println(test.size());
```
1
2
3
4
5
6
7
8
9
10
11
12
 System.out.println(test.size());
 
 for(int i=1;i<6;i++){
 	test.removeFirst();
 }
 System.out.println(test.size());
 
 for(int i=1;i<6;i++){
 	test.removeLast();
 }
 System.out.println(test.size());
```
}