欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实现一个特殊的栈,在栈的基本功能上,再实现返回栈中最小元素的操作 Java代码实现

程序员文章站 2022-06-08 17:57:09
...

实现一个特殊的栈,在栈的基本功能上,再实现返回栈中最小元素的操作 Java代码实现  这种类型的题目,往往是面试笔试题中的入门题目,往往考察面试者的Coding能力;
  如题;要实现这种功能,那么这个 “特殊的栈” 就需要用两个普通的栈来实现,一个栈(取名为dataStack)用来存放push进来的元素,一个栈(取名为minStack)用来存放最小的元素。
开始操作:
  一开始,两个栈都为空,然后 dataStack来了第一个元素,因为minStack也为空,所以直接将该元素压入minStack中;
  此时 dataStack来了第二个元素,那么这个元素是否压入minStack中就要进行判断,如果该元素 <= minStack栈顶的元素那么就将其压入栈中,否则,就将minStack中栈顶的元素再压入一次(这样做的目的是为了minStack中的元素个数与dataStack中的元素个数相等);
  如果此时dataStack需要pop出栈顶元素,那么minStack也必须pop出栈顶元素(这样做的目的是为了minStack中的元素个数与dataStack中的元素个数相等);
  如果需要返回最小的元素(getMin),那么就弹出minStack中最小的元素即可,这样不用遍历,满足了时间复杂度O(1)。
  下面上代码:(代码很完整,复制到编译器就可以跑起来了,觉得还可以的老铁点个赞再走哦!)

public class GetMinStack
{
    //设置两个大小相同的栈
    private static Stack<Integer> dataStack;
    private static Stack<Integer> minStack;

    public GetMinStack()
    {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public static void push(int obj)
    {
        if (dataStack.isEmpty())
        {
            dataStack.push(obj);
            minStack.push(obj);
        }
        else if (!(dataStack.isEmpty()))
        {
            dataStack.push(obj);
            if (minStack.peek()<=obj)
            {
                minStack.push(minStack.peek());
            }
            else {
                minStack.push(obj);
            }
        }
    }

    public static Integer pop()
    {
        if (dataStack.isEmpty()) throw new IllegalArgumentException("The Stack is null");

        minStack.pop();
        return dataStack.pop();
    }

    public static Integer getMin()
    {
        if (minStack.isEmpty()) throw new IllegalArgumentException("The Stack is null");

        return minStack.peek();
    }

    public static void main(String[] args) {
        GetMinStack getMinStack = new GetMinStack();
        push(1);
        push(2);
        push(2);
        push(3);
        push(4);
        push(3);
        push(-1);
        System.out.println(pop());
        System.out.println(getMin());
    }
}