首页 > 试题广场 >

集合栈

[编程题]集合栈

热度指数：15537 时间限制：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)

Python

Yannyezixin

思路：

思路很清晰简单，就是一个二维数组。每一行是一个栈，栈的高度（即二维数组的列数）为指定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)