首页 > 试题广场 >

集合栈

[编程题]集合栈
  • 热度指数：15539 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

请实现一种数据结构SetOfStacks，由多个大小为size的栈组成，当前一个栈填满时，则新建一个栈，且也可以与普通栈一样拥有相同的push和pop操作。

现给定一个操作序列int[][2] ope(C++为vector&ltvector&ltint>>)，若执行push操作则第一个数为1，第二个数为应push的数字；若执行pop操作，则第一个数为2，第二个数为空。返回值为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)
Java
wanbf头像 wanbf 
import java.util.*;
public class SetOfStacks {
    public ArrayList> setOfStacks(int [][] ope, int size) {
        // write code here
        ArrayList> res = new ArrayList>();
        if(ope==null || ope.length==0 || size <= 0) return res;
        for(int i=0;i<ope.length;i++){
            if(ope [i][0]==1) push(ope [i][1],res,size);
            if(ope [i][0]==2) pop(res);
        }
        return res;
    }
    static void push(int val,ArrayList> res,int size){
        if(res.isEmpty() || res.get(res.size()-1).size()==size){
            ArrayList list = new ArrayList();
            list.add(val);
            res.add(list);
        }else{
            res.get(res.size()-1).add(val);
        }

    }
    static void pop(ArrayList> res){
        if(res.size()==0) return;
        ArrayList list = res.get(res.size()-1);
        if(list.size()==1) res.remove(list);
        else{
            list.remove(list.size()-1);
        }
    }
}
发表于 2022-01-14 21:26:21 回复(0)
Java
🍂夜森🍃头像 🍂夜森🍃 
import java.util.*;
 
public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> stack = new ArrayList<>();
        for(int i = 0;i < ope.length;i++){
            if(ope[i][0] == 1){
                if(stack.size() == size){  //当前列表已满
                    ret.add(stack);
                    stack = new ArrayList<>();  //新建空列表
                }
                stack.add(ope[i][1]);
            }else if(ope[i][0] == 2){
                if(stack.isEmpty()){  //当前列表为空，不能删除
                    stack = ret.get(ret.size() - 1);  //取出栈集合中的最后一个列表
                    ret.remove(ret.size() - 1);
                }
                stack.remove(stack.size() - 1);
           }
       }
       //最后一个 list 可能不满，但也要记得判断将其插入 ret
       if(stack.size() > 0){
           ret.add(stack);
       }
       return ret;
    }
}

编辑于 2020-04-09 11:21:25 回复(0)
Java
zidianlyu头像 zidianlyu 
import java.util.*;

public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        Stack<Integer> tmp = new Stack<Integer>();
        for(int i = 0; i < ope.length; i++){
            if(ope[i][0] == 1){

                如果满Stack
                if(tmp.size() == size){

                    Stack与ArrayList的转换
                    res.add(new ArrayList(tmp));
                    tmp.clear();
                }
                tmp.push(ope[i][1]);
            } else {

                如果有连续超量的pop操作,需要从res里面挖出来
                if(tmp.size() == 0){

                    Stack与ArrayList的转换
                    tmp = new Stack();
                    tmp.addAll(res.remove(res.size() - 1));
                }
                tmp.pop();
            }
        }

        if (tmp.size() > 0)
            res.add(new ArrayList(tmp));
        return res;
    }
}
发表于 2018-07-01 07:52:22 回复(0)
Java
百乐门前一回首头像 百乐门前一回首 
import java.util.*;

public class SetOfStacks {
public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here
        ArrayList<ArrayList<Integer>> Sset=new ArrayList<ArrayList<Integer>>();
        
        ArrayList<Integer> elem=new ArrayList<Integer>();
        ArrayList<Integer> last=new ArrayList<Integer>();
        for(int i=0;i<ope.length;i++){
            if(Sset.size()!=0 && elem.size()==0){//如果当前栈为空，从栈组中取出最后一个栈最为操作对象
               last=new ArrayList<Integer>();
               last.addAll(Sset.get(Sset.size()-1));
               elem=last;  
               Sset.remove(Sset.size()-1); 
            }
            if(ope[i][0]==1){
                if(elem.size()==size){
                    Sset.add(elem);
                    elem=new ArrayList<Integer>();
                }
                elem.add(ope[i][1]);
             }
            if(ope[i][0]==2  && elem.size()!=0){
                elem.remove(elem.size()-1);
            }
        }
        if(elem.size()!=0){
            Sset.add(elem);
        }
        return Sset;
    }
}
编辑于 2017-06-07 16:43:44 回复(0)
Java
阿狸不是猫头像 阿狸不是猫 
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)
Java
一神头像 一神
不要考虑的太复杂，只需要保留一个当前的stack即可。操作如下：
1. push操作：stack为满，则push到stack中。stack已满，将stack加入集合，重新new一个stack，将数据push进去。
2. pop操作：stack不为空，则直接pop。stack为空，从set中取栈顶的stack，然后pop.

最后，当stack不为空，将stack加入到set集合中. 

public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        // write code here
        ArrayList<ArrayList<Integer>> set = new ArrayList<ArrayList<Integer>>();
        if (ope == null || ope.length == 0) {
            return set;
        }
                
        ArrayList<Integer> curStack = new ArrayList<Integer>(size);
        
        for (int i = 0, len = ope.length; i < len; i ++) {
            if (ope[i][0] == 1) {
                // push
				if (curStack.size() < size) {
                    curStack.add(ope[i][1]);
                } else {
                    set.add(curStack);
                    curStack = new ArrayList<Integer>(size);
                    curStack.add(ope[i][1]);
                }						                
            } else {
                // pop
                if (curStack.size() != 0) {
                    curStack.remove(curStack.size() - 1);
                } else {
                    if (set.size() > 0) {
                    	curStack = set.get(set.size() - 1);
                        curStack.remove(curStack.size() - 1);
                    	set.remove(set.size() - 1);
                    }
                }
            }
        }
        
        if (curStack.size() > 0) {
            set.add(curStack);
        }
        
        return set;
    }
}

发表于 2017-01-25 11:14:05 回复(0)
Java
重大小牛一枚头像 重大小牛一枚
import java.util.*;

public class SetOfStacks {
    public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
        int len=ope.length;
ArrayList<ArrayList<Integer>> arrayLists=new ArrayList<>();
ArrayList<Integer> array=new ArrayList<>(size);
arrayLists.add(array);
for(int i=0;i<len;i++){
int a=ope[i][0];
int b=ope[i][1];
int peeksize=arrayLists.get(arrayLists.size()-1).size();
if(a==1){//
if(peeksize==size){
ArrayList<Integer>array1=new ArrayList<>();
arrayLists.add(array1);
                    arrayLists.get(arrayLists.size()-1).add(b);
}else if(peeksize<size) {
arrayLists.get(arrayLists.size()-1).add(b);
}
}else if(a==2){
if(peeksize==0){
arrayLists.remove(arrayLists.get(arrayLists.size()-1));
                     peeksize=arrayLists.get(arrayLists.size()-1).size();
                    arrayLists.get(arrayLists.size()-1).remove(peeksize-1);
}else if(peeksize>0){
arrayLists.get(arrayLists.size()-1).remove(peeksize-1);
}
}
}
return arrayLists;
    } 
}

编辑于 2016-08-15 14:35:23 回复(0)
提交观点

问题信息

栈
难度：
8条回答 16654浏览

热门推荐

通过挑战的用户

查看代码

相关试题

集合栈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号