【Java数据结构】栈

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

一个char的栈模型类：

package cn.deu;

public class CharStack {
    private int MaxSize;
    private char arr[];
    private int top;
    
    //构造方法
	public CharStack(int maxSize) {
		MaxSize = maxSize;
		arr=new char[MaxSize];
		top=-1;
	}
    
	//入栈
	public void push(char n){
		arr[++top]=n;
	}
	
	//出栈
	public char pop(){
		return arr[top--];
	}
	
	//站是否为空
	public boolean isEmpty(){
		return (top==-1);
	}
	
	//栈是否满
	public boolean isFull(){
		return (top==MaxSize-1);
	}
}

栈实例测试

package en.edu.Test;

import cn.deu.MyStack;

public class StackTest {


	public static void main(String[] args) {
         MyStack ms=new MyStack(10);
         
         ms.push(40);
         ms.push(30);
         ms.push(20);
         ms.push(10);
         ms.push(-10);
         ms.push(-20);
         
         while(!ms.isEmpty()){
        	 System.out.println(ms.pop());
         }
	}


}

应用:

用栈结构来实现单词逆序：

package cn.deu;

public class Reverse {
   private String input;

   public Reverse(String input) {
	this.input = input;
   }
   
   public String doReverse(){
	   CharStack cs=new CharStack(input.length());
	   for (int i = 0; i < input.length(); i++) {
		char ch=input.charAt(i);
		cs.push(ch);
	   }
	   String output="";
	   while(!cs.isEmpty()){
		   char ch=cs.pop();
		   output+=ch;
	   }
	   return output;
	   
   }
   
}