栈:从简单栈到解决经典栈问题

2023-12-29 11:39:18

Java学习手册+面试指南:https://javaxiaobear.cn

栈是一种基于先进后出(FILO)的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

我们称数据进入到栈的动作为压栈,数据从栈中出去的动作为弹栈。

1、栈的API设计

类名Stack
构造方法Stack:创建Stack对象
成员方法1.public boolean isEmpty():判断栈是否为空,是返回true,否返回false
2.public int size():获取栈中元素的个数
3.public T pop():弹出栈顶元素
4.public void push(T t):向栈中压入元素t
成员变量private Node head:记录首结点
private int N:当前栈的元素个数
public class Stack<T> implements Iterable<T>{
    /**
     *   栈长度
     */
    private int size;

    /**
     * 头结点
     */
    private Node head;

    public Stack() {
        head = new Node(null,null);
        size = 0;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }

    /**
     * 数据入栈
     * @param t
     */
    public void push(T t){
        Node next = head.next;
        //新节点
        Node newNode = new Node(t, next);
        //重新赋值
        head.next = newNode;
        size++;
    }

    /**
     * 数据出栈
     * @return
     */
    public T pop(){
        Node next = head.next;
        if(null == next){
            return null;
        }
        head.next = head.next.next;
        size--;
        return next.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator<T>{
        private Node n = head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }
        @Override
        public T next() {
            Node node = n.next;
            n = n.next;
            return node.item;
        }
    }

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

2、括号匹配问题

给定一个字符串,里边可能包含"()"小括号和其他字符,请编写程序检查该字符串的中的小括号是否成对出现。
例如:
“(上海)(长安)”:正确匹配
“上海((长安))”:正确匹配
“上海(长安(北京)(深圳)南京)”:正确匹配
“上海(长安))”:错误匹配
“((上海)长安”:错误匹配

步骤:

  1. 创建一个栈用来存储左括号
  2. 从左往右遍历字符串,拿到每一个字符
  3. 判断该字符是不是左括号,如果是,放入栈中存储
  4. 判断该字符是不是右括号,如果不是,继续下一次循环
  5. 如果该字符是右括号,则从栈中弹出一个元素t;
  6. 判断元素t是否为null,如果不是,则证明有对应的左括号,如果不是,则证明没有对应的左括号
  7. 循环结束后,判断栈中还有没有剩余的左括号,如果有,则不匹配,如果没有,则匹配
/**
     * 左括号入栈,右括号出栈
     * @param str
     * @return
     */
public boolean isMatch(String str){
    //创建一个栈存储左括号
    Stack<String> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        
        if(s.equals("(")){
            stack.push(s);
        }else if(s.equals(")")){
            String pop = stack.pop();
            if (pop == null) {
                return false;
            }
        }
    }
    //栈中元素是否为空
    if(stack.size == 0){
        return true;
    }
    return false;
}

3、逆波兰表达式

中缀表达式就是我们平常生活中使用的表达式,例如:1+32,2-(1+3)等等*

中缀表达式的特点是:二元运算符总是置于两个操作数中间

逆波兰表达式(后缀表达式):

逆波兰表达式是波兰逻辑学家J?卢卡西维兹(J? Lukasewicz)于19 29年首先提出的一种表达式的表示方法,后缀表达式的特点:运算符总是放在跟它相关的操作数之后。

给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式,求出该逆波兰表达式的结果

/**
     * 求逆波兰表达式
     * @param number
     * @return
     */
public int caculate(String[] number){
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < number.length; i++) {
        String s = number[i];
        Integer pop;
        Integer pop1;
        Integer temp;
        if("+".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop + pop1;
            stack.push(temp);
        }else if("-".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 - pop;
            stack.push(temp);
        }else if("*".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 * pop;
            stack.push(temp);
        }else if("/".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 / pop;
            stack.push(temp);
        }else {
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}

在这里插入图片描述

文章来源:https://blog.csdn.net/Y_hanxiong/article/details/135285976
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。