首页 > 代码库 > 算法(Algorithms)第4版 练习 1.3.8
算法(Algorithms)第4版 练习 1.3.8
方法实现:
//1.3.8 package com.qiusongde; import java.util.Iterator; import java.util.NoSuchElementException; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; public class ResizingArrayStack<Item> implements Iterable<Item> { private Item[] content; private int number; public ResizingArrayStack() { content = (Item[]) new Object[1]; number = 0; } private void resizeArray(int max) { if(max < number) throw new IllegalArgumentException("the size of new array must larger than the size of Stack"); Item[] temp = (Item[]) new Object[max]; for(int i = 0; i < number; i++) { temp[i] = content[i]; } content = temp; } public boolean isEmpty() { return number == 0; } public int size() { return number; } public void push(Item item) { if(number == content.length) resizeArray(2 * content.length); content[number++] = item; } public Item pop() { if(isEmpty()) throw new NoSuchElementException("Stack is empty"); Item item = content[--number]; content[number] = null;//Aoid loitering if(number == content.length/4 && number > 0) resizeArray(content.length/2); return item; } @Override public Iterator<Item> iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements Iterator<Item> { private int i = number; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { if(!hasNext()) throw new NoSuchElementException("Stack is empty"); return content[--i]; } @Override public void remove() { throw new UnsupportedOperationException(); } } //Just for test(main) private int arrayLength() { return content.length; } public static void main(String[] args) { ResizingArrayStack<String> stack = new ResizingArrayStack<String>(); StdOut.println("Initialized size:" + stack.size() + " Array Size:" + stack.arrayLength()); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) { stack.push(item); StdOut.println("push success:" + item + " size:" + stack.size() + " Array Size:" + stack.arrayLength()); StdOut.print("Left on stack: "); for (String s : stack) { StdOut.print(s + " "); } StdOut.println(); } else { if(stack.isEmpty()) StdOut.println("pop error, stack empty"); else { StdOut.println("pop success:" + stack.pop() + " size:" + stack.size() + " Array Size:" + stack.arrayLength()); StdOut.print("Left on stack: "); for (String s : stack) { StdOut.print(s + " "); } StdOut.println(); } } } } }
测试结果:
Initialized size:0 Array Size:1
it
push success:it size:1 Array Size:1
Left on stack: it
was
push success:was size:2 Array Size:2
Left on stack: was it
-
pop success:was size:1 Array Size:2
Left on stack: it
the
push success:the size:2 Array Size:2
Left on stack: the it
best
push success:best size:3 Array Size:4
Left on stack: best the it
-
pop success:best size:2 Array Size:4
Left on stack: the it
of
push success:of size:3 Array Size:4
Left on stack: of the it
times
push success:times size:4 Array Size:4
Left on stack: times of the it
-
pop success:times size:3 Array Size:4
Left on stack: of the it
-
pop success:of size:2 Array Size:4
Left on stack: the it
-
pop success:the size:1 Array Size:2
Left on stack: it
it
push success:it size:2 Array Size:2
Left on stack: it it
was
push success:was size:3 Array Size:4
Left on stack: was it it
-
pop success:was size:2 Array Size:4
Left on stack: it it
the
push success:the size:3 Array Size:4
Left on stack: the it it
-
pop success:the size:2 Array Size:4
Left on stack: it it
-
pop success:it size:1 Array Size:2
Left on stack: it
算法(Algorithms)第4版 练习 1.3.8
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。