背包、队列和栈

程序员文章站 2022-06-01 08:30:11

...

Java中的Iterable与Iterator详解

文章目录

算术表达式求值
迭代
栈

能够动态调整数组大小的实现（LIFO）

对象游离

链表实现（LIFO）

队列
背包

三种数据类型：背包（Bag）、队列（Queue）和栈（Stack）。它们的不同之处就在于删除或者访问对象的顺序不同。

算术表达式求值

E.W.Dijkstra 发明了一个非常简单的算法，用到了两个栈（操作数栈、运算符栈）。具体思路：

将操作数压入（push）操作数栈；
将运算符压入运算符栈；
忽略左括号；
在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个括号后，操作数栈上就只剩一个表达式的值。运算顺序：

(1 + ((2 + 3) * (4 * 5)))
(1 + (5 * (4 * 5)))
(1 + (5 * 20))
(1 + 100)
101

Dijkstra 的双栈算术表达式求值算法

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<>();     // 运算符栈
        Stack<Double> vals = new Stack<>();    // 操作数栈
        while (!StdIn.isEmpty()) {
            // readString() 方法使用了 Scanner.next() 来读取字符串
            String s = StdIn.readString();
            if (s.equals("("));
            else if (s.equals("+")) ops.push(s);
            else if (s.equals("-")) ops.push(s);
            else if (s.equals("*")) ops.push(s);
            else if (s.equals("/")) ops.push(s);
            else if (s.equals("sqrt")) ops.push(s);
            else if (s.equals(")")) {
                String op = ops.pop();
                double val = vals.pop();
                if (op.equals("+")) val = vals.pop() + val;
                else if (op.equals("-")) val = vals.pop() - val;
                else if (op.equals("*")) val = vals.pop() * val;
                else if (op.equals("/")) val = vals.pop() / val;
                else if (op.equals("sqrt")) val = Math.sqrt(val);
                vals.push(val);
            } else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}

迭代

我们知道 foreach 语句可以迭代访问集合中的数据，其实它本质上与 while 语句是等价的，看这两组代码：

Stack<String> collection = new Stack<>();

for (String s : collection)
    StdOut.println(s);

Stack<String> collection = new Stack<>();
Iterator<String> i = collection.iterator();

while (i.hasNext()) {
    String s = i.next();
    StdOut.println(s);
}

可迭代的集合的集合数据类型需要：

实现一个 iterator() 方法并返回一个 Iterator 对象；
Iterator 类必须包含两个方法：hasNext()（返回一个 boolean 值）和 next()（返回一个集合中的泛型元素）。

对与可迭代的数据类型，Java 中定义了所需接口 java.lang.Iterable ：

public interface Iterable<Item> {
    Iterator<Item> iterator();
}

我们使用接口机制来指定一个类所必须实现的方法，所以在一个需要迭代的集合中我们必须实现接口中的 iterator() 方法。

Java容器中，所有的 Collection 子类会实现 Iteratable 接口以实现 foreach 功能，Iteratable 接口的实现又依赖于实现了 Iterator 的内部类(参照 LinkedList 中listIterator() 和 descendingIterator() 的 JDK 源码)。

有的容器类会有多个实现Iterator 接口的内部类，通过返回不同的迭代器实现不同的迭代方式。

栈

能够动态调整数组大小的实现（LIFO）

package DataStructureAndAlgorithms.DataStructure;

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[1];
    private int N = 0;
    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }

    /**
     * 将栈移动到一个大小为 max 的新数组
     * @param max
     */
    private void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }
    private void push(Item item){
        if (N == a.length) {
            resize(2 * a.length);
        }
        a[N++] = item;
    }
    private Item pop(){
        Item item = a[--N];
        a[N] = null;//避免对象游离
        if (N > 0 && N == a.length/4) {
            resize(a.length / 2);
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }
    //嵌套类(非静态的嵌套类也称为内部类)可以访问包含它的类的实例变量
    private class ReverseArrayIterator implements Iterator<Item>{

        //支持后进先出的迭代
        private int i = N;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public Item next() {
            return a[--i];
        }

        @Override
        public void remove() {

        }

    }

    public static void main(String[] args) {
        ResizingArrayStack<String> r = new ResizingArrayStack<>();
        r.push("1");
        r.push("2");
        r.push("3");
        r.pop();
       r.forEach(e -> System.out.println(e));//2 1
    }
}

对象游离

在上面使用 pop() 方法弹出了一个元素，它就不会再被访问了，但数组中的引用仍可以让它继续存在。像这种保存一个不需要的对象的引用的情况就称之为游离。
为了避免游离，我们只需要将弹出的元素值设置为 null，这会覆盖无用的引用，并使系统在该元素使用完毕后回收它的内存。

链表实现（LIFO）

package DataStructureAndAlgorithms.DataStructure;


import java.util.Iterator;

/**
 * 链表实现 LIFO
 *
 * @param <Item>
 */
public class Stack<Item> implements Iterable<Item>{
    private Node first;
    private int N;


    /**
     * 私有嵌套类的一个特点是只有包含它的类能够直接访问它的实例变量
     */
    private class Node {
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
        //写法二
//        return  N == 0;
    }

    public int size(){
        return N;
   }
    //压栈 向栈顶添加元素
    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
   }
    //弹栈  从栈顶删除元素
    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
   }

    /**
     * 集合数据类型必须实现一个 iterator() 方法并返回一个 Iterator 对象
     * Iterator 类必须包含两个方法：hasNext() 和 next() （返回集合中的一个泛型元素）
     * @return
     */

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item>{

        private Node current = first;
        public boolean hasNext(){
            return current != null;
        }
        public void remove(){}

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
       s.push("abc");
       s.push("jagoh");
       s.pop();
        for (String item : s
             ) {
            System.out.println(item);
        }
        System.out.println("(" + s.size() + " left on stack");
    }
}

背包、队列和栈

队列

package DataStructureAndAlgorithms.DataStructure;

import java.util.Iterator;

/**
 * FIFO 队列
 * @param <Item>
 */
public class Queue<Item> implements Iterable<Item>{
    private Node first;//指向最早添加的结点的链接
    private Node last;//指向最近添加的结点的链接
    private int N;

    private class Node{

        Item item;
        Node next;
    }
    public boolean isEmpty(){
        return first == null;
    }
    public int size(){
        return N;
    }
    /**
     * 向表尾添加元素
     * @param item
     */
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()){
            first = last;
        }else {
            oldLast.next = last;
        }
        N++;

    }

    /**
     * 从表头删除元素
     */
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if (isEmpty()){
            last = null;
        }
        N--;
        return item;
    }
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{

        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {

        }
    }

    public static void main(String[] args) {
        Queue<String> queue = new Queue<>();
        queue.enqueue("algha");
        queue.enqueue("lahg");
        queue.enqueue("lahg");
        queue.dequeue();
        for (String item : queue
             ) {
            System.out.println(item);
        }
    }

}

背包、队列和栈

背包

package DataStructureAndAlgorithms.DataStructure;

import java.util.Iterator;

/**
 * LIFO
 * 顺序不重要
 */
public class Bag<Item> implements Iterable<Item>{
    private Node first;
    private class Node {
        Item item;
        Node next;
    }

    /**
     * 和Stack的 push() 方法相同
     * @param item
     */
    public void add(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
    }
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{

        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {

        }
    }

    public static void main(String[] args) {
        Bag<String> bag = new Bag<>();
        bag.add("1");
        bag.add("1");
        bag.add("1");
        for (String b : bag){
            System.out.println(b);
        }

    }
}

上一篇： IText之pdf表单填充

下一篇：关于Jackson的使用说明

背包、队列和栈

文章目录

算术表达式求值

迭代

栈

能够动态调整数组大小的实现（LIFO）

对象游离

链表实现（LIFO）

队列

背包

优先队列和堆

堆和优先队列

堆和优先队列

堆和优先队列

堆和优先队列

优先队列和堆

优先队列和堆

【玩转数据结构】----优先队列和堆

php redis分布式锁和任务队列代码实例详解

堆排序和优先级队列priority_queue