简单的非变长背包
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();
}
}
浏览量: 9