每日一题为了工作 2020 0303 第一题

Java 栈的相关操作

题目：
* 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
* 要求：
* 1.pop、push、getMin操作的时间复杂度都是O(1)。
* 2.设计栈类型可以使用现成的栈结构。

* 首先明确Java栈的相关操作函数

Stack stack = new Stack();//实例化栈对象

* 进栈操作

stack.push(“Object”);//返回的是入栈的内容

stack.add("Object");//返回的是true或false

* 出栈操作

stack.pop();//输出并删除栈顶元素

stack.peek();//输出不删除栈顶元素

*判断栈是否为空

stack.isEmpty();

*查看某元素在栈中的位置计数从1开始

int index = stack.search("a");

*题目分析

分析：
* 在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈
* 没有区别，这个栈记为stackData; 另一个栈用于保存每一步的最小值，这个栈记
* 为tackMin。具体的实现方式有两种。
* 第一种设计方案如下。
* • 压入数据规则
* 假设当前数据为newNum, 先将其压入stackData。然后判断stackMin是否为空
* 如果为空，则newNum也压入stackMin中
* 如果不为空，则比较newNum和stackNum的栈顶元素哪一个更小
* 如果newNum更小或两者相等，则newNum也压入到stackMin中
* 如果stackMin中的栈顶元素小，则stackMin中不压入任何内容。

* 压入数据代码

public class MyStackOne {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    //构造方法
    public MyStackOne() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }
    //
    public void push(int newNum) {
        if(this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        }else if(newNum <= this.getMin()){
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }
    public int pop() {
        if(this.stackData.isEmpty()) {
            throw new RuntimeException("your stack is empty!");
        }
        int value = this.stackData.pop();
        if(value == this.getMin()) {
            this.stackMin.pop();
        }
        return value;
    }
    public int getMin() {
        if(this.stackMin.isEmpty()) {
            throw new RuntimeException("your stack is empty!");
        }
        return this.stackMin.peek();
    }
    
    
}

第二种设计方案如下。
* • 弹出数据规则
* 在stackData中弹出数据，弹出数据的值记为value，弹出stackMin中的栈顶，返回
* value。
* 查询当前栈中最小值操作
* stackMin始终记载着stackData中的最小值，所以stackMin中的栈顶元素始终是当
* 前stackData的最小值。

* 第二种设计代码

import java.util.Stack;


public class MyStackTwo {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    
    public MyStackTwo() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }
    public int getMin() {
        if(this.stackMin.isEmpty()) {
            throw new RuntimeException("your stack is empty！");
        }
        return this.stackMin.peek();
    }
    public void push(int newNum) {
        if(this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        }else if(newNum < this.getMin()) {
            this.stackMin.push(newNum);
        }else {
            int newMin = this.stackMin.peek();
            this.stackData.push(newMin);
        }
        this.stackData.push(newNum);
    }
    public int pop() {
        if(this.stackMin.isEmpty()) {
            throw new RuntimeException("your stack is empty!");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }

* @author 雪瞳

每日一题 为了工作 2020 0303 第一题

每日一题为了工作 2020 0303 第一题