算法练习(32):栈拷贝、迭代器(1.3.12)

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

算法(第4版)

知识点

• 栈拷贝
• Java迭代器

题目

1.3.12 编写一个可迭代的Stack用例，它含有一个静态的copy()方法，接受一个字符串的栈作为参数并返回该栈的一个副本。注意：这种能力是迭代器价值的一个重要体现，因为有了它我们无需改变基本 API 就能实现这种功能。

---

1.3.12 Write an iterable Stack client that has a static method copy() that takes a stack of strings as argument and returns a copy of the stack. Note: This ability is a prime example of the value of having an iterator, because it allows development of such func- tionality without changing the basic API.

分析

由于栈的迭代器是逆向的迭代器，实现时需要注意方向问题。
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

public class Stack2<Item> implements Iterable<Item> {

    /**
     * 
     ***** 链表实现*****
     */
    private int N;
    private Node first;

    private class Node {
        Item item;
        Node next;
    }

    public Stack2() {
        N = 0;
        first = null;
    }

    public void push(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    public Item top() {
        return first.item;
    }

    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public boolean isEmpty() {
        // 或:first = null
        return N == 0;
    }

    public int size() {
        return N;
    }

    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new ArrayIterater();
    }

    private class ArrayIterater implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            // TODO Auto-generated method stub
            return current != null;
        }

        public Item next() {
            // TODO Auto-generated method stub
            Item item = current.item;
            current = current.next;
            return item;
        }

        public void remove() {
            // TODO Auto-generated method stub
        }

    }

    public static Stack2<String> copy(Stack2<String> stack2) {
        Stack2<String> resultStack = new Stack2<String>();
        //逆序1
        Stack2<String> tempStack = new Stack2<String>();
        Iterator<String> iterator = stack2.iterator();
        while (iterator.hasNext()) {
            tempStack.push(iterator.next());
        }
        //逆序2
        Iterator<String> tempIterator = tempStack.iterator();
        while (tempIterator.hasNext()) {
            resultStack.push(tempIterator.next());
        }

        return resultStack;
    }

    public static void main(String[] args) {
        // String testString =
        // "it was - the best - of times - - - it was - the - -";
        Stack2<String> stack = new Stack2<String>();
        stack.push("我");
        stack.push("的");
        stack.push("名字");
        stack.push("叫");
        stack.push("顶级程序员不穿女装");
        stack.push("微博:https://m.weibo.cn/p/1005056186766482");
        //打印
        System.out.println("原栈逆序输出:");
        for (String string : stack) {
            System.out.print(string);
        }
        System.out.println("");
        System.out.println("开始拷贝...");
        //拷贝
        Stack2<String> stack2 = Stack2.copy(stack);
        System.out.println("拷贝成功");
        System.out.println("开始打印拷贝后的栈");
        //创建迭代器
        for (String string : stack2) {
            System.out.print(string);
        }
    }
}

输出结果

原栈逆序输出:
微博:https://m.weibo.cn/p/1005056186766482顶级程序员不穿女装叫名字的我
开始拷贝...
拷贝成功
开始打印拷贝后的栈
微博:https://m.weibo.cn/p/1005056186766482顶级程序员不穿女装叫名字的我

代码索引

Stack2.java

视频讲解

顶级程序员教你学算法(32)-栈拷贝、迭代器(1.3.12)

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。