데이터 구조 면접 문제 1.2.3 - min 함 수 를 포함 한 스 택 디자인 [데이터 구조]

package questions;

import java.util.ArrayList;

/**
 * @title     min    [    ]<br>
 * @question         ，      min  ，          。    min、push  pop        O(1)<br>
 * @analysis   ：    google      。
 * 
 *                   ，        push      ，           。            。
 *                    push         ，                   。
 * 
 *                            （        ）。  push          ，                ，
 *                  。
 * 
 *                     。     ，            ：         pop  ，             ？
 * 
 *                              （        ）    。         。  push        ，       （
 *                   
 *           。                   ，                ）push     ；  pop         
 *           ，  pop   
 * @author Sam
 *
 */
public class Ex1o2o3 {

	public static void main(String[] args) {
		MinStack stack = new MinStack();
		stack.push(3);
		stack.print();
		stack.push(4);
		stack.print();
		stack.push(2);
		stack.print();
		stack.push(1);
		stack.print();
		stack.pop();
		stack.print();
		stack.pop();
		stack.print();
		stack.push(0);
		stack.print();
	}
}

class MinStack {
	private ArrayList<Integer> dataStack;//    List  min    index    
	private ArrayList<Integer> minStack;// store the position of Min Element

	public MinStack() {
		dataStack = new ArrayList<Integer>();
		minStack = new ArrayList<Integer>();
	}

	public void push(int item) {
		if (isEmpty()) {
			dataStack.add(item);
			minStack.add(0);
		} else {
			dataStack.add(item);
			int minIndex = minStack.get(minStack.size() - 1);
			int min = dataStack.get(minIndex);
			if (min > item) {
				minStack.add(dataStack.size() - 1);
			} else {
				minStack.add(minIndex);
			}
		}
	}

	public int pop() {
		int top = -1;
		if (isEmpty()) {
			System.out.println("no element,no pop");
		} else {
			minStack.remove(minStack.size() - 1);
			top = dataStack.remove(dataStack.size() - 1);
		}
		return top;
	}

	public int min() {
		if (isEmpty()) {
			return -1;
		}
		int minIndex = minStack.get(minStack.size() - 1);
		return dataStack.get(minIndex);
	}

	public void print() {
		System.out.println("   \t   \t   ");
		for (int i = 0; i < dataStack.size(); i++) {
			System.out.println(String.format("%d\t%d\t%d", dataStack.get(i),
					minStack.get(i), min()));
		}
	}

	public boolean isEmpty() {
		return 0 == dataStack.size();
	}
}

   	   	   
3	0	3
   	   	   
3	0	3
4	0	3
   	   	   
3	0	2
4	0	2
2	2	2
   	   	   
3	0	1
4	0	1
2	2	1
1	3	1
   	   	   
3	0	2
4	0	2
2	2	2
   	   	   
3	0	3
4	0	3
   	   	   
3	0	0
4	0	0
0	2	0