10个国内建筑网站,长沙品牌网站制作服务报价,最简单的网站,网站下载链接打不开Lab 2: Stack Queue ADT Part 1
这里只说一下最小栈的思路#xff0c;我们可以在定义一个栈#xff0c;来同步存储当前情况下的占的最小值。最小栈第一时间的想法可能是设定一个变量#xff0c;每次push进来栈中的元素进行对比#xff0c;保持最小值#xff0c;…Lab 2: Stack Queue ADT Part 1
这里只说一下最小栈的思路我们可以在定义一个栈来同步存储当前情况下的占的最小值。最小栈第一时间的想法可能是设定一个变量每次push进来栈中的元素进行对比保持最小值但是这样做并没有考虑到如果POP时的各种情况。因此我们设置一个最小值的栈他和存储的栈同步Push和Pop只是它每次push 的是栈目前存储的元素中的最小的值这样就解决了 Pop 后的最小值问题了。
public class StackMinAnyType extends ComparableAnyType implements StackInterfaceAnyType {private static final int MAX_SIZE 1024;private AnyType[] xstack;private AnyType[] minstack;private int size;public StackMin() {this.xstack (AnyType[]) new Object[MAX_SIZE];this.minstack (AnyType[]) new Object[MAX_SIZE];this.size 0;}Overridepublic int size() {return this.size;}Overridepublic AnyType pop() throws EmptyStackException {if (isEmpty()) {throw new EmptyStackException();}return this.xstack[--this.size];}Overridepublic AnyType peek() throws EmptyStackException {if (isEmpty()) {throw new EmptyStackException();}return this.xstack[this.size - 1];}Overridepublic void push(AnyType item) {if (this.size MAX_SIZE) {this.xstack[this.size] item;if (size 0 || item.compareTo(this.minstack[size - 1]) 0) {this.minstack[this.size] item;} else {this.minstack[this.size] this.minstack[size - 1];}}}Overridepublic void clear() {this.size 0;}Overridepublic boolean isEmpty() {return size() 0;}public AnyType findMin() {return this.minstack[this.size - 1];}
}Part 2
这个题目的主要思想是寻找第一个比自己小的数距离从暴力的角度来想我每次遍历一个数字就从这个数向前遍历直到遇到比自己大的数为止这样的时间复杂度是n方考虑优化的话可以进一步想到如果前面的数比自己小那么它的结果的距离范围的数字都会比自己小则可以剪枝一部分遍历的时间我们可以进一步的优化设置一个栈如果当前元素小于栈顶元素则索引的距离即为所求如果当前元素比栈顶元素值大的时候则一直Pop出站直到栈顶元素更大的时候这时两者的索引距离就是范围。下面是两种情况下的代码一种是直接给了完整的数组可以查询的一种是等待输入流随时输入随时输出的。
/*** Simple computeSpan static function* working on arrays*/public static int[] computeSpan(int[] input) {int len input.length;int[] spans new int[len];StackInteger stack new Stack();for (int i 0; i len; i) {while (!stack.isEmpty() input[stack.peek()] input[i]) {stack.pop();}spans[i] (stack.isEmpty()) ? (i 1) : (i - stack.peek());stack.push(i);}return spans;}/*** Compute the span of the input values* using a stack.* Complexity: THETA(n) where is n is the* number of values to compute the span of*/public void computeSpan() {StackInteger priceStack new Stack();StackInteger indexStack new Stack();int day 0;while (input.hasNextInt()) {int price input.nextInt();int span 1;while (!priceStack.isEmpty() priceStack.peek() price) {priceStack.pop();indexStack.pop();}if (indexStack.isEmpty()) {span day 1;} else {span day - indexStack.peek();}priceStack.push(price);indexStack.push(day);output.printf(value: %d span: %d\n, price, span);day;}}Part 3
用链表写一个队列就不说了寻找pair浅谈一下暴力的话n方的复杂度依次遍历优化的话放在哈希表中减去On的查询的复杂度
public static void showPairs(int n, String fileName) throws FileNotFoundException, EmptyQueueException {ListQueueInteger queue new ListQueue();Scanner scanner new Scanner(new File(fileName));while (scanner.hasNextInt()) {queue.offer(scanner.nextInt());}scanner.close();MapInteger, Integer map new HashMap();int index 0;while (!queue.isEmpty()) {Integer num queue.poll();if (map.containsKey(num - n)) {System.out.println(( (num - n) , num ));}map.put(num, index);}}Part 4
用栈来写一个队列思路也很简单使用两个栈一个输入一个输出当输出栈为空时将输入栈的值全部压到输出栈中
package tiei.aads.adt;import java.util.Stack;/*** A class for queues implemented with stacks*/
public class StackQueueAnyType implements QueueInterfaceAnyType {private StackAnyType instack new Stack();private StackAnyType outstack new Stack();Overridepublic int size() {return this.instack.size() this.outstack.size();}Overridepublic boolean isEmpty() {return this.instack.isEmpty() this.outstack.isEmpty();
// return QueueInterface.super.isEmpty();}Overridepublic void offer(AnyType item) {this.instack.push(item);}Overridepublic AnyType poll() throws EmptyQueueException {if(this.outstack.isEmpty()){while (this.instack.isEmpty()){this.outstack.push(this.instack.pop());}}return outstack.pop();}Overridepublic AnyType peek() throws EmptyQueueException {if(this.outstack.isEmpty()){while (this.instack.isEmpty()){this.outstack.push(this.instack.pop());}}return outstack.peek();}
} Part 5
是一个经典的T形火车问题主要思路就是使用一个Map存储下一个目标火车所在的栈然后依次将不是目标的元素存储到另一个栈中因为你需要考虑最简洁的移动方式所以需要精准找到目标火车的位置如果不需要最简洁的要求完全可以在两个栈中依次寻找就跟我下面还没有优化完全的代码一样过段时间我一定改
package tiei.aads.adt;import java.util.*;/*** A class to arrange train configuration*/
public class TrainManagement {private String[] from; // the initial orderingprivate String[] to; // the final orderingprivate StackInterfaceString U; // to hold the cars on track U(nsorted)private StackInterfaceString T; // to hold the cars on track T(emporary)private StackInterfaceString S; // to hold the cars on track S(orted)private MapString, StackInterfaceString map new HashMap();/*** Build a TrainManagement object* Preconditions:* from and to have the same size N and are* both permutations of each other*/public TrainManagement(String[] from, String[] to) {this.from from;this.to to;U new ArrayStack();T new ArrayStack();S new ArrayStack();for (int i from.length - 1; i 0; i--) {U.push(from[i]);map.put(from[i], U);}}/*** Output the basic move commands to transfer* the cars from the from order on track U* to the to order on track S*/public void arrange() throws EmptyStackException {int toIndex 0;while (toIndex to.length) {String targetCar to[toIndex];boolean found false;while (!U.isEmpty()) {String car U.pop();System.out.println(move car car from U to T);T.push(car);if (car.equals(targetCar)) {found true;System.out.println(move car car from T to S);T.pop();toIndex;break;}}while (!T.isEmpty() !found) {String car T.pop();System.out.println(move car car from T to U);U.push(car);}}}/*** A short main for quick testing*/public static void main(String[] args) throws EmptyStackException {String[] from {33, 11, 44, 22};String[] to {11, 22, 33, 44};TrainManagement tm new TrainManagement(from, to);tm.arrange();}// expected output//// move car 33 from U to T// move car 11 from U to T// move car 11 from T to S// move car 44 from U to T// move car 22 from U to T// move car 22 from T to S// move car 44 from T to U// move car 33 from T to S// move car 44 from U to T// move car 44 from T to S
}
