判断出入顺序是否符合栈

65 阅读 0 评论 43 点赞

我是靠谱客的博主生动心锁，最近开发中收集的这篇文章主要介绍判断出入顺序是否符合栈，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

//已
package four;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
4.判断出入顺序是否符合栈
例如:入栈的顺序是:a b c d e,一共有120种排序方式,代码判断那种排序符合出栈方式
(用递归输出 a，b，c，d，e 的 120 种排列方式)
代码包括两个方法:
4.1利用代码还原栈的原理进行判断  有入栈和出栈的序列
出栈序列和入栈序列进行比较,
如果出栈的序号大,就进行入栈一个,然后入栈序列加一,
如果出栈序号和入栈相等,就出栈然后出栈,两个序列号都加一
如果小于的话,就出栈,
出栈之前还要判断栈顶是否是这个数,如果不是的话就说明这个出栈序列号不符合出栈要求
4.2利用快速的方法判断是否符合
4.2.1两个数之间大于2
4.2.2是前后交换的
4.2.3他们之间的数在之前没有出现过
4.2.4从右到左进行判断
 */
public class Warehouse
{
	public static void main(String[] args) throws Exception
	{
		Warehouse w = new Warehouse();
		String[] a ={ "a", "b", "c","d" ,"e"};
		String sum="";
		for(String s:a)
		{
			sum=sum+s;
		}
		List<String> possible = new ArrayList<String>();
		System.out.println(sum+"的所有全排列可能");
		w.kinds(a, 0, a.length, possible);
		for (String temp : possible)
		{
			System.out.println(temp + "  " + w.method1(sum, temp));
		}
	}

	/*
	 * 4.1利用代码还原栈的原理进行判断 有入栈和出栈的序列 出栈序列和入栈序列进行比较, 如果出栈的序号大,就进行入栈一个,然后入栈序列加一,
	 * 如果出栈序号和入栈相等,就出栈然后出栈,两个序列号都加一 如果小于的话,就出栈,
	 * 出栈之前还要判断栈顶是否是这个数,如果不是的话就说明这个出栈序列号不符合出栈要求
	 */
	public boolean method1(String str1, String str2) throws Exception
	{
		boolean judge = true;
		char[] a = str1.toCharArray();
		char[] b = str2.toCharArray();
		int falg1 = 0, falg2 = 0;
		while (true)
		{
			if (Arrays.binarySearch(a, b[falg2]) > falg1) // 如果出栈的序号大,就进行入栈一个,然后入栈序列加一,
			{
				falg1++;
			}
			if (Arrays.binarySearch(a, b[falg2]) < falg1) // 如果小于的话,就出栈,
			{
				int location = falg1 - 1;
				while (a[location] == ' ')
					location--;
				if (a[location] == b[falg2])
				{
					a[location] = ' '; // 将出栈的位置变成空
					falg2++;
				} else
				{
					judge = false;
					break;
				}
			}
			if (Arrays.binarySearch(a, b[falg2]) == falg1) // 如果出栈序号和入栈相等,就出栈然后出栈,两个序列号都加一
			{
				if(falg1<a.length-1)
				{
					a[falg1]=' ';
					falg1++;
				}
				if(falg2<a.length-1)
					falg2++;
			}
			if(falg1 == a.length-1 && falg2 == b.length-1)
				break;
		}
		return judge;
	}
	public void method2()
	{
		System.out.println("我不想写了");
	}
	/*
	 * 全排列的递归写法
	 * 递归思想是:比如abc的全排列,
	 * 先是指向a的前一个,整个的abc的全排列等于abc的前一个位置,即第零个位置的每一个可能加上abc的全排列
	 * 再到第一个位置,它的每一个可能是a+(bc的全排列)  ,b+(ac的全排列),  c+(ab的全排列)
	 * 再到第二个位置,它的每一个可能是 
	 * 		a+(bc的全排列)---->ab+(c的全排列)
	 * 		b+(ac的全排列)---->ba+(c的全排列)
	 * 		c+(ab的全排列)---->ca+(b的全排列)
	 */
	public void kinds(String[] s, int start, int end, List<String> cup)
	{
		String sum = "";
		if (start == end)
		{
			for (String son : s)
			{
				sum = sum + son;
			}
			cup.add(sum);

			return;
		}
		for (int i = start; i < end; i++)
		{
			swap(s, i, start);
			kinds(s, start + 1, end, cup);
			swap(s, i, start);
		}
	}

	public void swap(String[] a, int i, int j)
	{
		String temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}