java模拟实现栈的一系列操作

时间：2022-09-17 23:34:58

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素（先进后出原则）。

而我们需要实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。

1.设原有的栈叫做栈A，此时创建一个额外的栈B，用于存储栈A元素的下标。

2.当第一个元素进入栈A的时候，让新元素的下标进入栈B。这个元素默认是栈A的当前最小值。

3.每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素的下标进入栈B，此时栈B的栈顶元素就是栈A当前最小值的下标。

4.每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第二小的元素，代替刚才的出栈元素成为了栈A的当前最小值。

5.当调用getMin方法的时候，直接返回栈B的栈顶所指向的栈A对应元素即可。

附上代码求解 
 

public class stackTest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> stackBackUp = new Stack<Integer>();
        pushStack(stack,stackBackUp,10);
        pushStack(stack,stackBackUp,7);
        pushStack(stack,stackBackUp,6);
        pushStack(stack,stackBackUp,4);
        pushStack(stack,stackBackUp,8);
        pushStack(stack,stackBackUp,3);
        pushStack(stack,stackBackUp,1);
        pushStack(stack,stackBackUp,2);
        System.out.println("当前stack:"+stack);
        System.out.println("stack下标对应的栈:"+stackBackUp);
        popStack(stack,stackBackUp);
        System.out.println("第1次移除操作后stack:"+stack);
        System.out.println("第1次移除操作后stack下标对应的栈:"+stackBackUp);
        popStack(stack,stackBackUp);
        System.out.println("第2次移除操作后stack:"+stack);
        System.out.println("第2次移除操作后stack下标对应的栈:"+stackBackUp);
        popStack(stack,stackBackUp);
        System.out.println("第3次移除操作后stack:"+stack);
        System.out.println("第3次移除操作后stack下标对应的栈:"+stackBackUp);
        System.out.println("stack中最小值:"+getMin(stack,stackBackUp));
    }
    /**  * /**  * 先进栈：  * 1:创建2个栈，一个栈放元素（stack），另外一个栈放元素下标(stakcBackUp)  * 2:向stack中放入元素时，先与stakcBackUp顶部元素（代表stack下标）所对应的stack元素比较  *  *  * @param stack 放元素的栈  * @param stackBackUp 放元素下标的栈  * @param i 放入的元素  */  public static void pushStack(Stack<Integer> stack,Stack<Integer> stackBackUp,int i){
        if(stack.isEmpty()){//第一次放进去的值默认最小  stack.push(i);
            stackBackUp.push(0);
        }else if(stack.get(stackBackUp.peek())<i){
            stack.push(i);
        }else{
            stack.push(i);
            stackBackUp.push(stack.size()-1);
        }
    }
    /**  * 出栈操作  * 先明确：栈的原则（是一种先进后出的集合）  * 当从stack中出栈时，先与stackBackUp栈顶元素对应的值进行比较，若相同则说明此时  * stack出战的为最小值，同时将stackBackUp栈顶元素移除  * 反之仅移除stack，stackBackUp不动  */  public static void popStack(Stack<Integer> stack,Stack<Integer> stackBackUp){
        if(stack.peek()==stack.get(stackBackUp.peek())){
            //System.out.println(11);  stackBackUp.pop();
            stack.pop();
        }else{
            stack.pop();
        }
    }
    /**  * 3:总结stackBackUp最上面的下标对应的stack中的元素最小  * @param stack  * @param stackBackUp  * @return  */  public static int getMin(Stack<Integer> stack,Stack<Integer> stackBackUp){
        return stack.get(stackBackUp.peek());
    }




标签：
相关文章