SetOfStacks
cc150
请实现一种数据结构SetOfStacks,由多个栈组成,其中每个栈的大小为size,当前一个栈填满时,新建一个栈。
该数据结构应支持与普通栈相同的push和pop操作。
给定一个操作序列int[][2] ope,每个操作的第一个数代表操作类型,
若为1,则为push操作,后一个数为应push的数字;
若为2,则为pop操作,后一个数无意义。
请返回一个int[],为完成所有操作后的SetOfStacks,顺序应为从下到上,默认初始的SetOfStacks为空。
保证数据合法。
思路
因为个栈的个数不确定(size不确定),所以使用二维链表 也可以用链表套栈
前者只需要注意加东西只加在最后面 弹东西也从后面弹。
代码
package _09_Linear.Stack_QueuePractice;
import org.junit.Test;
import java.util.ArrayList;
public class SetOfStacks {
public ArrayList<ArrayList<Integer>> setOfStack(int[][] ope, int size) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
ArrayList<Integer> currStack = new ArrayList<>(size);
list.add(currStack);
for (int[] opAndValue : ope) {
int op = opAndValue[0];
int value = opAndValue[1];
if (op == 1) {//1Push
if (currStack.size() == size) {//当前满了
currStack = new ArrayList<>(size);//创建一个新栈
list.add(currStack);
}
currStack.add(value);
} else {//2pop
if (currStack.size() == 0) {
list.remove(currStack);//站的列表中移除
currStack = list.get(list.size() - 1);//被操作的栈是列表中的上一个栈
}
currStack.remove(currStack.size() - 1);
}
}
return list;
}
@Test
public void test() {
int[][] ope = new int[3][2];
//push
ope[0][0] = 1;
ope[1][0] = 1;
ope[2][0] = 1;
//value
ope[0][1] = 1;
ope[1][1] = 2;
ope[2][1] = 3;
ArrayList<ArrayList<Integer>> ans = setOfStack(ope, 1);
for (ArrayList<Integer> a:ans) {
for (int i = 0; i < a.size(); i++) {
System.out.println(a.get(i));
}
System.out.println("+++");
}
}
}
ans
1
+++
2
+++
3
+++
本文作者:Author: 寒光博客
文章标题:[java] SetOfStacks 二维链表实现一种指定数据结构
本文地址:https://dxoca.cn/java/306.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/306.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。