数据结构:栈及其应用

本文阅读 5 分钟
首页 代码,Java 正文

img

Stack接口

因为栈可以用顺序存储实现也可以用链式存储实现,所以把共性抽取定义出Stack接口 img

ArrayStack类(栈的顺序存储具体实现)

因为栈本身是一种特殊的线性表,所以我们可以用上一篇博客中完成的ArrayList来实现我们的ArrayStack

public class ArrayStack<E> implements Stack<E> { 
    //栈的内部用线性表来实现
    private ArrayList<E> list;

    /** * 创建默认容量的线性表 */
    public ArrayStack(){ 
        list=new ArrayList<E>();
    }

    /** * 创建指定容量的线性表 * @param capacity */
    public ArrayStack(int capacity){ 
        list=new ArrayList<>(capacity);
    }

    /** * 获取线性表中元素个数 * @return */
    @Override
    public int size() { 
        return list.size();
    }

    /** * 判断栈是否为空 * @return */
    @Override
    public boolean isEmpty() { 
        return list.isEmpty();
    }

    /** * 压栈,在表尾添加 * @param element */
    @Override
    public void push(E element) { 
        list.add(element);
    }

    /** * 弹栈一个元素并且返回(在线性表的末尾删除一个元素并且返回) * @return */
    @Override
    public E pop() { 
        return list.remove(list.size()-1);
    }

    /** * 查看当前栈顶元素(不删除) * @return */
    @Override
    public E peek() { 
        return list.get(list.size()-1);
    }

    /** * 清空栈 */
    @Override
    public void clear() { 
        list.clear();
    }

    @Override
    public Iterator<E> iterator() { 
        return list.iterator();
    }

    @Override
    public String toString() { 
        StringBuilder builder = new StringBuilder(String.format("ArrayStack:%d/%d[", size(),list.getCapacity()));
        if (isEmpty()) { 
            builder.append("]");//ArrayList:0/10;

        } else { 
            for (int i = 0; i < size(); i++) { 
                builder.append(list.get(i));
                if (i != size() - 1) { 
                    builder.append(",");
                } else { 
                    builder.append("]");
                }
            }
        }
        return builder.toString();
    }
}

img

十进制转为十六进制

img

public class DecToHex { 
    public static void main(String[] args) { 
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入一个十进制数:");
        int num=scanner.nextInt();
        /** * 因为会涉及到数字和字母,比如A,B这样的,所以泛型应该是Charcater * 创建一个栈来存储余数 */
        ArrayStack<Character> stack=new ArrayStack<>();
        int mod;
        while (num!=0){ 
            //余数入栈
            //余数可能是0~9也可能是A~F
             mod=num%16;
             if (mod<10){ 
                 //数字0到9
                 stack.push((char)(mod+'0'));
             }else { 
                 //否则是数字10到15,要转换成A到F
                 stack.push((char)('A'+mod-10));
             }
             num/=16;

        }
        //按照顺序弹栈
        while (!stack.isEmpty()){ 
            Character pop = stack.pop();
            System.out.print(pop);
        }
    }
}

img

十六进制转为十进制

img

public class HexToDec { 
    public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入一个十六进制的字符串:");
        String num = scanner.nextLine();
        //创建一个栈,存储每一个字符
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < num.length(); i++) { 
            stack.push(num.charAt(i));
        }
// System.out.println(stack);
        //依次弹栈并累加计算结果
        int sum = 0;
        //幂数
        int exponent = 0;
        char c;
        while (!stack.isEmpty()) { 
            c = stack.pop();
            sum += Math.pow(16, exponent) * getNumber(c);
            exponent++;
        }
        System.out.println(sum);


    }

    /** * 把字符转换为对应的数字 * 字符是0~9或A~F * * @param c * @return */
    private static int getNumber(char c) { 
        if (!(c >= '0' && c <= '9' || c >= 'A' && c <= 'F')) { 
            throw new IllegalArgumentException("错误的输入十六进制数 " + c);
        }
        //说明字符是符合十六进制的数字要求的
        if (c >= '0' && c <= '9') { 
            return c - '0';
        } else { 
            return 'A' + c - 10;
        }

    }
}

img

public class JudgeHw { 
    public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入一个字符串:");
        String str = scanner.nextLine();
        //创建栈
        ArrayStack<Character> stack=new ArrayStack<>();
        char c;
        for (int i = 0; i < str.length(); i++) { 
            //判断字符串的长度是奇数还是偶数
             //如果是奇数的话,则把中间数据过滤掉,不需要压栈
            if (str.length()%2==1&& i==str.length()/2){ 
                continue;
            }
            c=str.charAt(i);
            //如果栈空,则入栈
            if (stack.isEmpty()){ 
                stack.push(c);
            }else{ 
                if (stack.peek()==c){ 
                    stack.pop();
                }else { 
                    //不相等则入栈
                    stack.push(c);
                }

            }
            //栈如果非空,则比较栈顶元素和待入栈元素是否相等,如果不相等,则入栈
            //如果相等,则出栈
        }
        //如果最后栈空,则是回文
        if (stack.isEmpty()){ 
            System.out.println("是回文");
        }else{ 
            System.out.println("不是回文");
        }





    }
}

img

img 20.有效的括号 思路分析

  • 遇到左括号就入栈
  • 如果遇到右括号
    - 看看栈顶是否有元素 ,如果栈为空,说明无法匹配 - 如果栈顶有元素,但是括号不匹配,则说明无法匹配
  • 所有字符扫描完毕后,如果栈空,说明有效,否则无效
class Solution { 
    public boolean isValid(String s) { 
  Stack<Character> stack=new Stack<>();
        int len=s.length();
        for (int i = 0; i < len; i++) { 
            char c=s.charAt(i);
            if(c=='('||c=='['||c=='{'){ 
                //入栈
                stack.push(c);
            }else{ 
                //否则就是右括号
                //如果栈是空的,则无法匹配
                if (stack.isEmpty()) return false;
                //如果栈非空,则出栈进行匹配
                Character pop = stack.pop();
                if (pop=='(' && c!=')') return  false;
                if (pop=='{'&& c!='}') return false;
                if (pop=='['&& c!=']') return false;
            }
        }
        //所有字符扫描完毕后,如果栈空,说明有效,否则无效
        return stack.isEmpty();

    
    }
}

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 img

<font size="4">这道题目可以遍历一下字符串,如果是字符是数字的话,则入栈,如果为运算符,则把栈顶的两个元素弹出,进行运算,注意它们的顺序,栈是后进先出的特点,如果是减法或除法,注意:是后面弹出的数减去或者除去前面弹出的一个数,然后把运算结果存入栈中</font>

class Solution { 
    public int evalRPN(String[] tokens) { 
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i <tokens.length;i++){ 
            String str = tokens[i];//获取下标为 i 字符串元素
            if(isOperator(str)){ // 如果 str 是运算符 为 true,否则为false
                int num2 = stack.pop();// 获取 栈顶 的 两个数字数据(出栈)
                int num1 = stack.pop();
                switch(str){ // 判断 str 具体是 哪一个字符串,就执行对应的运算,并将其结果入栈
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }else{ // 将 数字字符转换成 整形数据 存入 栈中
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();// 返回/出栈 最终存入栈中的结果
    }
    public boolean isOperator(String s){ // 判断 str 是运算符 返回 true;否则,返回 false
        if(s.equals("+") || s.equals("-")|| s.equals("*") || s.equals("/")){ 
            return true;
        }
        return false;
    }
}
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://zengyihong.blog.csdn.net/article/details/125701543
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复