栈
- 先进后出
- 为栈中的每一个元素定义一个结点Node，这个结点包括元素本身和下一个结点的引用，栈底结点的下一个为null。
- 只有一个栈顶指针
实现出栈、入栈和迭代等操作。
public class Stack<T> implements Iterable<T> { //栈顶元素 private Node<T> first; //栈长度 private int n; //栈的存储单位：一个存放当前元素和下一个结点的结点 private static class Node<T>{ private T item; private Node<T> next; } /** * @Author haien * @Description 初始化一个空栈 * @Date 19:56 2018/10/25 **/ public Stack(){ first = null; n=0; } public boolean isEmpty(){ return first==null; } public int size(){ return n; } public void push(T item){ Node<T> oldfirst=first; first=new Node<T>(); first.item=item; first.next=oldfirst; n++; } public T pop(){ if(isEmpty()) throw new NoSuchElementException(); T item=first.item; first=first.next; n--; return item; } /** * @Author haien * @Description 出栈但不删除元素 * @Date 2018/10/25 * @Param [] * @return void **/ public T peek(){ if(isEmpty()) throw new NoSuchElementException(); return first.item; } /** * @Author haien * @Description 把所有元素都连成一个字符串 * @Date 2018/10/25 * @Param [] * @return java.lang.String **/ @Override public String toString() { StringBuilder s=new StringBuilder(); //适用于处理大量字符串 for(T item:this){ s.append(item); s.append(' '); } return s.toString(); } @Override public Iterator<T> iterator(){ return new ListIterator<T>(first); } private class ListIterator<T> implements Iterator<T>{ private Node<T> current; public ListIterator(Node<T> current) { this.current = current; } @Override public boolean hasNext() { return current!=null; } @Override public T next() { if(!hasNext()) throw new NoSuchElementException(); T item=current.item; current=current.next; return item; } @Override public void remove(){ throw new UnsupportedOperationException(); } } }应用：用两个栈实现四则运算
/** * @Author haien * @Description 用栈实现四则运算 * @Date 2018/10/29 **/ public class Evaluate { //设置优先级 public static int priority(String s) throws ValidationException { switch(s){ case "(": return 4; case "*": case "/": return 3; case "+": case "-": return 2; case ")": return 1; default: throw new ValidationException("算术表达式格式错误!"); } } public static void main(String[] args) throws ValidationException { //数字栈 Stack<Double> s1=new Stack<>(); //符号栈 Stack<String> s2=new Stack<>(); StringBuilder num=new StringBuilder(""); int i=0; double a=0.0; System.out.println("请输入表达式："); //读取表达式 while(!StdIn.isEmpty()){ //获取表达式 String s=StdIn.readLine().replaceAll("\\s*",""); //获取一行字符串；去空白符 //遍历表达式 while(i<=s.length()){ //数字（支持多位数、小数） if(i<s.length()&&(s.charAt(i)>='0'&&s.charAt(i)<='9'||s.charAt(i)=='.')){ num.append(s.charAt(i)); i++; if(i==s.length()||((s.charAt(i)<'0'||s.charAt(i)>'9')&&s.charAt(i)!='.')){ if(!ValidatorUtil.isNumeric(num)){ //是否整数或小数 throw new ValidationException("算术表达式格式错误!"); } s1.push(Double.parseDouble(num.toString())); num=new StringBuilder(""); } } //运算符 //无效括号 else if(i<s.length()&&s.charAt(i)==')'&&!s2.isEmpty()&&s2.peek().equals("(")) { s2.pop(); //记得把栈里没用的左括号弹掉 i++; } //进栈(栈为空||运算符优先级大于栈顶||栈顶为左括号) else if(i<s.length() &&(s2.isEmpty() ||priority(String.valueOf(s.charAt(i))) > priority(s2.peek()) ||s2.peek().equals("(")) ){ s2.push(String.valueOf(s.charAt(i))); i++; } //表达式只有一个数字 else if(s1.size()==1) break; //弹栈（i>=字符串长度时就已经读取完了，但是符号栈还有就还要进行运算||符号优先级低于栈顶） else if((i>=s.length() && !s2.isEmpty()) || (priority(String.valueOf(s.charAt(i))) <= priority(s2.peek()))){ //- / 记得颠倒过来 switch (s2.pop()){ case "+": s1.push(s1.pop()+s1.pop()); break; case "-": a=s1.pop();s1.push(s1.pop()-a); break; case "*": s1.push(s1.pop()*s1.pop()); break; case "/": a=s1.pop();s1.push(s1.pop()/a); break; } } else{ throw new ValidationException("算术表达式格式错误!"); } } System.out.println("结果为："+s1.pop()); System.out.println("请输入表达式："); i=0; } } }队列
- 先进先出
- 相当于在栈的基础上加上一个队头指针，指向最早加入的成员，别新成员一来老成员就不见了
如果是数组的话很少用循环数组，而是超出容量重新创建一个新数组并把旧元素移过去
/** * @Author haien * @Description 基于链表的队列 * @Date 2018/10/26 **/ public class Queue<T> implements Iterable<T>{ //队头，用于出队 private Node first; //队尾，用于入队 private Node last; //长度 private int n; //结点 private class Node{ private T item; private Node next; } public boolean isEmpty(){ return first==null; } public int size(){ return n; } public void enQueue(T item){ Node oldlast=last; last=new Node(); //必须要new，防止栈为空时下一行出现NPE last.item=item; //为什么私有属性也能访问？？？ last.next=null; if(isEmpty()) first=last; else oldlast.next=last; n++; //放最后，方便前面判空 } public T deQueue(){ if(isEmpty()) throw new NoSuchElementException(); n--; T item=first.item; first=first.next; //防止游离，否则last还指着已经出队的那个元素 if(isEmpty()) last=null; return item; } public T peek(){ if(isEmpty()) throw new NoSuchElementException(); return first.item; } @Override public String toString() { StringBuilder s=new StringBuilder(); for(T item:this){ //调用的是this的迭代器 s.append(item); s.append(' '); } return s.toString(); } @Override public Iterator<T> iterator() { return new ListIterator(); } private class ListIterator implements Iterator{ //不能定义为MyIterator<T>，此T与外部类的T会被视为另一类 private Node currrent; public ListIterator() { this.currrent = first; } @Override public boolean hasNext() { return currrent!=null; } @Override public T next() { if(!hasNext()) throw new NoSuchElementException(); T item=currrent.item; currrent=currrent.next; return item; } @Override public void remove() { throw new UnsupportedOperationException(); } } public static void main(String[] args) { Queue<String> queue=new Queue<>(); //输入字符串，回车,进栈，输入-，回车,出栈 while (!StdIn.isEmpty()){ //底层是scanner.hasNext()，请求输入并获取输入流判断是否为空 //底层是scanner.next()，从输入流中读取字符串，遇到空格结束一次读取，直到读到输入流末尾再重新请求输入 String item=StdIn.readString(); if(!item.equals("-")) queue.enQueue(item); else if(!queue.isEmpty()) StdOut.print(queue.deQueue()+" "); } StdOut.println("("+queue.size()+" left on queue)"); } }背包
- 其实就是不能出栈的栈，只能往里add元素
代码实例
- DataStructure/dataStructure
