本文根据《大话数据结构》一书，实现了Java版的栈的顺序存储结构、两栈共享空间、栈的链式存储机构。

栈：限定仅在表尾进行插入和删除操作的线性表。

栈的插入（进栈）和删除（出栈）操作如下图所示。

 　　

 

1.栈的顺序存储结构

　　用数组存放数据，top变量来指示栈顶元素在数组中的位置（栈顶指针）。一个长度为5的栈的示意图如下：

　　实现程序：

/** * 栈的顺序储存结构 *  * 问题：构造器中，泛型数组创建是否有更好的方法？ * @author Yongh * */public class SqStack
     
       {	private E[] data;	private int top;  //栈顶指针，top=-1时为空栈	private int maxSize;	private static final int DEFAULT_SIZE= 10;		public SqStack() {		this(DEFAULT_SIZE);	}	public SqStack(int maxSize) {		//无法创建泛型数组 data=new E[maxSize];		data=(E[]) new Object[maxSize];		top=-1;		this.maxSize=maxSize;	}		public void push(E e) {		if(top==maxSize-1) 			throw new RuntimeException("栈已满，无法进栈！");		top++;		data[top]=e;	}		public E pop() {		if(top==-1)			throw new RuntimeException("空栈，无法出栈！");		E e=data[top];		top--;		return e;	}		public void printStack() {		if(top==-1) {			System.out.println("空栈");					}else {			for(int i=0;i<=top;i++) {				System.out.println(data[i]);			}		}			}}
     

　　

　　测试代码：

public class StackTest {	public static void main(String[] args) {		SqStack
     
       sqStack=new SqStack
      
       ();			    Student[] students= {new Student("小A",11),new Student("小B",12),new Student("小C",13),	            new Student("小D",14),new Student("小E",151)};	    for(int i=0;i<5;i++) {	    	sqStack.push(students[i]);	    }	    sqStack.printStack();	    for(int i=0;i<5;i++) {	    	sqStack.pop();	    }	    sqStack.printStack();	    	}       }class Student{    public Student(String name, int age) {        this.name=name;        this.age=age;    }    String name;    int age;    public String toString() {    	return name;    }}
      
     

　　

小A小B小C小D小E空栈

 

2.两栈共享空间

　　通过一个数组存放两个栈，能较好地利用空间。用top1和top2变量表示栈1和栈2的栈顶指针，两个栈的栈底分别位于数组的头部和尾部。

　　实现程序（在SqStack程序的基础上稍加改造即可）：

/**  * 栈的顺序储存结构（两栈共享空间） *  * 注意点：栈满条件为top1+1==top2 *  * @author Yongh * */public class SqDoubleStack
     
       {	private E[] data;	private int top1;  //栈1栈顶指针，top=-1时为空栈	private int top2;  //栈2栈顶指针，top=maxSize-1时为空栈	private int maxSize;	private static final int DEFAULT_SIZE= 10;		public SqDoubleStack() {		this(DEFAULT_SIZE);	}	public SqDoubleStack(int maxSize) {		//无法创建泛型数组 data=new E[maxSize];		data=(E[]) new Object[maxSize];		top1=-1;		top2=maxSize-1;		this.maxSize=maxSize;	}		/*	 * 进栈操作，stackNumber代表要进的栈号	 */	public void push(int stackNumber,E e) {				if(top1+1==top2) 			throw new RuntimeException("栈已满，无法进栈！");		if(stackNumber==1) {			data[++top1]=e;					}else if(stackNumber==2) {			data[--top2]=e;					}else {			throw new RuntimeException("栈号错误！");		}	}		/*	 * 出栈操作	 */	public E pop(int stackNumber) {		E e;		if(stackNumber==1){			if(top1==-1)				throw new RuntimeException("空栈1，无法出栈！");			e=data[top1--];		}else if(stackNumber==2) {			if(top2==maxSize-1)				throw new RuntimeException("空栈2，无法出栈！");			e=data[top2++];		}else {			throw new RuntimeException("栈号错误！");		}		return e;	}	}
     

　　

3.栈的链式存储结构

 　　通过单向链表实现的栈，栈顶放在单链表的头部（注意进栈操作并不是往链表的后面插入，而是从头部插入）。

　　链栈的示意图如下。

　　插入与删除操作示意图：

　　

　　实现程序：

/** *  * 栈的链式存储结构 *  * @author Yongh */public class LinkStack
     
       {	private StackNode
      
        top;	private int count;		private class StackNode
       
        {		E data;		StackNode
        
          next;		public StackNode(E data,StackNode
         
           next) {			this.data=data;			this.next=next;		}	}		public LinkStack() {		top=new StackNode
          
           (null, null); count=0; } public void push(E e) { StackNode
           
             node=new StackNode
            
             (e, top); top=node; count++; } public E pop() { if(count==0) throw new RuntimeException("空栈，无法出栈！"); StackNode
             
               node; node=top; top=top.next; count--; E e=node.data; node=null; return e; } public void printStack() { if(count==0) { System.out.println("空栈"); }else { StackNode
              
                node=top; for(int i=0;i
               
                 linkStack=new LinkStack
                
                 (); Student[] students= {new Student("小A",11),new Student("小B",12),new Student("小C",13), new Student("小D",14),new Student("小E",151)}; for(int i=0;i<5;i++) { linkStack.push(students[i]); } linkStack.printStack(); System.out.println("----"); for(int i=0;i<5;i++) { System.out.println(linkStack.pop()); } linkStack.printStack(); }}
                
               
              
             
            
           
          
         
        
       
      
     

　　

小E小D小C小B小A----小E小D小C小B小A空栈

 

 4.栈的应用

　　（1）实现递归

　　　　一些问题（如斐波那契数列的求解），可通过递归函数获得，而递归函数是由栈来实现的。

典型的斐波那契数列

　　（2）四则运算表达式求值

　　　　利用后缀表达式（逆波兰表示法）结合栈可以实现四则运算表达式的求解。而且通过栈，就可以把我们平时用的中缀表达式转化为后缀表达式。