java实现单调栈和单调队列

package com.test.autimatic;

import org.apache.poi.ss.formula.functions.T;

import java.util.*;


public class SingleQueueAndSingleStack {


    public static void main(String[] args) {
        //mystack--获取比当前值大的最近的元素
        int[] arr = {2,1,3,4,3};
        List list = new ArrayList<>();//最终数据
        MyStack myStack = new MyStack<>();
        for (int i = arr.length-1; i >= 0; i--) {
            Integer add = myStack.add(arr[i]);
            list.add(add==null?-1:add);
        }
        System.out.println(list);
        System.out.println("---------------------------");
        //myqueue---单调队列，获取一为3的长度段区间内的最大值
        int[] arrQue = {2,1,3,4,3};
        MyQueue queue = new MyQueue<>();
        List endMax = new ArrayList<>();
        for (int i = 0; i < arrQue.length; i++) {
            queue.add(arrQue[i]);
            if(i > 2) {
                queue.delete(arrQue[i-3]);
            }
            endMax.add(queue.max());
        }
        System.out.println(endMax);
    }


    
    public static class MyStack>{

        private Stack stack;//存储数据的队列

        private Key max;//存储最大元素

        
        public MyStack() {
            this.stack = new Stack<>();
        }

        
        public Key add(Key key){
            //如果stack不为空且栈顶元素比目标值小，删除栈顶元素-维持低增粘
            while (!stack.isEmpty() && stack.peek().compareTo(key) < 0){
                stack.pop();
            }
            //设置最大值
            if(stack.isEmpty()){
                max = key;
            }
            //获取倒数第二个数
            Key end = stack.isEmpty()? null:stack.peek();
            //添加元素
            stack.push(key);
            return end;
        }

        
        public Key del(){
            if(!stack.isEmpty()){
                return stack.pop();
            }else{
                max = null;
            }
            return null;
        }

        
        public Key max(){
            return this.max;
        }

    }

    
    public static class MyQueue>{

        //数据集合---
        private Deque queue;

        public MyQueue() {
            this.queue = new linkedList<>();
        }

        
        public void add(key key){
            //先进先出--从头进去数据
            while (!queue.isEmpty() && queue.peekFirst().compareTo(key) < 0 ){
                queue.pollFirst();//如果比队头大，则删去队头元素
            }
            //添加元素
            queue.addFirst(key);
        }

        
        public key max(){
            if(queue.isEmpty()){
                return null;
            }
            //返回最后一个元素就是最大值
            return queue.peekLast();
        }

        
        public key delete(key key){
            if(!queue.isEmpty() && queue.peekLast().compareTo(key) == 0){
                return queue.pollLast();//如果最后一个数据为当前要删除的数据则删除
            }else{
                return null;
            }
        }

    }

}