数据查询网站,网站建设与管理专业就业,国外可以做推广的网站,wordpress 视频 去广告插件下载题目#xff1a;
堆盘子。设想有一堆盘子#xff0c;堆太高可能会倒下来。因此#xff0c;在现实生活中#xff0c;盘子堆到一定高度时#xff0c;我们就会另外堆一堆盘子。请实现数据结构SetOfStacks#xff0c;模拟这种行为。SetOfStacks应该由多个栈组成#xff0c;…题目
堆盘子。设想有一堆盘子堆太高可能会倒下来。因此在现实生活中盘子堆到一定高度时我们就会另外堆一堆盘子。请实现数据结构SetOfStacks模拟这种行为。SetOfStacks应该由多个栈组成并且在前一个栈填满时新建一个栈。此外SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同也就是说pop()返回的值应该跟只有一个栈时的情况一样。 进阶实现一个popAt(int index)方法根据指定的子栈执行pop操作。
当某个栈为空时应当删除该栈。当栈中没有元素或不存在该栈时poppopAt 应返回 -1. 输入 [StackOfPlates, push, push, popAt, pop, pop] [[1], [1], [2], [1], [], []] 输出 [null, null, null, 2, 1, -1] 题目解释
1.执行StackOfPlates1意思是定义每堆盘子只能存放1个盘子无返回值所以输出null
2.执行puhs (1)意思是堆盘子1号无返回值所以输出null
3.执行puhs (2)意思是堆盘子2号此时因为前一堆盘子已经满了需要新建一堆盘子继续堆无返回值所以输出null
4.执行popAt (1)意思是从下标为1的盘子堆中拿走最上面的一个盘子这里盘子堆的下标是从0开始的所以也就是从第二堆盘子拿所以返回的是2
5.执行pop意思是从最后一堆盘子中拿走最上面的一个盘子这里因为前一个已经将第二堆盘子清空了所以应该从第一堆盘子中拿所以返回的是1
6.执行pop意思是从最后一堆盘子中拿走最上面的一个盘子这里因为已经没有盘子堆了所以无法拿盘子返回-1
解题思路
1.将一个个盘子堆想象成一个个栈创建一个数组数据类型为栈这样就可以给每堆盘子进行编号
2.当前盘子已经堆满后就要堆一个新的所以要创建一个栈
3.在拿走盘子时如果拿走之后当前这堆盘子为空了要将当前这个盘子堆的栈清除掉
源代码如下
class StackOfPlates {
public:vectorstackint ss;//定义一个数组每个元素存放的是一个栈int sum;//没堆盘子的最大高度StackOfPlates(int cap) {sumcap;}//堆盘子void push(int val) {//如果每堆盘子的最大高度为0那么就不能堆盘子if(sum0){return;}//当前还没有堆盘子时或者是当前的这堆盘子已经到达最大高度了//就要创建一个新的栈if(ss.empty()||ss.back().size()sum){ss.push_back(stackint());}//将盘子堆到栈中ss.back().push(val);}//把盘子从最后一个栈里拿出来int pop() {//如果当前数组中没有栈或者当前栈为空则无法从栈中将盘子取出if(ss.empty()||ss.back().empty()){//直接返回-1return -1;}//记录当前的栈顶元素int resss.back().top();//栈顶元素出栈ss.back().pop();//如果当前栈为空了if(ss.back().empty()){//把当前栈从数组中清除//因为这个栈就是数组的最后一个元素所以可以直接pop_back()ss.pop_back();}//返回这个值return res;}//把盘子从下标为index的这个栈中取出int popAt(int index) {//如果当前数组中没有栈//如果当前下标超过栈的总数//如果下标为index的这个栈为空//以上三种情况都无法出栈返回-1if(ss.empty()||indexss.size()||ss[index].empty()){return -1;}//记录index栈的栈顶元素int resss[index].top();//出栈ss[index].pop();//如果当前栈为空了if(ss[index].empty()){//将当前这个栈清除ss.erase(ss.begin()index);}return res;}
};
