/**
* 栈的实现
*/
package com.zl.stack;
import java.util.NoSuchElementException;
public interface IStack<T> {
/**
* 获取栈顶元素并且移除
*
* @return T 返回栈顶元素
*/
public T pop() throws NoSuchElementException;
/**
* 将元素压入栈顶
*
* @param t
* @return
*/
public boolean push(T t) throws ArrayIndexOutOfBoundsException;
/**
* 获取栈顶元素,不移除
*
* @return 获取栈顶元素
*/
public T peek() throws NoSuchElementException;
/**
* 栈是否为空
*
* @return
*/
public boolean isEmpty();
/**
* 获取指定元素在栈的位置索引
*
* @param obj
* @return
*/
public int getIndex(Object obj) throws NoSuchElementException;
/**
* 元素个数
*/
public int length();
}
package com.zl.stack;
import java.util.NoSuchElementException;
/**
* <p>
* 使用顺序表实现栈.
* </p>
* <p>
* 可以设置初始容量, 容量确定后不能改变.
*
* @author gg
*
* @param <T>
*/
public class ArrayStack<T> implements IStack<T> {
private static final int INITIAL_CAPACITY = 15;
private Object[] elements;
private int length;
private int capacity;
public ArrayStack() {
this(INITIAL_CAPACITY);
}
public ArrayStack(int capacity) {
elements = new Object[capacity];
this.capacity = capacity;
}
@SuppressWarnings("unchecked")
@Override
public T pop() {
if (length <= 0) {
throw new NoSuchElementException("栈为空,没有元素");
}
T t = (T) elements[--length];
System.out.println("出栈:" + t.toString());
return t;
}
@Override
public boolean push(T t) {
if (!checkBound()) {
throw new ArrayIndexOutOfBoundsException(checkBoundMessage());
}
elements[length++] = t;
System.out.println("入栈:" + t.toString());
return true;
}
@SuppressWarnings("unchecked")
@Override
public T peek() {
if (length <= 0) {
throw new NoSuchElementException("栈为空,没有元素");
}
T t = (T) elements[length - 1];
System.out.println("获得栈顶元素:" + t.toString());
return t;
}
@Override
public boolean isEmpty() {
return length == 0;
}
@Override
public int getIndex(Object obj) {
for (int i = 0; i < length; i++) {
if (elements[i].equals(obj)) {
System.out.println("找到索引是:" + i);
return i;
}
}
throw new NoSuchElementException("未找到元素:" + obj.toString());
}
@Override
public int length() {
System.out.println("length = " + length);
return length;
}
public String travers() {
if (isEmpty()) {
return null;
}
StringBuffer sb = new StringBuffer();
sb.append("开始遍历....");
sb.append("\n");
while(length>0){
sb.append(pop());
sb.append("\n");
}
sb.append("结束遍历....");
return sb.toString();
}
// 检查是否存在空间把元素压入栈
private boolean checkBound() {
return length >= 0 && length < capacity;
}
// 越界信息
private String checkBoundMessage() {
return "总容量:" + capacity + " 现在存在的元素个数:" + length;
}
}
|