本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- Queue概念
- Queue数组实现
题目
1.3.13 假设某个用例程序会进行一系列入栈和出栈操作。入栈操作会将整数0到9按顺序压入栈；出栈操作会打印返回值。下面哪种顺序是不可能产生的？
1.3.13 Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations. The enqueue operations put the integers 0 through 9 in order ontothe queue; the dequeue operations print out the return value. Which of the following sequence(s) could not occur?
a. 0 1 2 3 4 5 6 7 8 9
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
d. 4 3 2 1 0 5 6 7 8 9
分析
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅
答案
b是不能产生的。
题目
1.3.14 编写一个类ResizingArrayQueueOfStrings，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。
1.3.14 Develop a class ResizingArrayQueueOfStrings that implements the queue abstraction with a fixed-size array, and then extend your implementation to use array resizing to remove the size restriction.
分析
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅
答案
public class ResizingArrayQueueOfStrings {
private int N;
private String[] items;
public class Node {
String item;
Node next;
}
public ResizingArrayQueueOfStrings(int cap) {
items = new String[cap];
}
public void enqueue(String item) {
if (N == items.length) {
resize(items.length * 2);
}
items[N++] = item;
}
public String dequeue() {
// 拷贝所有的老数组元素到新的数组，并命名为oldItems
String[] oldItems = new String[N];
for (int i = 0; i < N; i++) {
oldItems[i] = items[i];
}
// 重新设置Stack的大小
items[--N] = null;
if (N == items.length / 4) {
resize(items.length / 2);
}
// 获取新数组
for (int i = 0; i < N; i++) {
items[i] = oldItems[i + 1];
}
return oldItems[0];
}
public boolean isEmpty() {
return true;
}
public int size() {
return N;
}
private void resize(int max) {
String[] tempItems = new String[max];
for (int i = 0; i < N; i++) {
tempItems[i] = items[i];
}
items = tempItems;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ResizingArrayQueueOfStrings strings = new ResizingArrayQueueOfStrings(2);
strings.enqueue("我");
strings.enqueue("的");
strings.enqueue("名字");
strings.enqueue("叫顶级程序员不穿女装");
strings.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
System.out.println(strings.dequeue());
System.out.println(strings.dequeue());
System.out.println(strings.dequeue());
System.out.println(strings.dequeue());
System.out.println(strings.dequeue());
// System.out.println(strings.dequeue());
}
}
代码索引
ResizingArrayQueueOfStrings.java
视频讲解
顶级程序员教你学算法(33): Queue的数组实现(1.3.13-1.3.14)
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
