栈是一种线性表，仅限在一端进行插入和删除操作，特点是先进后出。
由于栈是一种线性结构，首先可以想到用数组来实现，但由于数组初始化后容量就已经确定，如果不添加扩容操作，则会出现栈溢出，同时扩容操作也会降低一些效率；如果事先九分配较大空间则可能造成资源浪费。一种解决方法是同一个数组实现两个栈，让两个栈向数组中心延伸，当两个栈底元素相遇则溢出，虽然空间利用率大于数组长度的一半，但仍不理想。
另一种实现方法则是链表实现，链表实现可以避免数组实现的各项问题。
栈的基本操作接口
public interface StackMethods {
Stack initStack(Stack stack);//栈的初始化
Object getTop() throws Exception;//获取栈顶
void push(Object data);//入栈
public Object pop() throws Exception;//出栈
void clearStack();//清空栈内元素
boolean isStackEmpty();
int stackLength();
}
栈的实体类
public class Stack {
public Object data;
public Stack next;
public Stack( Object data) {
this.data = data;
}
}
栈基本操作方法的具体实现类SimpleStack
public class SimpleStack implements StackMethods {
private Stack first = null;
@Override
public Stack initStack(Stack stack) {
return null;
}
/**
* 返回站定元素
*/
@Override
public Object getTop() throws Exception{
if( first == null) throw new Exception("empty!");
return first.data;
}
/**
* 入栈
*/
@Override
public void push(Object data) {
Stack stack = new Stack(data);
stack.next = first;
first = stack;
}
/**
* 出栈
*/
@Override
public Object pop() throws Exception{
if( first == null) throw new Exception("empty!");
Object data = first.data;
first = first.next;
return data;
}
/**
* 清空栈
*/
@Override
public void clearStack() {
while(first != null){
first = first.next;
}
}
@Override
public boolean isStackEmpty() {
return first == null;
}
@Override
public int stackLength() {
int i = 0;
while(first != null) i++;
return i;
}
public static void main(String[] args) throws Exception{
SimpleStack s = new SimpleStack();
for(int i=0; i<10; i++){
s.push(i);
System.out.println(s.getTop()+"");
}
while(!s.isStackEmpty()){
System.out.println(s.pop()+"");
}
}
}