寒光博客

[java] SetOfStacks 二维链表实现一种指定数据结构
SetOfStacks cc150 请实现一种数据结构SetOfStacks,由多个栈组成,其中每个栈的大小为si...
扫描右侧二维码阅读全文
25
2019/10

[java] SetOfStacks 二维链表实现一种指定数据结构

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 (寒光博客)”原创,转载请保留文章出处。
Last modification:October 26th, 2019 at 12:23 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment