3.3 题目:

基础:

设想有一堆盘子,堆太高可能会倒下来。因此在现实生活中,盘子堆到一定高度后,我们会另外堆一堆盘子。

请实现数据结构SetOfStacks,模拟这种行为。SetOfStacks由多个栈组成,并且在前一个栈填满时新建一个栈。

此外,SetOfStacks的push和pop方法应和普通栈逻辑相同,即push加入到最新栈,pop从最新的栈弹出。

进阶:

实现一个popAt(int index) 方法,根据指定的子栈,进行pop操作。

解法:

基础:

* package StackAndQueue;  
*   
* import java.util.ArrayList;  
* import java.util.Stack;  
*   
* public class SetOfStacks<E> {  
*     //用于记录所维护的所有Stack  
*     private ArrayList<Stack<E>> list = new ArrayList<>();  
*     //记录最新的Stack,待存入和取值的Stack  
*     private Stack<E> currentStack;  
*     //每个栈的最大容量  
*     private static final int MAX_CAP = 100;   
*       
*     public SetOfStacks(){  
*         Stack<E> stack = new Stack<>();  
*         list.add(stack);  
*         currentStack = stack;  
*     }  
*       
*     public void push(E value){  
*         if(currentStack.size() >= MAX_CAP){  
*             Stack<E> newStack = new Stack<>();  
*             newStack.push(value);  
*             list.add(newStack);  
*             currentStack = newStack;  
*         }  
*         else{  
*             currentStack.push(value);  
*         }  
*     }  
*       
*     public E pop(){  
*         E value = currentStack.pop();;  
*         if(currentStack.size() == 0 && list.size() > 1){  
*             list.remove(currentStack);  
*             currentStack = list.get(list.size()-1);  
*         }  
*         return value;  
*     }  
*       
*     public E peek(){  
*         if(isEmpty()){  
*             return null;  
*         }  
*         return currentStack.peek();  
*     }  
*   
*     public boolean isEmpty() {  
*         return list.size() ==1 && currentStack.size() == 0;  
*     }  
* }  

测试用例:

* @Test  
*     public void test_3_3() {  
*         SetOfStacks<Integer> setOfStacks = new SetOfStacks<>();  
*         for(int i = 0 ;i<201;i++){  
*             setOfStacks.push(i);  
*         }  
*         System.out.println(setOfStacks.peek());  
*           
*         System.out.println(setOfStacks.pop());  
*     }  
使用debug加入断点调试,查看setOfStacks的组成情况即可。

进阶问题解法:

有两种情况

一是待删除的元素就在最新的栈中,那么直接删除即可

二是待删除的元素在前面已经装满的栈中,假如有 0 1 2
三个栈,删除0中的栈顶元素,要保持装入的顺序不变,就需要把1中的栈底元素弹出压入0的栈顶,再把2的栈底元素弹出压入1的栈顶,如果栈的数目更多,依次类推即可,这样操作的目的是保证前面的栈都是满的。

另外,还要注意,进行完情况二的移位之后,若最新栈(currentStack)没有元素了,要从list中删除。

* public E popAt(int index){  
*         if(index > list.size()-1){  
*             return null;  
*         }  
*         Stack<E> stack = list.get(index);  
*         E value = stack.pop();  
*         //如果选中的子栈是当前最新子栈  
*         if(stack == currentStack){  
*             //如果子栈前面还有满子栈,且该子栈弹出后没有元素,从list中删除  
*             if(currentStack.size() == 0 && list.size() > 1){  
*                 list.remove(currentStack);  
*             }  
*         //不是当前最新子栈,是前面的满子栈  
*         }else{  
*             //从待删除子栈开始循环,使用下一个stack的copyInto方法把栈中元素复制到数组中,再取栈底元素压入  
*             //待删除子栈,然后删除下一个stack中的栈底元素(使用listIterator的remove方法)  
*             for(int i=index;i < list.size()-1;i++){  
*                 Stack<E> s = list.get(i);  
*                 Stack<E> next = list.get(i+1);  
*                 Object[] array = new Object[next.size()];  
*                 next.copyInto(array);  
*                 s.push((E) array[0]);  
*                 Iterator<E> itr = next.listIterator(0);  
*                 if(itr.hasNext()){  
*                     itr.next();  
*                     itr.remove();  
*                 }  
*             }  
*             //这里判断移位后最新子栈是否没有数据  
*             if(currentStack.size() == 0){  
*                 list.remove(currentStack);  
*             }  
*         }  
*         return value;  
*     }  

测试用例:

* @Test  
*     public void test_3_3_Advance(){  
*         SetOfStacks<Integer> setOfStacks = new SetOfStacks<>();  
*         for(int i = 0 ;i<201;i++){  
*             setOfStacks.push(i);  
*         }  
*         setOfStacks.popAt(0);  
*     }  

可以把201改成250 进行第二次测试。

技术
©2019-2020 Toolsou All rights reserved,
Vue 中获取下拉框的文本及选项值python 中的短路逻辑java几种常见运行时异常及简单例子(精华)2020年8月2日 TypeScript 泛型的使用LED 滚动文字Vue开发小技巧fio使用详解明明是post请求为什么会在地址栏显示参数?ELementUI select多选下拉框获取选中项的全部属性(精华)2020年7月15日 微信小程序 template的使用