题解 | #栈的压入、弹出序列#

C 的粗暴实现

#include<stdbool.h>

typedef struct Stack {
	int val;
	struct Stack* next;
}Stack;

int IsEmpty(Stack* S)
{
	if (!S || !(S->next))
		return 1;
	return 0;
}

void push(Stack* S, int v)
{
	Stack* tmp = (Stack*)malloc(sizeof(Stack));
	tmp->val = v;
	tmp->next = S->next;
	S->next = tmp;
}

int pop(Stack* S)
{
	Stack* tmp;
	int tmp_v;
	if (!IsEmpty(S))
	{

		tmp = S->next;
		tmp_v = tmp->val;

		S->next = tmp->next;

		free(tmp);
		tmp = NULL;
		return tmp_v;
	}
	return -1000;
}

int top(Stack* S)
{
	Stack* tmp;
	int tmp_v;
	if (!IsEmpty(S))
	{
		return S->next->val;
	}
	return -1000;
}

bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    Stack* head = (Stack*)malloc(sizeof(Stack));
	int* Push = pushV;
	int* Pop = popV;
	int flag = 0;
    
	
	if (pushVLen != popVLen|| pushV==NULL||popV==NULL)
		return false;

	head->next = NULL;
	head->val = -1000;

	while (Pop - popV < popVLen)
	{
		while (IsEmpty(head) || top(head) != *Pop)
		{
			if (Push - pushV >= pushVLen)
				break;
			push(head, *Push);
			Push++;
		}

		if (top(head) != *Pop)
			break;
		pop(head);
		Pop++;
	}
	if (IsEmpty(head) && Pop - popV == popVLen)
		return 1;
    return 0;
}