完美世界辰东,小说网

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案

【劍指Offer】9.《用兩個(gè)棧實(shí)現(xiàn)隊(duì)列》詳解-創(chuàng)新互聯(lián)

題目描述
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒(méi)有元素，deleteHead 操作返回 -1 )

創(chuàng)新互聯(lián)長(zhǎng)期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為雙湖企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、成都做網(wǎng)站，雙湖網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

解題思路
棧（Stack）又叫堆棧，是一種特殊的“線性”數(shù)據(jù)結(jié)構(gòu)，它是在同一端進(jìn)行插入和刪除數(shù)據(jù)的線性表。
棧是最基礎(chǔ)也是最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)之一。對(duì)于棧的操作如下圖所示：
在這里插入圖片描述
基本了解了棧這種數(shù)據(jù)結(jié)構(gòu)之后，我們?cè)賮?lái)看如何解決這個(gè)題目。由于棧是先進(jìn)后出的操作方式，而隊(duì)列是先進(jìn)先出的操作方式，所以為了解決這個(gè)題，我們要引入2個(gè)棧。

//正序
    Stacks1;
    //逆序
    Stacks2;

分別為正序棧和逆序棧。
當(dāng)需要對(duì)隊(duì)列進(jìn)行尾部添加時(shí)，需要考慮以下幾種情況：
1.正序棧s1與逆序棧s2都為空，則當(dāng)前隊(duì)列為空
2.正序棧s1為空但逆序棧s2不為空時(shí)，則當(dāng)前為逆序存放于逆序棧s2中，s2中當(dāng)前的操作對(duì)象是隊(duì)列頭部，我們需要將逆序棧s2中的數(shù)據(jù)全部pop進(jìn)正序棧s1中實(shí)現(xiàn)reverse反轉(zhuǎn)，反轉(zhuǎn)之后s1中操作對(duì)象就是當(dāng)前隊(duì)列的尾部以實(shí)現(xiàn)尾部添加數(shù)據(jù)

public void appendTail(int value) {//兩個(gè)都為空，所以添加的是第一個(gè)?；蛘吣壳罢幱谡蜿?duì)列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //當(dāng)前處于逆序狀態(tài)中，將其添加到正序隊(duì)列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

對(duì)隊(duì)列進(jìn)行刪除也是同理，大家可以看看代碼理解一下：

public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

全部解題代碼

class CQueue{//正序
    Stacks1;
    //逆序
    Stacks2;
    public CQueue() {s1=new Stack<>();
        s2=new Stack<>();
    }

    public void appendTail(int value) {//兩個(gè)都為空，所以添加的是第一個(gè)?；蛘吣壳罢幱谡蜿?duì)列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //當(dāng)前處于逆序狀態(tài)中，將其添加到正序隊(duì)列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

    public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}

總結(jié)
該題目非常的簡(jiǎn)單且很有意思，在網(wǎng)上看到有別的同學(xué)說(shuō)Java實(shí)現(xiàn)的Stack棧比較占內(nèi)存，大家可以嘗試以下用隊(duì)列實(shí)現(xiàn)2個(gè)棧的方式來(lái)減少內(nèi)存的使用，如果對(duì)我的解題有任何問(wèn)題歡迎各位大佬在評(píng)論區(qū)進(jìn)行指點(diǎn)，如果你喜歡我的文章的話“一鍵三連”（點(diǎn)贊、評(píng)論、收藏）支持一下吧~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)題目：【劍指Offer】9.《用兩個(gè)棧實(shí)現(xiàn)隊(duì)列》詳解-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://fisionsoft.com.cn/article/cshhoi.html

新聞中心

其他資訊