c#如何實(shí)現(xiàn)棧的壓入、彈出序列

這篇文章將為大家詳細(xì)講解有關(guān)c#如何實(shí)現(xiàn)棧的壓入、彈出序列，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

    輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1、2、3、4、5是某棧的壓棧順序，序列4、5、3、2、1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4、3、5、1、2就不可能是該壓棧序列的彈出序列。

    首先，可以在第一個(gè)序列也就是壓棧順序中找第二個(gè)序列中第一個(gè)元素，是4，因?yàn)榈诙€(gè)序列中第一個(gè)元素是第一個(gè)被彈出的，那么在壓入順序中，被彈出數(shù)據(jù)之前的所有數(shù)據(jù)都被壓入了棧中且還沒(méi)有被彈出，也就是連續(xù)壓進(jìn)去了1、2、3、4，然后彈出第一個(gè)數(shù)據(jù)4；之后在第二個(gè)序列中往后的元素，是5，如果不是棧頂元素就在第一個(gè)序列中從4開(kāi)始往后找繼續(xù)壓入再?gòu)棾?，再次往后取第二個(gè)序列中的元素，如果是棧頂元素就彈出，直到?？涨覂蓚€(gè)序列都遍歷一遍為止，否則，如果棧不為空且兩個(gè)序列都遍歷過(guò)了，則說(shuō)明第二個(gè)序列不是壓棧序列的彈出序列。

程序設(shè)計(jì)如下：

#include <iostream>
#include <stack>
#include <assert.h>
using namespace std;

bool IsPopSeq(int *push_arr, int *pop_arr, size_t size)
{
    assert(push_arr && pop_arr && size);//判斷參數(shù)的有效性
    stack<int> s;

    size_t push_index = 0;
    size_t pop_index = 0;
    while(pop_index < size)
    {
    //將輸入隊(duì)列中處于輸出隊(duì)列第一個(gè)元素之前的所有元素都?jí)喝霔?nèi)   
        while(push_index < size)
        {
            s.push(push_arr[push_index]);
            ++push_index;
            if(s.top() == pop_arr[pop_index])
                break;
        }
        //判斷，如果輸入隊(duì)列全部壓完了但仍然沒(méi)有找到輸出隊(duì)列的的第一個(gè)元素，就返回false
        if((!s.empty()) && (s.top() != pop_arr[pop_index])) 
            return false;

        //當(dāng)棧中的元素恰好就是輸出隊(duì)列的彈出順序時(shí)就不斷的彈出
        while((!s.empty()) && (pop_arr[pop_index] == s.top()))
        {
            s.pop();
            ++pop_index;
        }
    }   
    //正確返回的條件就是當(dāng)輸入隊(duì)列和輸出隊(duì)列都遍歷完畢且棧為空時(shí)判斷完成
    if((push_index == size) && (pop_index == size) && s.empty())
        return true;
    else
        return false;
}

int main()
{
    int push_arr[] = {1, 2, 3, 4, 5};

    int pop_arr1[] = {4, 5, 3, 2, 1};
    int pop_arr2[] = {4, 3, 5, 1, 2};
    int pop_arr3[] = {2, 5, 3, 4, 1};

    size_t size = sizeof(push_arr)/sizeof(push_arr[0]);

    bool ret = IsPopSeq(push_arr, pop_arr1, size);
    cout<<ret<<endl;
    ret = IsPopSeq(push_arr, pop_arr2, size);
    cout<<ret<<endl;
    ret = IsPopSeq(push_arr, pop_arr3, size);
    cout<<ret<<endl;

    return 0;
}

運(yùn)行程序：

從上面的數(shù)組可以判斷結(jié)果分別為true，false，false。

《完》

關(guān)于“c#如何實(shí)現(xiàn)棧的壓入、彈出序列”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。