以下是一个基于栈的出栈序列检查的
C语言代码：
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
int top = -1;
void push(int val)
{
if (top == MAX_STACK_SIZE - 1)
{
printf("Stack overflow
");
exit(1);
}
stack[++top] = val;
}
int pop()
{
if (top == -1)
{
printf("Stack underflow
");
exit(1);
}
return stack[top--];
}
int main()
{
int n, i, j;
int push_seq[MAX_STACK_SIZE], pop_seq[MAX_STACK_SIZE];
printf("Enter the size of the sequence: ");
scanf("%d", &n);
printf("Enter the push sequence: ");
for (i = 0; i < n; i++)
{
scanf("%d", &push_seq[i]);
}
printf("Enter the pop sequence: ");
for (i = 0; i < n; i++)
{
scanf("%d", &pop_seq[i]);
}
i = 0;
j = 0;
while (i < n && j < n)
{
if (push_seq[i] == pop_seq[j])
{
i++;
j++;
}
else if (top != -1 && stack[top] == pop_seq[j])
{
pop();
j++;
}
else
{
push(push_seq[i++]);
}
}
while (top != -1 && j < n)
{
if (stack[top] == pop_seq[j])
{
pop();
j++;
}
else
{
break;
}
}
if (top == -1 && j == n)
{
printf("The pop sequence is valid.
");
}
else
{
printf("The pop sequence is not valid.
");
}
return 0;
}
该程序要求用户输入一个序列的大小，一个压栈序列和一个出栈序列。然后，程序使用一个基于栈的算法来检查出栈序列的合法性。如果出栈序列是合法的，程序将输出“ The pop sequence is valid.”，否则输出“The pop sequence is not valid.”。该算法的基本思想是模拟压栈和出栈过程。我们从压栈序列的开头开始遍历，遇到一个和出栈序列的当前元素相等的元素时，我们将它出栈。否则，我们将该元素压入栈中。如果栈顶元素和出栈序列的当前元素相等，则将栈顶元素出栈。在遍历完压栈序列后，我们检查栈中剩余的元素是否可以与出栈序列中的元素匹配。如果可以，则弹出栈顶元素并移动到下一个出栈元素。如果不能匹配，则出栈序列无效。此算法的时间复杂度为O(n)，其中n为序列的大小。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/13945.html