溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
元素出棧，入棧順序的合法性。如入棧的序列（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;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
