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

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

解題思路
棧（Stack）又叫堆棧，是一種特殊的“線性”數(shù)據(jù)結(jié)構(gòu)，它是在同一端進行插入和刪除數(shù)據(jù)的線性表。
棧是最基礎(chǔ)也是最常見的數(shù)據(jù)結(jié)構(gòu)之一。對于棧的操作如下圖所示：

基本了解了棧這種數(shù)據(jù)結(jié)構(gòu)之后，我們再來看如何解決這個題目。由于棧是先進后出的操作方式，而隊列是先進先出的操作方式，所以為了解決這個題，我們要引入2個棧。

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

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

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

        //當(dāng)前處于逆序狀態(tài)中，將其添加到正序隊列中
        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();
    }

全部解題代碼

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

    public void appendTail(int value) {//兩個都為空，所以添加的是第一個。或者目前正處于正序隊列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //當(dāng)前處于逆序狀態(tài)中，將其添加到正序隊列中
        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é)
該題目非常的簡單且很有意思，在網(wǎng)上看到有別的同學(xué)說Java實現(xiàn)的Stack棧比較占內(nèi)存，大家可以嘗試以下用隊列實現(xiàn)2個棧的方式來減少內(nèi)存的使用，如果對我的解題有任何問題歡迎各位大佬在評論區(qū)進行指點，如果你喜歡我的文章的話“一鍵三連”（點贊、評論、收藏）支持一下吧~

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

本文題目：【劍指Offer】9.《用兩個棧實現(xiàn)隊列》詳解-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/cshhoi.html