算法-栈的实现

package test.stack;

import org.apache.poi.ss.formula.functions.T;
import test.linear.linkList;

import java.util.Iterator;


public class Stack implements Iterable {

    private Node head;

    private int N;



    private class  Node {
        T item;
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public Stack(){
        this.head = new Node(null,null);
        this.N=0;
    }


    public Boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return N;
    }

    public void push(T t){

        Node oldfirst = head.next;
        head.next = new Node(t,oldfirst);

        N++;
    }

    public T pop(){
        if(head.next==null){
            return null;
        }
        Node n = head.next;
        head.next =  head.next.next;
        N--;
        return n.item;
    }


    @Override
    public Iterator iterator() {
        return new Literator();
    }

    private class Literator implements Iterator {
        private Node n;
        public Literator(){
            this.n = head ;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }

        @Override
        public void remove() {

        }




    }

}

测试代码

package test.stack;

public class StackTest {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push("aa");
        stack.push("bb");
        stack.push("cc");
        for (String s : stack) {
            System.out.println(s);
        }
        System.out.println("----------------------");
        String result = stack.pop();
        System.out.println("弹出的元素是："+result);
        System.out.println("剩下的个数的:"+stack.size());
       result = stack.pop();
        System.out.println("弹出的元素是："+result);
        System.out.println("剩下的个数的:"+stack.size());
         result = stack.pop();
        System.out.println("弹出的元素是："+result);
        System.out.println("剩下的个数的:"+stack.size());
         result = stack.pop();
        System.out.println("弹出的元素是："+result);
        System.out.println("剩下的个数的:"+stack.size());
    }
}

cc
bb
aa
----------------------
弹出的元素是：cc
剩下的个数的:2
弹出的元素是：bb
剩下的个数的:1
弹出的元素是：aa
剩下的个数的:0
弹出的元素是：null
剩下的个数的:0

案例：

括号匹配问题

解决思路

：

代码实现

package test.stack;

public class BracketMatchTest {
    public static void main(String[] args) {
        String str = "((上海(长安))))";
        Boolean flag = isMatch(str);
        System.out.println("str中的括号是否匹配："+flag);
    }

    public static boolean isMatch(String str){
        Stack chars = new Stack<>();
        for (int i = 0; i  
 
 
 
遍历字符，如果当前字符不是操作符就压入栈中，如果是就从栈中取出俩个进行计算，然后压入栈中
 
 
package test.stack;

public class ReversePolishNotationTest {
    public static void main(String[] args) {
        String [] notation = {"3","17","15","-","*","18","6","/","+"};
        int result = caculate(notation);
        System.out.println("逆波兰表达式的结果为："+result);

    }

    public static int caculate(String [] notation){
        Stack stack = new Stack<>();
        for (int i = 0; i