寒光博客

[java]Stack 设计一个带最小值的栈 建立维护栈
思路 维护最小值栈 建立兄弟栈 在push新元素的时候 对新元素和旧元素比较大小 小 就入栈新元素 反之入栈 pe...
扫描右侧二维码阅读全文
24
2019/10

[java]Stack 设计一个带最小值的栈 建立维护栈

思路

维护最小值栈
建立兄弟栈
在push新元素的时候 对新元素和旧元素比较大小
小 就入栈新元素 反之入栈 peek(旧元素)
出栈时 兄弟栈也依次出栈即可

优化

空间换时间
没有更小的就不加入到兄弟栈
在push新元素的时候 对新元素和旧元素比较大小 然后入栈即可
pop时 在兄弟栈对比是否相同 再pop

代码

package _09_Linear.Stack_QueuePractice;

import _09_Linear.Stack.IStack;
import _09_Linear.Stack.MyStack;
import _09_Linear.list.DoubleLinkList;
import _09_Linear.list.ListNode;
import org.junit.Test;

import java.util.EmptyStackException;

public class StackWithMin<T> extends DoubleLinkList<T> implements IStack<T> {
    @Test
    public void test()throws Exception {
        StackWithMin stack = new StackWithMin<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(-5);
        stack.push(5);
        System.out.println(stack.min_O1());
//        System.out.println(stack.min_On());
        stack.pop();
        stack.pop();
        System.out.println(stack.min_O1());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.min_O1());

    }

    @Override
    public void push(T e) {
        add(e);

        //维护最小值栈 当然还可以节约空间 减少重复
        if (brother.empty()) {
            brother.push(e);
        } else {
            T peek = brother.peek();
            if ((Integer) e < (Integer) peek) {
                brother.push(e);
            } else {
                brother.push(peek);
            }
        }

    }

    @Override
    public T pop() {
        if (size <= 0) throw new EmptyStackException();
        ListNode<T> the = super.last.getPre();//last 的前一个
        T res = the.getData();

        the.getPre().setNext(last);//目标元素的前一个 指向最后
        last.setPre(the.getPre());//最后一个元素指向目标元素的前一个
        the.setPre(null);
        the.setNext(null);
        size--;

        brother.pop();//兄弟也弹出

        return res;

    }

    /**
     * O(n) 遍历
     *
     * @return
     */
    public int min_On() {
        ListNode<T> h = first.getNext();
        int min = -1;
        while (h != last) {
            if ((Integer) h.getData() <= min) {
                min = (Integer) h.getData();
            }
            h = h.getNext();//后移
        }
        return min;
    }



    /**
     * O(1) 空间换时间
     * 再Push时 维护最小值栈
     * @return
     * @throws Exception
     */
    //维护栈
    private MyStack<T> brother = new MyStack();

    public int min_O1() throws Exception {
        if (!brother.empty())
            return (Integer) brother.peek();
        else
            throw new Exception("没有元素了 所以无最小值");
    }

    //----------------------------------------
    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public T peek() {
        return last.getPre().getData();
    }
}
本文作者:Author:     文章标题:[java]Stack 设计一个带最小值的栈 建立维护栈
本文地址:https://dxoca.cn/java/305.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 24th, 2019 at 05:07 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment