Java实现"栈"结构

      一提到栈首先映入我们脑海的一个词就是“后进先出”（即其为单通道，只能有一个出口），显然这是栈最明显且重要的特点。栈的内部实现可以使用数组或链表来完成。

------------------------

1.栈的解析

栈之所有容易被理解是因为其包含的方法非常简单，主要包括以下三个方法：

• push()——一次只能向栈中压如一个数据，先入栈的数据在最下边。
• pop()——每次只能弹出栈顶数据，也就是一个数据。
• peek()——返回当前栈顶数据。

这些功能都由一个非常重要的变量top来辅助完成，其总是指向栈的最顶端，默认值为-1，每压如一个数据top++，弹出一个数据top--。当然在实际使用栈还会有isEmpty()来判断栈是否为空，isFull()方法判断栈是否已经满栈。

2.应用场合

栈通常用来解析某种类型的文本串，例如将输入数据进行反转输出，解析数据中的括号匹配等。

3.实现

public class Stack{
	private int top=-1; //指向栈顶，用于栈的遍历
	private int stackSize=0;//栈的大小
	private char[] stackArray=null;//用于创建栈的数组
	//create stack use array（创建一个指定大小的新栈）
	public void createStack(int size){
		stackSize=size;
		stackArray=new char[size];
	}
	//push element（数据压入）
	public void push(char element){
		if(top!=stackSize-1){  //应在压入数据前判断栈是否为满栈
		    stackArray[top+1]=element;
		    top++;
		}else{
		    System.out.println("Sorry,can`t push!This stack is full!");
		}	
	}
	//pop element（数据弹出）
	public void pop(){
		if(!isEmpty()){//在弹出时应判断栈是否为空栈，空栈则无数据可弹出
		  // System.out.println("pop->"+stackArray[top]);
		   //stackArray[stackSize-1]=0;
		   top--;   
		}else{
		    System.out.println("Sorry,can`t pop!This stack is empty!");
		}	
	}
	//look element（查看栈顶数据）
	public char peek(){
		char peekElement=stackArray[top];
		return peekElement;
	}
	
	//is empty（判断栈是否为空）
	public boolean isEmpty(){
		if(top==-1){
		    return true;
		}else{
		    return false;
		}	
	}
	//is full（判断栈是否为满栈）
	public boolean isFull(){
		if(stackSize!=-1){
		    if(top==stackSize-1){
		        return true;
		    }else{
		        return false;
		}	
		}else{
        	    System.out.println("Sorry,this stack is empty!");
		    return false;
		}	
	}	
}

此时Stack可以作为一个栈的工具类被其他类进行调用，并使用栈中提供的方法，我们来做一个小例子：对括号进行匹配：

import java.util.Scanner;
public class StackTest{
	public static void main(String[] aegs){
		Scanner sc=new Scanner(System.in);
		Stack st=new Stack();//创建栈对象
		System.out.println("Please set the element:");
		String info=sc.nextLine();//输入一行字符串
		st.createStack(info.length());//创建与字符串长度一致栈
		for(int in=0;in<info.length();in++){
			char c=info.charAt(in);
			switch(c){
				case '{':
				case '[':
				case '(':
					st.push(c);//将括号左半部分压栈
				break;
				case '}':
				case ']':
				case ')':
					if(!st.isEmpty()){
						char ch=st.peek();
						st.pop();//将遇到右半部分的括号弹出进行匹配，配对则匹配成功，否则显示未匹配位置
						if( (c=='}' && ch!='{')||
							(c==']' && ch!='[')||
							(c==')' && ch!='(') )
						 {
							System.out.println("Error:"+c+" at "+in);	
						 }
					}else{
						System.out.println("Error:"+c+" at "+in);	
					}
				break;
			}	
		}
		if(!st.isEmpty()){
			System.out.println("Error:missing right delimiter!");	
		}
		System.out.println("\nisEmpty:"+st.isEmpty());
		System.out.println("isFull:"+st.isFull());
	}
}

在本例子中我们只将括号字符压入栈中，并在括号右半部分出现时开始弹出栈中元素进行匹配。由于括号的特点是俩俩相对，所以栈的后进先出的特点很适合对其进行匹配。

4.栈的效率

       通过分析栈的实现过程和栈的实例会发现栈的插入和弹出只能从一个口切入，而不像数组可以根据指定索引值就可以存取数据。所以由于单项和一次只能插入或弹出一个值，所以数据项入栈和出栈的时间复杂度都为常数O(1)，时间消耗并不会依赖于栈中数据项的个数，因此操作时间很短。