三栈顺序问题，一个栈顶是1，栈底是n的一个长度为n的正整数栈，有两个空栈，通过一个过渡栈，可在另一个空栈从底到顶数有不同排列，如1234可转成2143，不过不是所有的排序都合法，4123就是非法序列，现在可以判断输入序列哪个是合法，哪个不合法。
从数学角度分析，设min，mid，max是任意从小到大的三个数，如果出现max..min..mid的情况就是不合法的，如4123，像412，413就是非法情况，可以三重循环去逐一检验，不过时间复杂度比较高；
利用整数的有序性模拟放入的过程，可以直接去找n，n-1...比如应当放在栈底的n,如果Start栈第一个不是n,就把出栈放入Mid栈中，直到找到n,接着就在两个栈的栈顶找n-1放到End中,找不到就重复Start出栈到Mid的过程，如果最后可以排好就是合法的

include<stdio.h>

#include<stdlib.h>
#include<stdbool.h>
typedef int ElemType;

typedef struct
{
	ElemType* base;
	int top;
	int SatckSize;
}Stack;
typedef Stack* PStack;


void InitStack(PStack S, int size)；
ElemType Pop(PStack S)；
bool Push(PStack S, ElemType PushItem)；
ElemType GetTop(PStack S)；
bool IsEmpty(PStack S)；


bool If_Real(PStack Start, PStack Mid, PStack End,int n)
{
	while (!IsEmpty(Start))
	{
		if (GetTop(Start) == n) {  Push(End, Pop(Start)); n--; }
		else if (GetTop(Mid) == n) {  Push(End, Pop(Mid)); n--; }
		else Push(Mid, Pop(Start));
	}
	while (GetTop(Mid) == n&&n) { Push(End, Pop(Mid)); n--; }
	if (n == 0)return true;
	else return false;
}

int main()
{
	PStack Start, Mid, End;
	Start = (PStack)malloc(sizeof(Stack));
	InitStack(Start, 100);
	Mid = (PStack)malloc(sizeof(Stack));
	InitStack(Mid, 100);
	End = (PStack)malloc(sizeof(Stack));
	InitStack(End, 100);

	Push(Start, 4); Push(Start, 3); Push(Start, 2); Push(Start, 6); Push(Start, 1); Push(Start, 5);
	Push(Mid, 0);
	if (If_Real(Start, Mid, End, 6))printf("Reasonable");
	else printf("Unreasonable");


}
void InitStack(PStack S, int size)；
{
	if (!S) exit(1);
	if (size > 0) S->base = (ElemType*)malloc(sizeof(ElemType) * size);
	if (!S->base)exit(1);
	S->SatckSize = size;
	S->top = 0;

}
ElemType Pop(PStack S)
{
	if (S->top <= 0)
	{
		printf("Stack is empty\n"); exit(1);
	}
	S->top--;
	return *(S->base + S->top);
}

bool Push(PStack S, ElemType PushItem)
{
	if (S->top >= S->SatckSize)
	{
		printf("Stack is full\n"); return false;
	}
	*(S->base + S->top) = PushItem;
	S->top++;
	return true;
}
ElemType GetTop(PStack S)
{
	if (S->top <= 0)
	{
		printf("NO Item\n");
		return false;
	}
	return *(S->base + S->top - 1);
}
  bool IsEmpty(PStack S)
{
	if (S->top == 0) return true;
	else return false;
}

三栈让数顺序改变的序列合法问题

原文：https://www.cnblogs.com/tzp-empty-hya/p/14589279.html