HDU1022 Train Problem

查看此图便会很容易的理解什么是栈了——就是只有一个入口（封闭的容器）,所以栈的特点就是先进后出，或者后进先出。

提到栈，不得不提指针，进栈时先移指针后进栈，出栈时先出栈后移指针。

下面要说的，此堆非彼堆：
栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。另外，栈数据可以共享。堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。 

另说下java中==和equals的区别，也加深对栈和堆的理解
==比较的是两个对象的栈中的数据，比较的是基本数据类型的内容；而equals比较的是堆中的数据，比较的是引用数据类型的地址。

HDU1022 详见http://acm.hdu.edu.cn/showproblem.php?pid=1022


java中有栈的类库，java.util.Stack;此类库中就有5个方法，简单实用记住就好
Ⅰ.empty() 测试堆栈是否为空，返回boolean值
Ⅱ.peek() 查看堆栈顶部的对象，但不会从堆栈中移除 
Ⅲ.pop() 移除并返回堆栈顶部的对象
Ⅳ.push(E e) 把项压入堆栈顶部 
Ⅴ.search(Object o) 返回对象在堆栈中的位置（int型），以1为基数

import java.util.*;
public class Main
{
	public static void main(String[] args)
	{
		Scanner scan=new Scanner(System.in);
		while(scan.hasNext())
		{
			int n=scan.nextInt();
			int index1=0,index2=0,k=0;
			boolean[] judge=new boolean[18];
			String init=scan.next();
			String comp=scan.next();
			Stack<Character> st=new Stack<Character>();
			int temp=1;
			while(index2<n)
			{
			   if(!st.empty()&&st.peek().equals(comp.charAt(index2)))
				{
					judge[k++]=false;
					st.pop();
					index2++;
				}
				else if(index1<n)
				{
					judge[k++]=true;
					st.push(init.charAt(index1));
					index1++;
				}
				else{
					temp=0;
					break;
				}
			}
			if(temp==1)
			{
				System.out.println("Yes.");
				for(int w=0;w<k;w++)
				{
					if(judge[w])
						System.out.println("in");
					else
						System.out.println("out");
				}
			}
			else
				System.out.println("No.");
			System.out.println("FINISH");
		}	
	}
}