首页 > 技术文章 > 【13】集合栈

noaman 2017-06-16 15:12 原文

【题目】

请实现一种数据结构SetOfStacks,由多个栈组成,其中每个栈的大小为size,当前一个栈填满时,新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。
给定一个操作序列int[][2] ope(C++为vector&ltvector&ltint>>),每个操作的第一个数代表操作类型,
若为1,则为push操作,后一个数为应push的数字;若为2,则为pop操作,后一个数无意义。
请返回一个int[][](C++为vector&ltvector&ltint>>),为完成所有操作后的SetOfStacks,顺序应为从下到上,默认初始的SetOfStacks为空。保证数据合法。

代码:

import java.util.*;

public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here     
        ArrayList<ArrayList<Integer>> list = new  ArrayList<ArrayList<Integer>>();
           
        //获取操作次数
        int len = ope.length;
        if(ope == null || len <=0 )
            return list;
        //定义第一个栈集合,用来存放数据(若这个栈集合满了,就新建一个集合再去存储元素)。大小为size
         ArrayList<Integer> tempList = new ArrayList<Integer>(size);
        list.add(tempList);   
        
        /**
        *ope二维数组,可能的数为: (1,x1),(0,x2),(1,x3),(1,x4),(0,x5),(1,x6)....
        * len 为二维数组的长度,也是操作的次数
        *                        *
        */
        for(int i = 0; i < len; i++){
            
            //ope[i][0]即为每个二维数组中的第一个数:如(1,x1)即为ope[0][0]
            //                                        (0,x2)即为ope[1][0]
            //若为1,则为push操作
            if(ope[i][0] == 1){
                //当前栈满,就新建一个栈集合用来存储数据,并把当前满的数据存储到集合中
                if(tempList.size() >= size){
                    tempList = new ArrayList<Integer>(size); 
                    list.add(tempList);
                }
                //ope[i][1]即为每个二维数组中的第2个数,是要存储的数:如存储(1,x1)中的x1:即为ope[0][1]
                //                                    存储(0,x2)的x2即为ope[1][1]
                tempList.add(ope[i][1]);
                
            }
            //若为2,则为pop操作
           if(ope[i][0] == 2){
                if(tempList.size() > 0){
                    tempList.remove(tempList.size() - 1);
                }else{
                    list.remove(list.size() - 1);
                    tempList = list.get(list.size() - 1);
                    tempList.remove(tempList.size() - 1);
                }
          
            }
            
            
        }
        
    
       return list; 
        
        
        
        
    }
}

 

推荐阅读