请实现一种数据结构SetOfStacks，由多个大小为size的栈组成，当前一个栈填满时，则新建一个栈，且也可以与普通栈一样拥有相同的push和pop操作。
现给定一个操作序列int[][2] ope(C++为vector<vector<int>>)，若执行push操作则第一个数为1，第二个数为应push的数字；若执行pop操作，则第一个数为2，第二个数为空。返回值为int[][](C++为vector<vector<int>>)，即为变动后的SetOfStacks，顺序从下到上，初始SetOfStacks为空，并保证数据合法。
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;
}
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;
}
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;
}
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
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;
}
};
# -*- 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
class SetOfStacks {
public:
vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
vector<vector<int> > res;
vector<int> tmp;
for(int i = 0; i < ope.size(); ++i)
{
if(ope[i][0] == 1)
{
if(tmp.size() == size)
{
res.push_back(tmp);
tmp.clear();
}
tmp.push_back(ope[i][1]);
}
else
{
if(tmp.empty())
{
if(res.empty())
continue;
else
{
tmp = res.back();
res.pop_back();
}
}
tmp.pop_back();
}
}
if(!tmp.empty())
res.push_back(tmp);
return res;
}
}; 
//常规思路
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;
}
};
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
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;
}
};
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;
}
};
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{}
}
};
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;
}
};
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;
}
};
//我好像把题目理解错了，所以写了好长。。
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);
}
}
}
题目分析：
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;
}
};
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;
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
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;
}
};