当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-2.设计包含min函数的栈

发表于: 2012-01-07   作者:bylijinnan   来源:转载   浏览:
摘要: 具体思路参见:http://zhedahht.blog.163.com/blog/static/25411174200712895228171/ import java.util.ArrayList; import java.util.List; public class MinStack { //maybe we can use origin array rathe
具体思路参见:http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
import java.util.ArrayList;
import java.util.List;


public class MinStack {

	//maybe we can use origin array rather than ArrayList
	private List<Integer> dataStack;
	private List<Integer> auxStack;//store the position of MinElement
	
	public static void main(String[] args) {
		MinStack minStack=new MinStack();
		minStack.push(3);
		minStack.printStatus();
		minStack.push(4);
		minStack.printStatus();
		minStack.push(2);
		minStack.printStatus();
		minStack.push(1);
		minStack.printStatus();
		minStack.pop();
		minStack.printStatus();
		minStack.pop();
		minStack.printStatus();
		minStack.push(0);
		minStack.printStatus();
	}

	public MinStack(){
		dataStack=new ArrayList<Integer>();
		auxStack=new ArrayList<Integer>();
	}
	public void push(int item){
		if(isEmpty()){
			dataStack.add(item);
			auxStack.add(0);//position=0
		}else{
			dataStack.add(item);
			int minIndex=auxStack.get(auxStack.size()-1);
			int min=dataStack.get(minIndex);
			if(min>item){
				auxStack.add(dataStack.size()-1);
			}else{
				auxStack.add(minIndex);
			}
		}
	}
	public int pop(){
		int top=-1;
		if(isEmpty()){
			System.out.println("no element,no pop");
		}else{
			auxStack.remove(auxStack.size()-1);
			top=dataStack.remove(dataStack.size()-1);
		}
		return top;
		
	}
	public int min(){
		int min=-1;
		if(!isEmpty()){
			int minIndex=auxStack.get(auxStack.size()-1);
			min=dataStack.get(minIndex);
		}
		return min;
	}
	public boolean isEmpty(){
		return dataStack.size()==0;
	}
	public void printStatus(){
		System.out.println("数据栈             辅助栈                最小值");
		for(int i=0;i<dataStack.size();i++){
			System.out.print(dataStack.get(i)+",");
		}
		System.out.print("          ");
		for(int i=0;i<dataStack.size();i++){
			System.out.print(auxStack.get(i)+",");
		}
		System.out.print("           ");
		System.out.print(this.min());
		System.out.println();
	}
	/*
步骤              数据栈            辅助栈                最小值
1.push 3    3          0             3
2.push 4    3,4        0,0           3
3.push 2    3,4,2      0,0,2         2
4.push 1    3,4,2,1    0,0,2,3       1
5.pop       3,4,2      0,0,2         2
6.pop       3,4        0,0           3
7.push 0    3,4,0      0,0,2         0
	 */
}

java-2.设计包含min函数的栈

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目: 设计一个栈,使得PUSH、POP以及GetMin(获取栈中最小元素)能够在常数时间内完成。 分析:
题目描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 输入: 输入可
题目 设计包含min 函数的栈。 定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。 要
题目1:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中,调用
1 /* 2 * 题目: 3 * 设计包含min的栈 4 * 定义栈的数据结构,要求添加一个min函数,能够得到栈的最
一、题目:包含Min函数的栈 题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的m
题目描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 输入: 输入可
题目链接地址: 九度OJ-题目1522:包含min函数的栈 题目描述: 定义栈的数据结构,请在该类型中实现
此题目来自于Crack the Coding Interview 3-2 3 2 How would you design a stack which, in additio
自己用c语言编写的一个程序,是按照数据结构书上给出的结构。如果不对的地方请指教。同时会给出c++
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号