本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 队列、栈的复制
题目
1.3.41 复制队列。编写一个新的构造函数，使以下代码：
Queue r = new Queue(q);
得到的 r 指向队列 q 的一个新的独立的副本。可以对 q 或 r 进行任意入列或出列操作但它们不会相互影响。
1.3.41 Copy a queue. Create a new constructor so that
Queue<Item> r = new Queue<Item>(q);
makes r a reference to a new and independent copy of the queue q. You should be able to push and pop from either q or r without influencing the other. Hint : Delete all of the elements from q and add these elements to both q and r.
分析
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅
答案
public static class Queue<Item> {
private int N;
public Queue(Queue<Item> q) {
int size = q.size();
for (int i = 0; i < size; i++) {
this.enqueue(q.dequeue());
}
}
private class Node {
Item item;
Node next;
}
private Node first;
private Node last;
public Queue() {
}
public boolean isEmpty() {
if (first == null)
return true;
return false;
}
public int size() {
return N;
}
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if (this.isEmpty()) {
first = last;
} else {
oldLast.next = last;
}
N++;
}
public Item dequeue() {
Item item = first.item;
first = first.next;
if (this.isEmpty()) {
last = null;
}
N--;
return item;
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue("I");
queue.enqueue("am");
queue.enqueue("Kyson");
Queue queue1 = new Queue(queue);
int size = queue1.size();
for (int i = 0; i < size; i++) {
System.out.println(queue1.dequeue());
}
}
}
题目
复制栈。为基于链表实现的栈编写一个新的构造函数，使以下代码
Stack t = new Stack(s);
得到的 t 指向栈 s 的一个新的独立的副本。
1.3.42 Copy a stack. Create a new constructor for the linked-list implementation of Stack so that
Stack<Item> t = new Stack<Item>(s);
makes t a reference to a new and independent copy of the stack s.
答案
public class Stack<Item> implements Iterable<Item> {
private Item[] a;
private int N;
public Stack(int cap) {
a =(Item[]) new Object[cap];
}
public Stack(Stack<Item> s) {
Stack<Item> xx = new Stack<Item>(1);
a =(Item[]) new Object[1];
Stack<Item>.StackIterator xit = s.iterator();
while (xit.hasNext()){
xx.push(xit.next());
}
Stack<Item>.StackIterator xxit = xx.iterator();
while (xxit.hasNext()) {
this.push(xxit.next());
}
}
public void push(Item item) {
if (a.length == N) {
resize(2 * N);
}
a[N++] = item;
}
public void resize(int max)
{
Item[] temp = (Item[]) new Object[max];
for (int i = 0 ; i < N ; ++i) {
temp[i] = a[i];
}
a = temp;
}
public boolean isEmpty() {
return N == 0;
}
public Item pop() {
Item item = a[--N];
a[N] = null;
if (N > 0 && a.length == N / 4) {
resize(a.length / 2);
}
return item;
}
public StackIterator iterator()
{
return new StackIterator();
}
private class StackIterator implements Iterator<Item>
{
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
}
}
测试用例
public static void main(String[] args)
{
Stack<String> a = new Stack<>(10);
a.push("1");
a.push("2");
a.push("3");
a.push("4");
a.push("5");
a.push("6");
a.pop();
a.pop();
Stack<String> b= new Stack<>(a);
}
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
