首页 > 代码库 > 【数据结构】栈-数组的实现

【数据结构】栈-数组的实现

首先是定义栈的基本结构,因为用数组实现

	private String[] stack;
	private int TOP = 0;

然后是构造方法

	StackOfStrings(int capacity) {
		stack = new String[capacity];
	}

然后是push,注意,TOP永远指向的是压入元素的后一位。

	public void push(String str) {
		if (TOP == stack.length) // if full, increase the stack size
			resize(2 * stack.length);
		stack[TOP++] = str;
	}

然后是pop

	public String pop() {
		String popItem = stack[--TOP];
		// if equal to 1/4, decrease the stack size
		if (TOP > 0 && TOP == stack.length / 4)
			resize(stack.length / 2);
		return popItem;
	}


然后是判空操作,想想为什么空的时候 TOP是0

	public boolean isEmpty() {
		return TOP == 0;
	}

最后附上resize的代码

	public void resize(int capacity) {
		String[] temp = new String[capacity];
		for (int i = 0; i < TOP; i++)
			temp[i] = stack[i];
		stack = temp;
	}




【数据结构】栈-数组的实现