package Stack;
import java.util.Iterator;
/**
* 顺åºæ ˆçš„动æ€æ‰©å®¹
* Author: PeiJiaNi
* @param 顺åºæ ˆå…ƒç´ 类型
*/
public class DynamicStackBaseArray implements Iterable {
private T[] items; // 数组
private int count; // æ ˆä¸çš„å…ƒç´ ä¸ªæ•°
private int length; // æ ˆç©ºé—´å¤§å°
/**
* åˆå§‹åŒ–æ ˆ
*
* @param length æ ˆç©ºé—´å¤§å°
*/
public DynamicStackBaseArray(int length) {
this.items = (T[]) new Object[length];
this.count = 0;
this.length = length;
}
/**
* å…¥æ ˆæ“作 å¹³å‡æ—¶é—´å¤æ‚度O(1)
*
* @param item å…¥æ ˆå…ƒç´
*/
public void push(T item) {
// æ ˆç©ºé—´å·²æ»¡ï¼Œåˆ™æ‰©å®¹
if (count == length) {
resize(2 * items.length);
}
items[count++] = item;
}
/**
* å‡ºæ ˆæ“作 å¹³å‡æ—¶é—´å¤æ‚度O(1)
*
* @return å¦‚æžœæ ˆå†…ä¸ä¸ºç©ºï¼Œåˆ™è¿”å›žæ ˆé¡¶å…ƒç´ ï¼Œå¦åˆ™è¿”回-1
*/
public T pop() {
if (count == 0) {
System.out.println("当å‰æ ˆå·²ç©ºï¼Œæ— æ³•è¿›è¡Œå‡ºæ ˆæ“作");
return null;
}
T item = items[--count];
items[count] = null;
if (count > 0 && (count == items.length / 4)) {
resize(items.length / 2);
}
// è¿”å›žä¸‹æ ‡ä¸º count-1 çš„æ•°ç»„å…ƒç´ ï¼Œå¹¶ä¸”æ ˆä¸å…ƒç´ 个数count-1
return item;
}
/**
* æ ˆç©ºé—´åŠ¨æ€å¢žåŠ 或å‡å°
*
* @param size
*/
private void resize(int size) {
T[] newItems = (T[]) new Object[size];
for (int i = 0; i < count; i++) {
newItems[i] = this.items[i];
}
this.items = newItems;
}
//è¿”å›žæ ˆä¸æœ€è¿‘æ·»åŠ çš„å…ƒç´ è€Œä¸åˆ 除它
public T peek() {
return items[count - 1];
}
/**
* 判æ–当å‰æ ˆæ˜¯å¦ä¸ºç©º
*
* @return æ ˆä¸ºç©ºï¼Œåˆ™è¿”å›žtrue,å¦åˆ™è¿”回-1
*/
public boolean isEmpty() {
return count == 0;
}
/**
* è¿”å›žæ ˆä¸å…ƒç´ 个数
*
* @return
*/
public int size() {
return count;
}
@Override
public Iterator iterator() {
return new ArrayIterator();
}
// 内部类
class ArrayIterator implements Iterator {
int numOfItems = count;
@Override
public boolean hasNext() {
return numOfItems > 0;
}
@Override
public T next() {
return items[--numOfItems];
}
}
public static void main(String[] args) {
DynamicStackBaseArray stack = new DynamicStackBaseArray(6);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
// System.out.println(stack.peek());
Iterator iterator = stack.iterator();
// System.out.println(iterator.hasNext());
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}