设计一个getMin功能的栈

Neo
Neo
2020-09-20 / 0 评论 / 158 阅读

题目描述

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

输入描述:

第一行输入一个整数N,表示对栈进行的操作总数。
下面N行每行输入一个字符串S,表示操作的种类。
如果S为"push",则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop",则表示弹出栈顶操作。
如果S为"getMin",则表示询问当前栈中的最小元素是多少。

输出描述:

对于每个getMin操作,输出一行表示当前栈中的最小元素是多少。

示例1

输入
6
push 3
push 2
push 1
getMin
pop
getMin
输出
1
2

import java.io.*;
import java.util.*;
import java.math.*;
  
/**
下面代码大部分都用来处理控制台输入问题,核心功能其实挺简单:
在普通栈之外再单独设置一个栈,专门用来存储最小值

入栈操作:基本栈入栈的时候比较一下入栈元素和最小栈栈顶元素的大小,如果小,就压入,如果大,就把最小栈栈顶元素重复压入。

出栈操作:普通栈出栈,同时最小栈也出栈

getMin操作:直接获取最小栈栈顶元素即可
*/
public class Main {
  
    public static void main(String[] args) {
        InputReader reader = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        reader.nextLine();
        int size = reader.nextInt();
        MyStack stack = new MyStack();
  
        for (int i = 0; i < size; i++) {
            reader.nextLine();
            String operate = reader.next();
  
  
            if("push".equals(operate)){
                Integer num = reader.nextInt();
                stack.push(num);
            }
            if("pop".equals(operate)){
                stack.pop();
            }
            if("getMin".equals(operate)){
                out.println(stack.getMin());
            }
  
  
        }
  
  
        out.close();
    }
}
  
class MyStack{
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
  
    public MyStack(){
        stack = new Stack<>();
        minStack = new Stack<>();
    }
  
    public void push(Integer integer){
        stack.push(integer);
        if(minStack.isEmpty()){
            minStack.push(integer);
        }else {
            if(integer <= minStack.peek()){
                minStack.push(integer);
            }else {
                minStack.push(minStack.peek());
            }
        }
        
    }
  
    public Integer pop(){
        if(minStack.size() == 0){
            throw new RuntimeException("your stack is empty");
        }
        minStack.pop();
        return stack.pop();
    }
  
    public Integer getMin(){
        if(minStack.size() == 0){
            throw new RuntimeException("your stack is empty");
        }
        return minStack.peek();
    }
}
  
  
  
  
  
/**
 * 常用输入模板
 */
class Template{
    private static InputReader inputReader = new InputReader();
  
    /**
     * 读入一行字符串
     * @return
     */
    public static String readString(){
        inputReader.nextLine();
        return inputReader.next();
    }
  
    /**
     * 读取一个以为数组
     * 第一行为数组长度
     * 第二行为数组
     * @return
     */
    public static int[] array1(){
        inputReader.nextLine();
        int length = inputReader.nextInt();
        int[] array = new int[length];
        inputReader.nextLine();
        for (int i = 0; i < length; i++) {
            array[i]= inputReader.nextInt();
        }
        return array;
    }
  
}
  
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
  
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
  
    boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            return false;
        }
        return true;
    }
    void nextLine(){
        try {
            tok = new StringTokenizer(buf.readLine());
        } catch (Exception e) {
            tok = null;
        }
    }
  
    String next() {
        if (hasNext()) return tok.nextToken();
        return null;
    }
  
    int nextInt() {
        return Integer.parseInt(next());
    }
  
    long nextLong() {
        return Long.parseLong(next());
    }
  
    double nextDouble() {
        return Double.parseDouble(next());
    }
  
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
  
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}