元素出栈，入栈顺序的合法性。如入栈的序列（1,2,3,4,5）。出栈序列为（4,5,3,2,1）
元素出栈，入栈顺序的合法性。如入栈的序列（1,2,3,4,5）。出栈序列为（4,5,3,2,1）
思路：
1）如果当前栈为空，且入栈序列不空，则入栈序列的下一个元素入栈；
2）如果当前辅助栈的栈顶元素不等于出栈序列的首元素，那么入栈序列一直入栈，直到入栈序列为空。
3）如果当前辅助栈的栈顶元素等于出栈序列的首元素，那么栈顶元素弹出，出栈序列第一个元素移走；
4) 如果入栈序列为空，出栈序列第一个元素仍然不等于栈顶元素，则表示2个序列是不匹配的。
下面用图说明
开始栈为空
入栈序列第一个元素入栈后，栈顶元素不等于出栈序列第一个元素，而且入栈序列不为空，继续入栈。
元素等于出栈序列首元素，执行出栈操作，4出栈
出栈序列指针指向后一位
判断当前栈顶元素是否等于出栈序列首位元素，且入栈序列不为空，如果不等于，继续入栈，如果等于，进行出栈操作。图中相等，所以5入栈。
当入栈序列为空时，栈顶元素等于dest，就执行出栈操作，在出栈过程中，如果栈顶元素一直等于dest，直到出栈序列为空，说明匹配，如果在出栈过程中，栈顶元素有和dest不相等的，说明匹配失败。
实现代码：
#include <iostream>
#include<string>
using namespace std;
#define MAX 10
template <class T>
class Stack
{
public:
//构造函数
Stack()
:_top(-1)
, _capatity( MAX)
, _stack( new T [_capatity])
{}
//析构函数
~Stack()
{
if (_stack)
{
delete[] _stack;
}
}
//插入数据
void Push(const T& x)
{
//检查栈是否已满
if (_top >= _capatity)
{
return;
}
_stack[++_top] = x;//这里必须是前置++，因为你的初始值为-1
}
//删除数据
T Pop()
{
//检查栈是否为空
if (_top == -1)
{
return -1;
}
return _stack[_top--];//这里必须是后置--，如果是前置--，就取不到栈顶元素
}
//返回栈顶元素
T Top()
{
if (_top == -1)
{
return -1;
}
return _stack[_top];
}
T Empty()const
{
return _top == -1;
}
private:
int _top;//栈顶数据
int _capatity;//栈可容纳的元素
T* _stack;//顺序栈
};
//检查合法性
int IsLegal(char * source, char* dest )
{
Stack<char > s;
if (strlen(source ) != strlen(dest))
{
return -1;
}
s.Push(* source++);//第一个元素入栈
while (*dest )
{
while (*dest != s.Top() && *source)
{
s.Push(* source++);
}
if (*dest == s.Top())
{
s.Pop();
dest++;
continue;
}
else if (*dest != s.Top() && * source == '\0' )
{
return -1;
}
else
{
s.Push(* source++);
}
}
return 0;
}
void Test()
{
Stack<int > s;
cout << s.Empty() << endl; //这里会返回1，因为编译器会把-1当成无符号数处理
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
while (!s.Empty())
{
cout << s.Pop() << " ";
}
cout << endl;
}
int main()
{
Test();
/*char *str = "12345";
char *arr = "45213";
int ret = IsLegal(str, arr);
if (ret == 0)
{
cout << "Legal" << endl;
}
else
{
cout << "No_Legal" << endl;
}*/
system( "pause");
return 0;
}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
