java 栈 stack的应用场景

比眉伴天荒 2022-03-01 08:52 213阅读 0赞

栈的特性: 先进后出

1. 单链表，求倒数第K个数

public class MyNode {
        public Integer value;
        public MyNode next;
        public MyNode(Integer value) {
            this.value = value;
        }
        @Override
        public String toString() {
            return "MyNode{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

MyNode node=new MyNode(1);
            MyNode temp=node;
            for(int i=2;i<11;i++){
                MyNode nodeNext=new MyNode(i);
                temp.next=nodeNext;
                temp=nodeNext;
            }
           int val= getSingleListLastKNum(node,4);
            System.out.println(val);

public static int getSingleListLastKNum(MyNode node,int k){
            Stack<MyNode> stacks=new Stack<>();
            while(node!=null){
                stacks.push(node);
                node=node.next;
            }
            MyNode target=null;
            int size=stacks.size();
            while(stacks.size()>0){
                target=stacks.pop();
                int subSize=stacks.size();
                if(size-subSize==k){
                    break;
                }
            }
           return target.value;
        }

思路就是将链表放入stack中，然后从栈中取出第K个元素即是倒数的第K个数。

这题的最优解就是双指针，链接在此：[https://www.cnblogs.com/edisonchou/p/4769164.html][https_www.cnblogs.com_edisonchou_p_4769164.html]

2. 单链表，判断其是否为回文数

MyNode node=new MyNode(1);
            MyNode temp=node;
            int j=1;
            for(int i=2;i<10;i++){
                int val=i;
                if(i>5){
                    val=i-2*j;
                    j++;
                }
                MyNode nodeNext=new MyNode(val);
                temp.next=nodeNext;
                temp=nodeNext;
            }
            System.out.println(node);
         boolean flag=isPalindromeNum(node);
            System.out.println(flag);

public static boolean isPalindromeNum(MyNode node){
            boolean flag=true;
            MyNode originalNode=node;
            Stack<MyNode> stacks=new Stack<>();
            while(node!=null){
                stacks.push(node);
                node=node.next;
            }
            while(stacks.size()>0){
               Integer value=stacks.pop().value;
               Integer oriVal=originalNode.value;
               if(value!=oriVal){
                   flag=false;
                   break;
               }
               originalNode=originalNode.next;
            }
            return flag;
        }

思路就是将链表放入stack中，然后从栈中取出元素依次与链表中的节点值进行对比，若有一个数不相等则直接跳出，说明不是回文数，否则就是回文数。

这题的最优解是快慢指针，链接在此: [https://blog.csdn.net/whm114336793/article/details/79996943][https_blog.csdn.net_whm114336793_article_details_79996943]

总结：

根据栈的特性，先进后出，我们发现这2题的共同特点都是需要将链表倒序之后才方便求值或者判断。所以栈的使用场景是需要将对象或者任意数据倒序之后做一类逻辑处理，例如：倒序输出，xml的语法检查等等都是满足此场景的

[https_www.cnblogs.com_edisonchou_p_4769164.html]: https://www.cnblogs.com/edisonchou/p/4769164.html
[https_blog.csdn.net_whm114336793_article_details_79996943]: https://blog.csdn.net/whm114336793/article/details/79996943