问题
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack s = new Stack();
s.push(1);
s.push(2);
s.add(0, 666);
System.out.println(s.get(0));
}
}
看看上面这段代码, 运行起来是没有报错的, 运行结果就是 666
这就很离谱, Stack居然支持随机插入???
这其实是原因也很简单, Vector是动态数组, Java中的Stack继承自Vector, 也就把Vector中所有公有方法都继承过来了, 包括Vector中的 add()
public class Stack<E> extends Vector<E>
public class Vector<E> extends AbstractList<E>
害 甲骨文你可长点心吧, 别整天打官司
这个问题告诉我们, 继承不能乱用, 能不用就不用, 因为继承打破了类的封装性, 父类的代码修改时, 可能值类也得修改, 子类依赖于父类
那不用继承用啥?
答案是组合!
继承和组合有啥区别?
继承是is-a的关系, 组合是has-a的关系
比如Tiger is a Animal, Animal就是Tiger的父类, 那Stack is a 动态数组? 我们可以考虑一下下面这个原则
如果设计成继承关系的话，我们是否有可能把子类进行向上的父类转型 如果可能，则应该设计成继承关系，否则应该是组合关系
上面的意思就是说能否把栈当成动态数组来使用, 答案是不可以, 栈不能像动态数组一样随机插入, 老虎可以像动物一样吃喝拉撒睡, 所以Stack不应该用继承, 应该用组合, 像这样
public class Stack<E>{
private Vector<E> v = new Vector<E> ();
// ...
}
有的人可能会问甲骨文会不知道这个吗? 为什么不改? 因为要向下兼容, 这里就不展开了
解决一: 封装Stack
后来Java官方推荐说使用Deque, 但是Deque本质是一个双向队列, 问题还是没有解决
下面是别人把Deque做一层封装实现Stack的代码
Stack.java
public interface Stack<T> {
void push(T object);
T pop();
}
DequeStack.java
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeStack<T> implements Stack<T> {
private final Deque<T> deque = new ArrayDeque<T>();
@Override
public void push(T object) {
deque.addFirst(object);
}
@Override
public T pop() {
return deque.removeFirst();
}
}
解决二: 自己实现
可以自己顺便实现一个动态数组, 也可以封装ArrayList, 这里我选择自己实现
Array.java
public class Array<E> {
private E[] data;
private int size; // 指向第一个没有元素的位置, 同时表示数组大小
/**
* 构造函数
* @param capacity 数组的容量
*/
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
/**
* 无参构造函数, 默认数组容量capacity=10
*/
public Array(){
this(10);
}
public Array(E[] arr){
data = (E[])new Object[arr.length];
for(int i=0; i<arr.length; i++){
data[i] = arr[i];
}
size = arr.length-1;
}
/**
* 获取数组的元素个数
* @return 数组的元素个数
*/
public int getSize(){
return size;
}
/**
* @return 数组的容量
*/
public int getCapacity(){
return data.length;
}
public boolean isEmpty(){
return size == 0;
}
/**
* 添加元素
* @param index 坐标, 从0开始
* @param e 元素值
*/
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size. ");
}
if(size == data.length){
resize(2 * data.length);
}
// index后面的都往后挪
int i=size-1;
while (i>=index) {
data[i+1] = data[i];
i--;
}
data[index] = e;
size++;
}
/**
* 添加一个元素到数组最后
* 时间复杂度(均摊复杂度) O(1), 考虑到不是每次都会触发resize(), 即最坏的情况(O(n))不是每次都发生, 平均下来每次addLast要进行两次操作
* @param e
*/
public void addLast(E e){
add(size, e);
}
/**
* 添加一个元素到数组最前
* @param e
*/
public void addFirst(E e){
add(0, e);
}
public E get(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("Get failed. Index is illegal. ");
}
return data[index];
}
public E getLast(){
return get(size - 1);
}
public E getFirst(){
return get(0);
}
public void set(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("Set failed. Index is illegal. ");
}
data[index] = e;
}
public boolean contains(E e){
for(int i=0; i<size; i++){
if(data[i].equals(e)){ // 引用比较, ==是值比较
return true;
}
}
return false;
}
public int find(E e){
for(int i=0; i<size; i++){
if(data[i].equals(e)){
return i;
}
}
return -1;
}
/**
* 删除元素
* @param index 元素坐标, 从0开始
* @return 被删元素的值
*/
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. Require index >=0 and index < size. ");
}
E ret = data[index];
// index后面的都往前挪
int i=index+1;
while (i<size) {
data[i-1] = data[i];
i++;
}
size--; // 此时size依然存着一个对象的引用, 所以不会被java的自动回收机制回收
data[size] = null; // 以方便回收, loitering object != memory leak
// 不要太Eager, Lazy一些能避免复杂度震荡
if(size == data.length/4 && data.length/2 != 0){ // 小心size=0, length=1的情况
resize(data.length/2);
}
return ret;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size-1);
}
/**
* 删除指定值的第一个元素
* @param e 元素值
* @return 删除成功返回true, 否则false
*/
public boolean removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
return true;
}
return false;
}
/**
* 删除指定值的所有元素
* @param e 元素值
*/
public void removeAllElement(E e){
while(removeElement(e));
}
/**
* 动态改变容量
* @param newCapacity 设定容量的大小
*/
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int i=0;
while (i<size) {
newData[i] = data[i];
i++;
}
data = newData;
}
/**
* 交换索引为i和j的两个元素
* @param i
* @param j
*/
public void swap(int i, int j){
if(i<0 || i>=size || j<0 || j>=size)
throw new IllegalArgumentException("Index is illegal");
E tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
@Override // 继承重写标志
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append('[');
for(int i=0; i<size; i++){
res.append(data[i]);
if(i != size-1){
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}
ArrayStack.java
public class ArrayStack<E> {
Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void push(E e) {
array.addLast(e);
}
/**
* 弹出栈顶元素
* @return 元素值
*/
@Override
public E pop() {
return array.removeLast();
}
@Override
public E peek() {
return array.getLast();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for(int i=0; i<array.getSize(); i++){
res.append(array.get(i));
if(i != array.getSize()-1){
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
为什么不用链表, 用数组呢? 因为对于链表来说, 每新添一个元素, 都要new一个Node类的对象, 这就意味着一次内存操作, 学过操作系统都知道, 内存操作一般都是系统运行的瓶颈, 所以面对大规模数据的时候，不应该使用链表, 所以就不放代码了溜了
Reference
