元素出棧，入棧順序的合法性。如入棧的序列（1,2,3,4,5）。出棧序列為（4,5,3,2,1）

創(chuàng)新互聯(lián)公司專注于涼城企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站,商城網(wǎng)站開發(fā)。涼城網(wǎng)站建設(shè)公司,為涼城等地區(qū)提供建站服務(wù)。全流程按需定制開發(fā)，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

思路：

1）如果當(dāng)前棧為空，且入棧序列不空，則入棧序列的下一個(gè)元素入棧；

2）如果當(dāng)前輔助棧的棧頂元素不等于出棧序列的首元素，那么入棧序列一直入棧，直到入棧序列為空。

3）如果當(dāng)前輔助棧的棧頂元素等于出棧序列的首元素，那么棧頂元素彈出，出棧序列第一個(gè)元素移走；

4) 如果入棧序列為空，出棧序列第一個(gè)元素仍然不等于棧頂元素，則表示2個(gè)序列是不匹配的。

下面用圖說明

開始棧為空

入棧序列第一個(gè)元素入棧后，棧頂元素不等于出棧序列第一個(gè)元素，而且入棧序列不為空，繼續(xù)入棧。

元素等于出棧序列首元素，執(zhí)行出棧操作，4出棧

出棧序列指針指向后一位

判斷當(dāng)前棧頂元素是否等于出棧序列首位元素，且入棧序列不為空，如果不等于，繼續(xù)入棧，如果等于，進(jìn)行出棧操作。圖中相等，所以5入棧。

當(dāng)入棧序列為空時(shí)，棧頂元素等于dest，就執(zhí)行出棧操作，在出棧過程中，如果棧頂元素一直等于dest，直到出棧序列為空，說明匹配，如果在出棧過程中，棧頂元素有和dest不相等的，說明匹配失敗。

實(shí)現(xiàn)代碼：

#include <iostream>

#include<string>

using namespace std;

#define MAX 10

template <class T>

class Stack

{

public:

         //構(gòu)造函數(shù)

        Stack()

        :_top(-1)

        , _capatity( MAX)

        , _stack( new T [_capatity])

        {}

         //析構(gòu)函數(shù)

        ~Stack()

        {

                 if (_stack)

                {

                         delete[] _stack;

                }

        }

         //插入數(shù)據(jù)

         void Push(const T& x)

        {

                 //檢查棧是否已滿

                 if (_top >= _capatity)

                {

                         return;

                }

                _stack[++_top] = x;//這里必須是前置++，因?yàn)槟愕某跏贾禐?1

        }

         //刪除數(shù)據(jù)

         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;//棧頂數(shù)據(jù)

         int _capatity;//棧可容納的元素

         T* _stack;//順序棧

};

//檢查合法性

int  IsLegal(char * source, char* dest )

{

         Stack<char > s;

         if (strlen(source ) != strlen(dest))

        {

                 return -1;

        }

        s.Push(* source++);//第一個(gè)元素入棧

         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; //這里會(huì)返回1，因?yàn)榫幾g器會(huì)把-1當(dāng)成無符號(hào)數(shù)處理

        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;

}

標(biāo)題名稱：元素出棧，入棧順序的合法性。如入棧的序列（1,2,3,4,5）。出棧序列為（4,5,3,2,1）
文章起源：http://www.rwnh.cn/article2/peohic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷、電子商務(wù)、網(wǎng)站內(nèi)鏈、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)