本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 双端队列Deque
题目
1.3.33 Deque。一个双向队列(或者称为deque)和栈或队列类似，但它同时支持在两端添加或删除元素。Deque能够存储一组元素并支持如下API。
API for a generic double-ended queue
编写一个使用双向链表实现这份API的Deque类。以及一个使用动态数据组调整实现这份API的ResizingArrayDeque类。
1.3.33 Deque. A double-ended queue or deque (pronounced “deck”) is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collec- tion of items and supports the following API: Write a class Deque that uses a doubly-linked list to implement this API and a class ResizingArrayDeque that uses a resizing array.
分析
双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫作insertLeft()和insertRight()，以及removeLeft()和removeRight()。如果严格禁止调用insertLeft()和removeLeft()方法（或禁用右段的操作），双端队列功能就和栈一样。禁止调用insertLeft()和removeRight()（或相反的另一对方法），它的功能就和队列一样了。双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。
- Java中的双端队列类
Deque.java：Java的Util库自带Deque类，因此可以直接new一个Deque对象，大家可以找相关教程查看Deque的用法 - Objective-C中的双端队列
CFArray.C：是CoreFoundation框架中的数组实现类，它就通过Deque实现的。关于CoreFoundation框架就不多说了，iOS开发的小伙伴应该都知道。
我们之前已经使用过Queue，只要稍加改造就可以，如下
public class ResizingArrayDeque1<Item> implements Iterable<Item> {
private Item[] a;
private int N;
public boolean isEmpty() {
return N == 0;
}
//构造函数
public ResizingArrayDeque1() {
a = (Item[]) (new Object[1]);
}
//大小
public int size() {
return N;
}
public void pushLeft(Item item) {
Item[] temp = (Item[]) (new Object[N + 1]);
temp[0] = item;
for (int i = 0; i < N; i++) {
temp[i + 1] = a[i];
}
a = temp;
N++;
}
private void resize(int max) {
Item[] temp = (Item[]) (new Object[max]);
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
public void pushRight(Item item) {
if (N == a.length) {
resize(N * 2);
}
a[N++] = item;
}
public Item popLeft() {
Item[] temp = (Item[]) (new Object[N + 1]);
Item popedItem = a[0];
for (int i = 0; i < N; i++) {
temp[i] = a[i + 1];
}
a = temp;
N--;
return popedItem;
}
public Item popRight() {
Item popedItem = a[--N];
a[N] = null;
if (a.length == 4 * N) {
resize(a.length / 2);
}
return popedItem;
}
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
int index = 0;
public boolean hasNext() {
return index != N;
}
public Item next() {
return a[index++];
}
public void remove() {
}
}
}
完整的代码在这里：ResizingArrayDeque1.java
这个答案的问题在于虽然pushRight的效率很高，只需要在数组后面追加元素就行了，但PushLeft的时候每次都要resize，因此耗时较多。所以不是很好的实现
public void pushLeft(Item item) {
//pushLeft的时候每次都新建对象，耗时
Item[] temp = (Item[]) (new Object[N + 1]);
temp[0] = item;
for (int i = 0; i < N; i++) {
temp[i + 1] = a[i];
}
a = temp;
N++;
}
要解决这个问题，我们需要换一种思路。
下面开始我们的主题，如何更好的创建一个双端队列。
1.init
Deque init
如图，创建数组的时候，我们默认给数组大小设置为2（想想这是为什么）。并给两个指针，head和tail 并且赋值为1，至于为什么head和tail的初始值不是0，我们接下来继续分析。
2.pushLeft
public void pushLeft(Item item) {
a[--head] = item;
}
pushLeft的时候，我们是要给head减一的，因此head和tail的初始值最好不要是0。
Deque pushLeft
如图，push了一个元素"我的"，push成功以后，head减一，这个时候head指针就指向了数组第0个元素。
2.pushRight
public void pushRight(Item item) {
a[tail++] = item;
}
Deque pushRight
这里需要注意的是，tail的大小已经超过数组的边界了，因为数组大小是2，tail=2的时候，已经超出a[1]。
3.popLeft
public Item popLeft() {
return a[head++];
}
跟pushLeft操作正好相反
Deque popLeft
4.Resize
在Deque中Resize操作也有很大不一样
private void resize(int max) {
if (max < 3) {
max = 3;
}
Item tmp[] = (Item[]) new Object[max];
int j = max / 3;
for (int i = head; i < tail; i++) {
tmp[j++] = a[i];
}
a = tmp;
head = max / 3;
tail = j;
}
具体的不一样是
(1)什么时候resize
(2)resize的参数怎么传
(3)resize后的head和tail怎么处理
下面我们一一解答：
(1)因为当我们每次pushLeft的时候head都会减一，当减到head为0的时候，这个时候就必须要resize了；同理，pushRight当加一加到数组大小后也需要resize。
(2)按我们以前的经验应该是传4，因为初始数组大小是2，每次调整都是2倍2倍调整，假设我们大小调整为4，那就相当于给数组的头部和尾部各加个位置，其实也是可以的，但两边各家一个元素其实幅度还是太小，因此我们这里选择，给上下各加当前大小的两倍。
(3)Resize后，因为数组的元素从中间开始加了，head也自然取中间数，tail取head+size()
答案
public class ResizingArrayDeque2<Item> implements Iterable<Item> {
private Item[] a;
private int head = 1;
private int tail = 1;
public boolean isEmpty() {
return head == tail;
}
public ResizingArrayDeque2() {
a = (Item[]) (new Object[2]);
}
public int size() {
return tail - head;
}
public void pushLeft(Item item) {
if (head == 0) {
resize(3 * size());
}
a[--head] = item;
}
private void resize(int max) {
if (max < 3) {
max = 3;
}
Item tmp[] = (Item[]) new Object[max];
int j = max / 3;
for (int i = head; i < tail; i++) {
tmp[j++] = a[i];
}
a = tmp;
head = max / 3;
tail = j;
}
public void pushRight(Item item) {
if (tail == a.length) {
resize(3 * size());
}
a[tail++] = item;
}
public Item popLeft() {
if (isEmpty()) {
return null;
}
if (size() * 6 < a.length) {
resize(size() * 3);
}
return a[head++];
}
public Item popRight() {
if (isEmpty()) {
return null;
}
if (size() * 6 < a.length) {
resize(size() * 3);
}
return a[--tail];
}
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
private int index = head;
public boolean hasNext() {
return index < tail;
}
public Item next() {
Item x = a[index++];
return x;
}
public void remove() {
}
}
public static void main(String[] args) {
ResizingArrayDeque2<String> deque = new ResizingArrayDeque2<String>(10);
deque.pushRight("我");
deque.pushRight("的");
deque.pushRight("名字");
deque.pushRight("叫顶级程序员不穿女装");
deque.pushRight("微博:https://m.weibo.cn/p/1005056186766482");
for (String string : deque) {
System.out.println(string);
}
System.out.println("===========================");
ResizingArrayDeque2<String> deque1 = new ResizingArrayDeque2<String>(10);
deque1.pushLeft("我");
deque1.pushLeft("的");
deque1.pushLeft("名字");
deque1.pushLeft("叫顶级程序员不穿女装");
deque1.pushLeft("微博:https://m.weibo.cn/p/1005056186766482");
for (String string : deque1) {
System.out.println(string);
}
System.out.println("===========================");
deque.popLeft();
for (String string : deque) {
System.out.println(string);
}
System.out.println("===========================");
deque1.popRight();
for (String string : deque1) {
System.out.println(string);
}
}
}
代码索引
视频讲解
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
网友评论