棧與進(jìn)棧出棧

網(wǎng)站建設(shè)公司,為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁(yè)設(shè)計(jì)及定制網(wǎng)站建設(shè)服務(wù),專(zhuān)注于企業(yè)網(wǎng)站設(shè)計(jì),高端網(wǎng)頁(yè)制作,對(duì)成都酒店設(shè)計(jì)等多個(gè)行業(yè)擁有豐富的網(wǎng)站建設(shè)經(jīng)驗(yàn)的網(wǎng)站建設(shè)公司。專(zhuān)業(yè)網(wǎng)站設(shè)計(jì),網(wǎng)站優(yōu)化推廣哪家好,專(zhuān)業(yè)成都網(wǎng)站營(yíng)銷(xiāo)優(yōu)化,H5建站,響應(yīng)式網(wǎng)站。

---

棧：是限定在棧表尾進(jìn)行插入或刪除的線性表，又稱(chēng)為后進(jìn)先出（LIFO）的線性表，這個(gè)特點(diǎn)可以形象的表示為……（鐵路調(diào)度站）

只要保證每次在棧頂操作，同一進(jìn)棧順序可以有不同的出棧順序，以下是部分出棧順序 

34521   25431  14532 32145    43215

---

那么究竟怎樣驗(yàn)證一個(gè)出棧序列與一個(gè)入棧序列匹配？

思路：將進(jìn)棧和出棧序列分別存在數(shù)組里，然后再創(chuàng)建一個(gè)輔助棧，把輸入序列中的元素依次壓入棧中，并按照出棧序列依次彈出。

將進(jìn)棧和出棧序列存在兩個(gè)數(shù)組里，然后再創(chuàng)建一個(gè)輔助棧，把輸入序列中的元素依次壓入棧中，并按照出棧序列依次彈出。

方法：以彈出序列4,5,3,2,1為例，第一個(gè)希望被彈出的數(shù)字是4，因此需要將4先壓入棧中，而壓入棧中的序列由進(jìn)棧序列決定，也就是在4進(jìn)棧之前保證1,2,3都在棧里面。這個(gè)時(shí)候棧中包含4個(gè)數(shù)字，分別是1,2,3,4，其中4位于棧頂，正好對(duì)應(yīng)出棧數(shù)組的第一個(gè)，彈出棧頂元素4，接下來(lái)希望彈出的元素是5，而5不在棧中，因此需要將進(jìn)棧序列4之后的元素壓進(jìn)去，這個(gè)時(shí)候5位于棧頂，就可以彈出來(lái)了，接下來(lái)希望被彈出的是3,2,1，在每次操作之前他們都位于棧頂，故直接彈出即可。

代碼：

#include<iostream>
#include<stack>
using namespace std;
bool Check_Push_Pop(int* pPush,int* pPop,int length)
{
    if(length<=0 ||  pPush == NULL || pPop == NULL)
    {
        return false;
    }
    int in = 0;
    int out = 0;
    stack<int> s;
    //s.push(pPush[0]);
    int index = 0;  //壓入元素的個(gè)數(shù)
    for(out = 0;out < length; out++)               //(1)for循環(huán)控制什么
    {
        for(in = index;in <=length; in++)  //pPush[1,2,3,4,5]   pPop[4,5,3,2,1]                                         
        {
             if((s.empty())||s.top()!=pPop[out])  //(2)為什么要進(jìn)行判空
             {
                 if(in == length)                 //(3)if檢測(cè)的是什么
                 {                       
                    return false;
                 }
                 s.push(pPush[in]);
                 ++index;
             }
             else
             {
                s.pop();
                break;                        //跳出這層for循環(huán)，使它遍歷下一個(gè)出棧元素
             }
        }
    }
    if(s.empty() && in == length && out==length)
        return true;
    else
        return false;
}
void Test1()
{
    int Push[5] = {1,2,3,4,5};
    int Pop[5] = {4,5,3,2,1};
    if(Check_Push_Pop(Push,Pop,5))
    {
        cout<<"輸入與輸出匹配"<<endl;
    }
    else
    {
        cout<<"輸入與輸出不匹配"<<endl;
    }
}
void Test2()
{
    int Push[5] = {1,2,3,4,5};
    int Pop[5] = {4,5,3,1,2};
    if(Check_Push_Pop(Push,Pop,5))
    {
        cout<<"輸入與輸出匹配"<<endl;
    }
    else
    {
        cout<<"輸入與輸出不匹配"<<endl;
    }
}
int main()
{
    Test1();
    //Test2();
    system("pause");
    return 0;
}

總結(jié)：

如果下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字，那么直接彈出。如果下一個(gè)彈出的數(shù)字不在棧頂，我們把進(jìn)棧序列中還沒(méi)有入棧的數(shù)字壓入輔助棧，直到把下一個(gè)需要彈出的數(shù)字壓入棧為止。如果所有的數(shù)字都?jí)喝肓藯Ｈ哉业较乱粋€(gè)彈出的數(shù)字，那么該序列不可能是一個(gè)彈出的序列。

對(duì)于入棧序列:1 2…i…j…k…n，那么它的出棧序列中不能有k…j…i這樣的序列子集。即如果入棧序列為ABC，則出棧序列不可以是CAB。

例題：

某個(gè)棧的入隊(duì)序列為A,B,C,D,E，則可能的出棧序列為（）

A . ADBEC(DBC)         B. EBCAD  (EBC)

C. BCDEA                   D.  EABCD（EAB）

用上述規(guī)律可以得出選C

當(dāng)前題目：進(jìn)棧出棧的合法性檢查
新聞來(lái)源：http://www.rwnh.cn/article2/pgcjic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、域名注冊(cè)、自適應(yīng)網(wǎng)站、定制開(kāi)發(fā)、軟件開(kāi)發(fā)、外貿(mào)建站

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)