Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
能动态调整数组大小、用数组实现的栈
import java.util.Iterator;
import java.util.Scanner;
//自动修改大小、内部用数组实现的栈
public class ResizingArrayStack<Item> implements Iterable<Item>{
private Item a[];
// 元素个数
private int N;
public ResizingArrayStack() {
// 不能创建泛型数组
a = (Item[]) new Object[2];
}
// 添加一个元素
public void push(Item item) {
if(isFull()) reSize(a.length * 2);
a[N++] = item;
}
// 删除最近添加的元素
public Item pop() {
if(isEmpty()) return null;
if(N * 4 == a.length) reSize(a.length / 2);
return a[--N];
}
// 栈是否为空
public boolean isEmpty() {
return N == 0;
}
// 栈是否已满
public boolean isFull() {
return N == a.length;
}
// 栈中的元素数量
public int size() {
return N;
}
// 创建一个新数组,将元素复制到新数组
private void reSize(int newSize) {
Item[] b = (Item[]) new Object[newSize];
for(int i=0; i<a.length; i++) {
b[i] = a[i];
}
a = b;
}
// Iterable 接口未实现的方法
@Override
public Iterator<Item> iterator() {
return new myIterator();
}
// 迭代器
private class myIterator implements Iterator<Item> {
private int i;
@Override
public boolean hasNext() {
return i < N;
}
@Override
public Item next() {
return a[i++];
}
}
// 测试用例
public static void main(String[] args) {
ResizingArrayStack<String> stack = new ResizingArrayStack<>();
Scanner in = new Scanner(System.in);
// 从键盘输入,根据内容入栈、出栈或者是结束输入。
while(in.hasNext()) {
String str = in.nextLine();
if(str.equals("-")) stack.pop();
else stack.push(str);
if(str.equals("exit")) break;
System.out.println();
}
for (String string : stack) {
System.out.print(string + " ");
}
in.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.