算法练习(111): Queue、Stack的互相拷贝(1.3.

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

1.3.41 复制队列。编写一个新的构造函数，使以下函数

Queue<Item> r = new Queue<Item>(q);

得到的 r 指向队列 q 的一个新的独立的副本。可以对 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());
        }
    }
}

题目

1.3.42 复制栈。为基于链表实现的栈编写一个新的构造函数，使以下代码

Stack<Item> t = new Stack<Item>(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);

}