算法(第四版)学习笔记之java实现能够动态调整数组大小的栈

下压(LIFO)栈：能够动态调整数组大小的实现

import java.util.Iterator;public class ResizingArrayStack<Item> implements Iterable<Item>{private int N = 0;private Item[] a = (Item[]) new Object[1];public boolean isEmpty(){return N == 0;}public int size(){return N;}public void resize(int max){Item[] temp = (Item[]) new Object[max];for(int i = 0 ; i < N ; i++){temp[i] = a[i];}a = temp;}public Item pop(){Item item = a[–N];a[N] = null;if(N > 0 && N == a.length / 4){resize(a.length / 2);}return item;}public void push(Item item){if(N == a.length){resize(a.length * 2);}a[N++] = item;}@Overridepublic Iterator<Item> iterator() {// TODO Auto-generated method stubreturn new reverseArrayIterator();}private class reverseArrayIterator implements Iterator<Item>{private int i = N;@Overridepublic boolean hasNext() {// TODO Auto-generated method stubreturn i > 0;}@Overridepublic Item next() {// TODO Auto-generated method stubreturn a[–i];}@Overridepublic void remove() {// TODO Auto-generated method stub}}}

优点：几乎(但还没用)达到了任意集合类数据类型的实现的最佳性能：1.每项操作的用时都与集合大小无关；2.空间需求总是不超过集合大小乘以一个常数。

缺点：某些push()和pop()操作会调整数组的大小，，这项操作的耗时和栈的大小成正比。

如若今生再相见，哪怕流离百世，迷途千年，也愿。

相关文章：

你感兴趣的文章：

标签云：