算法1.3—背包, 队列, 栈
算法1.3—背包, 队列, 栈

算法1.3—背包, 队列, 栈

内容纲要

简单的非变长背包

import edu.princeton.cs.algs4.Out;
import edu.princeton.cs.algs4.StdOut;

public class Bag<Item> {
    private Item[] items;
    private int pos=0;
    public Bag(int size){
        items = (Item[]) new Object[size];
    }

    void add(Item item){
        if(pos<=items.length)
            items[++pos] = item;
    }

    boolean isEmpty(){
        return pos==0;
    }

    int size(){
        return pos;
    }
}

class UnitTestForBag{
    public static void main(String[] args) {
        Bag bag = new Bag(10);
        StdOut.println(bag.isEmpty());
        bag.add("Babydoll");
        bag.add("Blazing");
        StdOut.println(bag.size());
    }
}

简单的非变长队列

import edu.princeton.cs.algs4.StdOut;

public class Queue<Item> {
    private Item[] queue;
    private int pos=0;

    public Queue(int size){
        queue = (Item[]) new Object[size];
    }

    void enqueue(Item item){
        if(pos<=queue.length)
            queue[pos++]  = item;
    }

    Item dequeue(){
        if(pos==0) return null;
        Item item = queue[0];
        for (int i = 0; i<pos; i++){
            queue[i] = queue[i+1];
        }
        queue[pos--]=null;
        return item;
    }

    boolean isEmpty(){
        return pos==0;
    }

    int size(){
        return pos;
    }
}

class UnitTestForQueue{
    public static void main(String[] args) {
        Queue queue = new Queue(10);
        StdOut.println(queue.dequeue());
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        StdOut.println(queue.dequeue());
        StdOut.println(queue.dequeue());
        StdOut.println(queue.size());
        StdOut.println(queue.dequeue());
        StdOut.println(queue.isEmpty());

    }
}

简单的非变长栈

import edu.princeton.cs.algs4.StdOut;

public class Stack<Item> {
    private Item[] stack;
    private int pos=0;

    public Stack(int size){
        stack = (Item[]) new Object[size];
    }

    void push(Item item){
        if(pos<=stack.length)
        stack[pos++] = item;
    }

    Item pop(){
        return this.isEmpty()?null:stack[--pos];    //prefix -- because the pos is at the next place (uninitialized)
    }

    boolean isEmpty(){
        return pos==0;
    }

    int size(){
        return pos;
    }
}

class UnitTestForStack{
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        StdOut.println(stack.isEmpty());
        StdOut.println(stack.pop());
        stack.push(2.2);
        stack.push(4.3);
        stack.push(3.2);
        StdOut.println(stack.pop());
        StdOut.println(stack.pop());
        StdOut.println(stack.size());
        StdOut.println(stack.isEmpty());

    }
}

Dijkstra的双栈运算符算法

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

//Dijkstra双栈算法
public class DijkstraDualStack {
    public static void Evaluate(){
        Stack<String> ops = new Stack<String>(15);
        Stack<Double> vals = new Stack<Double>(15);
        while(true){
            String s = StdIn.readString();
            if(s.equals("#"))   break;
            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 v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("-")) v = vals.pop() - v;
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                else if (op.equals("sqrt")) v = Math.sqrt(vals.pop());
                vals.push(v);
            }
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }

    public static void main(String[] args) {
        Evaluate();

    }
}

发表评论

您的电子邮箱地址不会被公开。