程式員代碼面試指南刷題--第一章.設計getMin功能的棧

題目描述

實作一個特殊功能的棧，在實作棧的基本功能的基礎上，再實作傳回棧中最小元素的操作。

輸入描述:

第一行輸入一個整數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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        for(int i=0;i<len;i++){
            String[] ss = br.readLine().trim().split(" ");
            String str = ss[0];
            
            if(str.equals("push")){
                int num = Integer.parseInt(ss[1]);
                s1.push(num);
                if(s2.isEmpty()||s2.peek()>=num){
                    s2.push(num);
                }
            }else if(str.equals("pop")){
                if(s1.isEmpty()){
                    throw new RuntimeException("沒資料了");
                }else if(s2.peek().equals(s1.peek())) {
                	s2.pop();
                }
                s1.pop();
            }else{
            	if(!s2.isEmpty()) {
            		System.out.println(s2.peek());
            	}else {
            		throw new RuntimeException("沒資料了");
            	}
            }
        }
    }
}
           

ps:其中涉及Integer對象的比較值比較用a.equals(b)。但是假如值在-128-127時用==依然可以判斷。

解法二：資料棧插入資料，min棧也插入

ps： 封裝一下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        MyStack ms = new MyStack(); 
        for(int i=0;i<len;i++){
            String[] ss = br.readLine().trim().split(" ");
            String str = ss[0];
            
            if(str.equals("push")){
                int num = Integer.parseInt(ss[1]);
                ms.push(num);
            }else if(str.equals("pop")){
                ms.pop();
            }else{
                System.out.println(ms.getMin());
            }
        }
    }
}
class MyStack{
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyStack(){
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    public void push(int num){
        if(s2.isEmpty()){
            s2.push(num);
        }else if(num<s2.peek()){
            s2.push(num);
        }else{
            int tmpmin = s2.peek();
            s2.push(tmpmin);
        }
        s1.push(num);
    }
    public int pop() {
        if(s1.isEmpty()){
             throw new RuntimeException("沒資料了");
        }
        s2.pop();
        return s1.pop();
    }
    public int getMin(){
        if(s1.isEmpty()){
             throw new RuntimeException("沒資料了");
        }
        return s2.peek();   
    }
}