首页 > 试题广场 > 集合栈
[编程题]集合栈

请实现一种数据结构SetOfStacks,由多个栈组成,其中每个栈的大小为size,当前一个栈填满时,新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。

给定一个操作序列int[][2] ope(C++为vector&ltvector&ltint>>),每个操作的第一个数代表操作类型,若为1,则为push操作,后一个数为应push的数字;若为2,则为pop操作,后一个数无意义。请返回一个int[][](C++为vector&ltvector&ltint>>),为完成所有操作后的SetOfStacks,顺序应为从下到上,默认初始的SetOfStacks为空。保证数据合法。

推荐
思路:首先建立一个栈组A(定义为vector<vector<int>> A),存放长度达到size的栈。定义vector<int> vect
操作如下:
从i = 0 ~ ope.size() - 1遍历
1、对于压栈指令(即ope[i][0] = 1),首先判断A是否为空
    1)如果A为空,那么考虑将数据压入vect
            1.如果vect长度已经达到size,那么先将vect压入A,然后清空vect里的元素,再将数据ope[i][1]压入vect;
            2.如果vect长度小于size,直接将vect压入A(此时不可以判断vect的长度是否到达size,即使到达size,也要确定下一个指令不是pop,才可以将vect压入A,以免压入之后,再从A[A.size() - 1]中弹出数据)。
    2)如果A不为空,先判断A的顶栈是否是满的,即判断A[A.size() - 1]长度是不是达到size,如果没有达到size,则将数据压入A[A.size() -1];如果达到size,则对vect进行判断,如果vect长度小于size,直接压入vect,否则执行上一步的第一条。
2、对于出栈指令,首先判断vect是否为空
    1)如果vect为空,则从A的顶栈中弹出顶元素,即执行A[a.size() - 1].pop_back(),弹出之后如果A[a.size() - 1]为空,则从A中弹出A[a.size() - 1],即执行A.pop_back;
    2)如果vect不为空,则直接从vect中弹出元素,即执行vect.pop_back().
遍历结束之后,如果vect不为空,则将vect压入A,即A.push_back(vect)。
返回A。

代码如下所示:
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<int> vect;
        vector<vector<int>> A;
        int len = vect.size();
        for(int i = 0; i < ope.size(); i ++)
            {
            //压入操作时
            if(ope[i][0] == 1)
                {
                //判断A是否为空
                if(A.size() == 0)
                    {
                    //判断vect是否已满
                    if(vect.size() == size)
                        {
                        A.push_back(vect);
                        vect.clear();
                        vect.push_back(ope[i][1]);
                    }
                    else
                        vect.push_back(ope[i][1]);
                }
                else  //A不为空
                    {
                    //判断A的顶栈是否已满
                    if(A[A.size() - 1].size() < size)
                        A[A.size() - 1].push_back(ope[i][1]);
                    else
                        {
                        if(vect.size() == size)
                            {
                            A.push_back(vect);
                            vect.clear();
                            vect.push_back(ope[i][1]);
                        }
                        else
                            vect.push_back(ope[i][1]);
                    }
                }
            }
            else   //弹出操作
                {
                //判断vect是否为空
                if(vect.empty())   //为空
                    {
                    //弹出A顶栈的元素
                    A[A.size() - 1].pop_back();
                    //判断顶栈是否为空
                    if(A[A.size() - 1].empty())  //为空则弹出顶栈
                        A.pop_back();
                }
                else    //vect不为空
                    vect.pop_back();
            }
        }
        if(!vect.empty())
            A.push_back(vect);
        return A;
    }
};
编辑于 2015-08-18 20:02:18 回复(3)
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<vector<int> > st;
        vector<int> temp;
        for(int i=0;i<ope.size();i++){
            if(ope[i][0]==1){//入栈
            	if(temp.size()==size){//栈满,则新建一个栈,再入栈
            		st.push_back(temp);
            		temp.clear();
            		temp.push_back(ope[i][1]);
            	}
            	else
            		temp.push_back(ope[i][1]);
            }
            if(ope[i][0]==2){//出栈
            	if(temp.size()!=0)//当前栈不为空,直接出栈
            		temp.pop_back();
            	else if(st.size()!=0){//当前栈为空,则从上一个栈出
            		temp=st[st.size()-1];
            		temp.pop_back();
            		st.pop_back();
            	}
            }
        }
        if(temp.size()!=0){
        	st.push_back(temp);
        }
        return st;
    }
};

发表于 2015-11-14 21:47:51 回复(6)
public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here
    	ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
    	ArrayList<Integer> curArray=new ArrayList<Integer>(size);
    	list.add(curArray);
    	for(int i=0;i<ope.length;i++){
    		switch(ope[i][0]){
    		//1:push
    		case 1:
    			//当前数组未满
    			if(curArray.size()!=size){
    				curArray.add(ope[i][1]);
    			}
    			else{
    				curArray=new ArrayList<Integer>(size);
    				list.add(curArray);
    				curArray.add(ope[i][1]);
    			}
    			break;
    		//2:pop
    		case 2:
    			//当前数组不为空
    			if(curArray.size()!=0){
    				curArray.remove(curArray.size()-1);
    			}
    			else{
    				list.remove(list.size()-1);
    				curArray=list.get(list.size()-1);
    				curArray.remove(curArray.size()-1);
    			}
    			break;
    		}
    	}
    	return list;
    }

发表于 2016-03-12 16:06:33 回复(7)
/*
java实现;
定义一个栈的集合,stackList,
curStack,代表当前栈,
先判断二维数组有多少行,代表操作次数
循环进行操作
判断操作是pop还是push
思路很简单,求赞!!
*/
import java.util.*;

public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
            ArrayList<ArrayList<Integer>> stackList = new ArrayList<ArrayList<Integer>>();
        if(ope==null||ope.length<1)
            return stackList;
       //定义操作的次数
        int opeCount = ope.length;
          //定义第一个栈       
         ArrayList<Integer> curStack = new ArrayList<Integer>();
       //因为操作数大于1,所以先把第一个栈加入集合中
         stackList.add(curStack);   
        for(int i=0;i<opeCount;i++)        
            {                                                       
                if(ope[i][0]==1)          //push操作
                    {
                        if(curStack.size()==size)     //如果当前栈的size已满
                            {
                                //新建一个栈,curStack指向新的栈 
                                 curStack = new ArrayList<Integer>(); 
                                 //将该栈加入集合栈
                                stackList.add(curStack);                            
                            }
                        curStack.add(ope[i][1]);               //数据入当前栈
                         
                    }
                if(ope[i][0]==2)            //pop操作                                               
                    {
                         //如果当前栈的大小大于0
                         if(curStack.size()>0)                         
                             //则直接删除,当前栈的最后一个元素   
                             curStack.remove(curStack.size()-1);  
                        else 
              //否则当前栈的size等于0说明栈集合中最后一个栈被pop空了
                        {
                              //把集合中最后一个空栈先删除掉 
                            stackList.remove(stackList.size()-1);        
                         //curStack指向集合中最后一个栈作为当前栈   
                        curStack = stackList.get(stackList.size()-1); 
                          //当前栈执行pop操作,弹出最后一个元素
                          curStack.remove(curStack.size()-1);      
                        }                               
                    }
            }
       
    return stackList;
    }
}
编辑于 2015-09-23 13:23:25 回复(0)
Ron头像 Ron
 public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here
    	ArrayList<ArrayList<Integer>> stackSet = new ArrayList<ArrayList<Integer>>();
    	stackSet.add(new ArrayList<Integer>());
    	/*
    	 * 1.添加元素时,确认stackSet的当前活动栈是否满
    	 * 		> 满 , 开辟新栈
    	 * 		> 不满,放入元素
    	 * 2.弹出元素时,确认stackSet当前活动栈是否为空
    	 * 		>空,则看当前栈是否为第一个栈,若是,则无法弹出,打印empty;若否,则删除当前栈,活动栈仍为栈的当前大小
    	 * 		>不空,则弹出最后的元素
    	 * 		
    	 */
    	for(int i = 0; i < ope.length; i++){
    		int cmd = ope[i][0];
    		int data = ope[i][1];
    		ArrayList<Integer> currentStack = stackSet.get(stackSet.size()-1);
    		if(cmd == 1){
    			if(currentStack.size() == size){//当前满,开辟新栈再放
    				stackSet.add(new ArrayList<Integer>());
    				currentStack = stackSet.get(stackSet.size()-1);
    				currentStack.add(data);
    			}else{//当前没满,继续放
    				currentStack.add(data);
    			}
    		}else if(cmd == 2){
    			if(stackSet.size() <= 1 && currentStack.size() == 0){//空
    				return stackSet;
    			}else{
    				if(currentStack.size() == 0){//仅仅当前栈空,但集合有数据,换集合中下一个栈弹出
    					stackSet.remove(stackSet.size()-1);
    					currentStack = stackSet.get(stackSet.size()-1);
    					currentStack.remove(currentStack.size()-1);
    				}else{//当前栈有值,直接弹出
    					currentStack.remove(currentStack.size()-1);
    				}
    			}
    		}else{
    			System.out.println("wrong input");
    		}
    	}
    	return stackSet;
    }

编辑于 2016-04-18 15:15:08 回复(1)
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        //思路很清晰简单, 就是一个二维数组。每一行是一个栈,栈的高度(即二维数组的列数)为指定size。
		//push操作时,最后一行,也就是最后一个栈如果满了,那么就增加一个行并入栈
		//pop操作时,pop最后一行的栈顶,如果最后一行为空,则pop掉最后一行再pop倒数第二行的栈顶
        vector<vector<int> > ret;
        vector<int> temp;
        
        for(int i=0; i<ope.size(); i++){
            //入栈
            if(ope[i][0]==1){
                //如果当前stack已满或还没有建立stack
                if(ret.empty()||ret.back().size()==size){
                    temp.clear();	//这一步很关键,因为temp是全局变量,所以每次用之前都要clear()
                    temp.push_back(ope[i][1]);
                    ret.push_back(temp);
                }
                
                //否则,直接将元素压入stack
                else{
                    ret.back().push_back(ope[i][1]);
                }
                    
            }
            else if(ope[i][0]==2){
                
                //如果当前栈是空的,那么就将空栈丢掉,并在前一个栈弹出元素
                if(ret.back().empty()){
                    ret.pop_back();
                    ret.back().pop_back();
                }
                
                //否则直接弹栈
                else{
                    ret.back().pop_back();
                }
            }
        }
        
        return ret;
        
    }

发表于 2016-10-02 21:53:32 回复(1)
思路:
创建一个二维vector mat,用来存储和返回;再创建一个一维vector vec,作为临时存储,用来向mat里面添加或删除元素,vec满了时用clear清空即可重复使用;指示器top说明vec目前有多少元素,top=0时表示vec为空。
每次先根据ope[k][0]填充vec,当vec.size()==size时,mat.push_back(vec),并清空vec,top置0;删除时,先判断top是否为0,如果是,则表示当前vec为空,则令vec=mat.back(),并从mat中删除最后一行,即mat.back_pop(),并删除vec最后一个元素,且令top = size - 1,说明vec中现在有size-1个元素;如果不是,则表示当前vec不为空,可以直接vec.back_pop()。
最后,在循环外面判断vec是否为空,如果是,则不管,直接返回;如果不是,则把vec添加到mat后面,即可返回。

class SetOfStacks {
public:
	vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
		// write code here
		int num = ope.size();
		if (num == 0)
		{
			return ope;
		} // if

		vector<vector<int>> mat;
		vector<int> vec;
		int top = 0;
		for (int k = 0; k < num; ++k)
		{
			if (ope[k][0] == 1)
			{
				vec.push_back(ope[k][1]);
				top++;
				if (vec.size() == size)
				{
					mat.push_back(vec);
					vec.clear();
					top = 0;
				} // if
			} // if
			else
			{
				if (top == 0)
				{
					vec = mat.back();
					mat.pop_back();
					vec.pop_back();
					top = size - 1;
				} // if
				else
				{
					vec.pop_back();
					top--;
				}
			} // else
		} // for
		if (!vec.empty())
			mat.push_back(vec);

		return mat;
	}
};

发表于 2016-08-15 11:02:10 回复(0)
import java.util.*;
//参考所得:分进栈出栈两种情况考虑,栈满了就新建一个栈;
public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> curArray =new ArrayList<Integer>();
        list.add(curArray);
        for(int i =0;i<ope.length;i++){
            switch(ope[i][0]){
                    case 1:if(curArray.size()== size){
                        		curArray =new ArrayList<Integer>();
                        		list.add(curArray);
                        		curArray.add(ope[i][1]);
                    		}else{
                        		curArray.add(ope[i][1]);
                    			}
                    		break;
                	case 2:if(curArray.size()!= 0){
                        		curArray.remove(curArray.size()-1);
                    		}else{
                        		list.remove(list.size()-1);//移除空的数组
                        		curArray =list.get(list.size()-1);
                        		curArray.remove(curArray.size()-1);
                    		}
                    		break;
            }
        }
        return list;
        
        
    }
}
运行时间:94ms
占用内存:1232k

发表于 2017-05-17 13:36:54 回复(1)
//常规思路
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        vector<vector<int> >res;
        vector<int>one;
        if(ope.size()<=0||size<=0) return res;
        for(int i=0;i<ope.size();++i)
        {
            if(ope[i][0]==1)//如果为1,进容器
            {
                if(one.size()<size)//如果临时容器不满,则直接进
                one.push_back(ope[i][1]);
                else{//如果满了,直接进大容器,并清空,推入此时数据
                    res.push_back(one);
                    one.clear();
                    one.push_back(ope[i][1]);
                }
            }
            else{ //如果为出容器
                if(one.size()>0)//如果临时容器不为空
                    one.pop_back();
                if(one.size()==0&&res.size()>0)//如果临时容器为空
                {
                    vector<int>back=res.back();//出大容器中的一个容器
                    one.swap(back);
                    res.pop_back();
                }
            }
        }
        if(one.size()>0)//如果临时容器不为空,推入大容器
        res.push_back(one);
        return res;
    }
};

发表于 2019-05-03 15:09:56 回复(0)
由于涉及push和pop,如果直接修改结果栈,可能涉及建栈和删栈,比较麻烦。所以,利用一个临时栈暂存,然后把最后的结果写入结果栈,建栈的地方注意段错误。

class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        vector<int> tmp;
        for (auto v : ope) {
            if (v.at(0) == 1) {
                tmp.push_back(v.at(1));
            } else {
                tmp.pop_back();
            }
        }
        vector<vector<int>> res;
        int cnt = 0;
        for (int i : tmp) {
            if (res.empty() || (int)res.back().size() == size) {
                res.push_back(vector<int>());
                cnt = 0;
            }
            ++cnt;
            res.back().push_back(i);
        }
        return res;
    }
};

运行时间:5ms

占用内存:456k


发表于 2018-12-24 15:35:32 回复(0)
解题思路:
//主要解题思路,创建一个二维数组和一个一维数组,对于压栈操作,如果一维数组为空或者一维数组的大小小于size,
//则直接将该数字压入此一维数组,如果一维数组等于size即栈满了,那么将此一维数组的所有元素移到二维数组,
//并且把此一维数组清空,再进行压入下一个元素动作。对于出栈操作,如果一维数组不为空,则直接出栈,如果
//为空,则将二维数组最后一组元素压入一维数组中,并对一维数组和二维数组分别进行pop_back操作。
//最后,如果一维数组不为空,把剩余元素压入二维数组中。并返回二维数组(集合栈)即可
代码:
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        vector<vector<int> > v;
        vector<int> tmp;
        for(int i=0; i<ope.size(); ++i)
        {
            if(ope[i][0]==1)
            {
                if(tmp.empty()||tmp.size()<size)
                {
                    tmp.push_back(ope[i][1]);
                }
                else
                {
                    v.push_back(tmp);
                    tmp.clear();
                    tmp.push_back(ope[i][1]);
                }
            }
            else if(ope[i][0]==2)
            {
                if(!tmp.empty())
                {
                    tmp.pop_back();
                }
                else
                {
                    tmp=v.back();
                    v.pop_back();
                    tmp.pop_back();
                }
            }
        }
        if(!tmp.empty())
        {
           v.push_back(tmp);
        }
        return v;
    }
};

发表于 2018-06-15 12:45:49 回复(0)
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<vector<int>> res;   //存储完成操作后的数据
        vector<int> temp;         //建立临时数组
        for(int i=0;i<ope.size();i++){
            if(ope[i][0]==1){        //入栈
                if(temp.size()!=size){
                    temp.push_back(ope[i][1]);    //临时数组没满size时直接存到临时数组
                }else{
                    res.push_back(temp);         //临时数组满size了,先把临时数组存入结果数组,然后清空
                    temp.clear();
                    temp.push_back(ope[i][1]);
                }
            }
            else{    //出栈
                if(!temp.empty()) temp.pop_back();     //临时数组中还有数据则直接弹出
                else{//临时数组中没有数据
                    res[res.size()-1].pop_back();
                    temp=res[res.size()-1];//从结果数组中取出一组数继续充当临时数组
                    res.pop_back();
                }
            }
        }
        if(!temp.empty()){  //遍历完以后临时数组中还有数据,直接存入结果数组中
            res.push_back(temp);
        }
        return res;
    }
};
发表于 2017-08-18 21:51:15 回复(0)
class SetOfStacks {
public:
    static vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<vector<int> > setStacks;
        vector<int> stck(size);
        stck.clear();
        int cnt = 0; // 当前栈元素个数
        int nth = 0; // 当前栈在vector中的索引 
        setStacks.push_back(stck);
        
        for(auto op : ope) {
            // 入栈
            if(op[0] == 1) {
                //栈满
                if(cnt==size) {
                    setStacks.push_back(stck);
                    cnt = 1;
                    ++nth;
                }
                //不满
                else {
                    ++cnt;
                }
                setStacks[nth].push_back(op[1]);
            }
            // 出栈
            else {
                //栈非空
                if(cnt > 0) {
                    --cnt;
                }
                //栈空
                else {
                    setStacks.pop_back();
                    cnt = size-1;
                    --nth;
                }
                setStacks[nth].pop_back();
            }
        }
        return setStacks;
    }
};


编辑于 2017-05-12 20:40:53 回复(0)
import java.util.*;

    public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
   
        ArrayList<Integer> curr=new ArrayList<Integer>(size);
        ArrayList<ArrayList<Integer>>  list =new ArrayList<ArrayList<Integer>>();
  
        for(int i=0 ;i<ope.length ;i++)
            {  
            //push
            if(ope[i][0]==1){
               
                if(curr.size()==size){ 
                    list.add(curr);
                    curr=new ArrayList(size);     
                }
              curr.add(ope[i][1]);
                
            }else{
                
                if(curr.size()!=0){
                curr.remove(curr.size()-1);
                }else{
                    
                      curr=list.get(list.size()-1);
                      list.remove(list.size()-1);
                      curr.remove(curr.size()-1);   
                }   
            }      
        }
        // 将最后没加上的数 加上
         if(curr.size()!=0)
    list.add(curr);
        return list;    
    }
}
发表于 2017-03-26 22:36:54 回复(0)
思路:
思路很清晰简单, 就是一个二维数组。每一行是一个栈,栈的高度(即二维数组的列数)为指定size。
push操作时,最后一行,也就是最后一个栈如果满了,那么就增加一个行并入栈
pop操作时,pop最后一行的栈顶,如果最后一行为空,则pop掉最后一行再pop倒数第二行的栈顶

# -*- coding:utf-8 -*-
class SetOfStacks:
    def __init__(self):
        self.stack = []
        self.size = None
    def setOfStacks(self, ope, size):
        if not ope:
            return []
        self.size = size
        for opera in ope:
            if opera[0] == 1:
                self.push(opera[1])
            else:
                self.pop()
        
        return self.stack
            
    def push(self, value):
        if not self.stack:
            self.stack.append([])
        if len(self.stack[-1]) < self.size:
            self.stack[-1].append(value)
        else:
            self.stack.append([value])
            
    def pop(self):
        if self.stack and self.stack[-1]:
            top = self.stack[-1].pop()
            if not self.stack[-1]:
                self.stack.pop()
        	return top      

发表于 2016-08-02 15:37:20 回复(0)
我太无聊了,自己写一个二维vector实现的myStack,居然一次就过了。。。。。。

class SetOfStacks {
    
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        vector<vector<int> > rst;

        for(int i=0;i<ope.size();i++)
        {
            myStacks(rst,ope[i][0],ope[i][1],size);
        }
        return rst;
    }
    void myStacks(vector<vector<int> > &v, int op, int value, int s)
    {
        if(v.empty())
        {
            if(op==1)
            {
                vector<int> t;
                t.push_back(value);
                v.push_back(t);
                return;
            }else return;
        }

        if(op==1)//push
        {
            int len=v.size()-1;
            if(v[len].size()<s)
            {
                v[len].push_back(value);
            }else
            {
                vector<int> t(1,value);
                v.push_back(t);
            }
        }else if(op==2)//pop
        {
            int len=v.size()-1;
            if(v[len].size()>0)
            {
                v[len].erase(v[len].end()-1);
            }else
            {
                v.erase(v.end()-1);
                myStacks(v,2,value,s);
            }
        }else{}
    }
};

发表于 2016-07-27 15:56:29 回复(0)
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        //栈的集合
        vector<vector<int> > stacks;
        int opeSize = ope.size();
        //当前单独的一个栈
        vector<int> singleStack;
        int count = 0;
        //遍历整个序列
        for(int i = 0; i < opeSize; i++){
            //操作为Push时
            if(ope[i][0] == 1){
                //当前栈未满
                if(count < size){
                    singleStack.push_back(ope[i][1]);
                    count++;
                }
                //当前栈已满
                else{
                    stacks.push_back(singleStack);
                    singleStack.clear();
                    singleStack.push_back(ope[i][1]);
                    count = 1;
                }
            }
            //操作为pop时
            else{
                //当前栈中有数据
                if(count > 0){
                    singleStack.pop_back();
                    count--;
                }
                //当前栈为空
                else{
                    singleStack = stacks.back();
                    stacks.pop_back();
                    singleStack.pop_back();
                    count = size - 1;
                }
            }
        }
        if(singleStack.size() != 0) stacks.push_back(singleStack);
        return stacks;
    }
};

编辑于 2016-05-09 22:08:27 回复(0)
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<vector<int>>resultStack;
        if(0 == ope.size() || 0 == size)
            return resultStack;
        for(int i = 0; i<ope.size();++i){
            if(1 == ope[i][0]){
                if(0 == resultStack.size() || resultStack.back().size() == size){
                    vector<int>oneOfStack;
                    resultStack.push_back(oneOfStack);
                }
                resultStack.back().push_back(ope[i][1]);
            }
            else{
                if(resultStack.size()==0)
                    return resultStack;
                if(0 ==resultStack.back().size()){
                    resultStack.pop_back(); 
                }
                resultStack.back().pop_back();
            }        
        }
        return resultStack;
    }
};

发表于 2016-05-06 21:43:21 回复(1)
//我好像把题目理解错了,所以写了好长。。
public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
		MyStack<Integer> s = new MyStack<>(size);
		for (int i = 0; i < ope.length; i++) {
			if (ope[i][0] == 1) {
				s.push(ope[i][1]);
			} else
				s.pop();
		}
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		s.f(list);
		return list;
	}

	@SuppressWarnings("unchecked")
	static class MyStack<T> {
		class Stack {
			Object[] s;
			int cur = -1;

			public Stack(int size) {
				s = new Object[size];
			}

			void push(T e) {
				s[++cur] = e;
			}

			T pop() {
				return (T) s[cur--];
			}

			boolean isFull() {
				return cur == MyStack.this.size - 1;
			}

			boolean isEmpty() {
				return cur == -1;
			}
		}

		ArrayList<Stack> list = new ArrayList<>();
		int cur = -1;
		int size;

		public MyStack(int size) {
			this.size = size;
		}

		void push(T k) {
			if (cur == -1) {
				list.add(new Stack(size));
				cur++;
			}

			Stack c = list.get(cur);
			if (c.isFull() && ++cur >= list.size()) {
				list.add(new Stack(size));
			}
			list.get(cur).push(k);
		}

		T pop() {
			Stack c = list.get(cur);
			if (c.isEmpty()) {
				cur--;
			}
			return list.get(cur).pop();
		}
		
		void f(ArrayList<ArrayList<Integer>> alist) {
			for (int i = 0; i <= cur; i++) {
				Stack s = list.get(i);
				ArrayList<Integer> arr = new ArrayList<>();
				for (int j = 0; j <= s.cur; j++) {
					arr.add((Integer)s.s[j]);
				}
				alist.add(arr);
			}
		}
	}

发表于 2016-04-05 12:06:11 回复(0)

题目分析:

这道题目基本没什么技巧,就是堆栈入栈的过程,相当于用多个数组来实现一个堆栈,如果一个数组满了,则使用另一数组,如果当且数组空了,则把该数组删除,从它前一个数组中操作,实现的时候注意数组交换数组时应该如何判断。
《程序员面试金典》--代码详解:
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
		int sz=ope.size();
		if(sz==0)
			return ope;
		vector<vector<int> > vecvec;
		vector<int> vec;
		int top=0;
		for(int i=0;i<sz;i++)
		{
			if(ope[i][0]==1)
			{
				vec.push_back(ope[i][1]);
				if(++top==size)
				{
					vecvec.push_back(vec);
					vec.clear();
					top=0;
				}
			}
			else
			{
				if(top==0)
				{
					vec=vecvec.back();
					vecvec.pop_back();
					top=size;
				}
				vec.pop_back();
				top--;
			}
		}
		if(!vec.empty())
			vecvec.push_back(vec);
		return vecvec;
    }
};

发表于 2015-10-03 13:44:56 回复(0)
class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {

        int opeSize = ope.size();
        if (opeSize == 0)
            return ope;  
        
        vector<vector<int> > result;
        vector<int> stack;
        int i = 0;
        while (i < opeSize) {
            stack.clear();
            while (stack.size() < size) {
                if (ope[i][0] == 1)
                    stack.push_back(ope[i][1]);
                else {
                    if (stack.size() != 0) {
                        stack.pop_back();
                    }
                    else {
                        stack = result[result.size()-1];
                        stack.pop_back();
                        result.pop_back();
                    }
                }
                if (++i == opeSize)
                    break;
            }
            result.push_back(stack);
        }
        
        return result;
    }
};

发表于 2015-08-28 11:06:17 回复(0)