堆栈的链式与数组仿真JAVA实现
文件清单如下:
Node.java //链结点接口
SLNode.java //链结点实现
StackEmptyException.java//堆栈异常处理类
Stack.java //堆栈接口定义类
StackSLinked.java //链式结构实现堆栈
StackArray.java //循环数组实现堆栈
Stackdemo.java //测试堆栈功能
*******************************************************
//编译OK chinanetboy with Eclipse
//Node.java
//链结点接口
package dsa.datastruct;
public interface Node{
//获取结点数据域
public Object getData();
//设置结点数据域
public void setData(Object obj);
}
*******************************************************
//编译OK chinanetboy with Eclipse
//SLNode.java
//链结点实现
package dsa.datastruct;
public class SLNode implements Node{
private Object element; //数据成员
private SLNode next; //指向下一个成员结点
//两个构造器
public SLNode(){this(null,null);}
public SLNode(Object obj, SLNode nextnode){
this.element=obj;
this.next =nextnode;
}
//2对属性读取器
public void setNext(SLNode nextnode){this.next=nextnode;}
public SLNode getNext(){return next;}
public void setData(Object obj){element=obj;}
public Object getData(){return element;}
}
*******************************************************
//编译OK chinanetboy with Eclipse
//Stack.java
//堆栈接口定义
package dsa.datastruct;
public interface Stack {
//1.返回堆栈的大小
public int getSize();
//2.判断堆栈是否为空
public boolean isEmpty();
//3.数据元素e入栈
public void push(Object e);
//4.栈顶元素出栈
public Object pop() throws StackEmptyException;
//5.取栈顶元素
public Object peek() throws StackEmptyException;
}
*******************************************************
//编译OK chinanetboy with Eclipse
//StackEmptyException.java
//堆栈为空的异常处理类
package dsa.datastruct;
public class StackEmptyException extends RuntimeException {
public StackEmptyException(String err) {
super(err);
}
}
*******************************************************
//StackSLinked.java
//用链表模仿堆栈
package dsa.datastruct;
public class StackSLinked implements Stack {
private SLNode top; //链表首结点引用
private int size; //栈的大小
public StackSLinked() {
top = null;
size = 0;
}
//返回堆栈的大小
public int getSize() {
return size;
}
//判断堆栈是否为空
public boolean isEmpty() {
return size==0;
}
//数据元素e入栈
public void push(Object e) {
SLNode q = new SLNode(e,top);
top = q;
size++;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (size<1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = top.getData();
top = top.getNext();
size--;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (size<1)
throw new StackEmptyException("错误，堆栈为空。");
return top.getData();
}
}
*******************************************************
//编译OK chinanetboy with Eclipse
//StatckArray.java
//堆栈的数组实现
package dsa.datastruct;
public class StackArray implements Stack{
private final int LEN = 10; //数组的默认大小
private Object[] elements; //数据元素数组
private int top; //栈顶指针
//构造器
public StackArray() {
top = -1;
elements = new Object[LEN];
}
//1.返回堆栈的大小
public int getSize() {
return top+1;
}
//2.判断堆栈是否为空
public boolean isEmpty() {
return top<0;
}
//数据元素e入栈
public void push(Object e) {
if (getSize()>=elements.length) expandSpace();
elements[++top] = e;
}
private void expandSpace(){
Object[] a = new Object[elements.length*2];
for (int i=0; i<elements.length; i++)
a[i] = elements[i];
elements = a;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = elements[top];
elements[top--] = null;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
}
*******************************************************
//Stackdemo.java
//测试堆栈功能
package dsa.test;
import dsa.datastruct.*;
public class Stackdemo {
public static void main(String[] args) {
Stack s1 = new StackSLinked();//链表模仿栈结构
s1.push(33);
s1.push(44);
s1.pop();
s1.push(11);
System.out.println("s1.isEmpty()="+s1.isEmpty());
System.out.println("s1.peek()="+s1.peek());
System.out.println("s1.getSize()="+s1.getSize());
Stack s2 = new StackArray();//数组模仿栈结构
s2.push(55);
s2.push(66);
s2.pop();
System.out.println("s2.isEmpty()="+s2.isEmpty());
System.out.println("s2.peek()="+s2.peek());
System.out.println("s2.getSize()="+s2.getSize());
}
}
运行结果:
s1.isEmpty()=false
s1.peek()=11
s1.getSize()=2
s2.isEmpty()=false
s2.peek()=55
s2.getSize()=1
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/chinayaosir/archive/2008/09/01/2860976.aspx