查看匯總：2015軟件水平考試程序員精選題匯總

　　用兩個棧實現(xiàn)隊列

　　題目：某隊列的聲明如下：

　　template class CQueue

　　{

　　public:

　　CQueue() {}

　　~CQueue() {}

　　void appendTail(const T& node); // append a element to tail

　　void deleteHead(); // remove a element from head

　　private:

　　T>m_stack1;

　　T>m_stack2;

　　};

　　分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊列中有兩個棧。因此這道題實質(zhì)上是要求我們用兩個棧來實現(xiàn)一個隊列。相信大家對棧和隊列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對隊列進行的插入和刪除操作都是在棧頂上進行;隊列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。

　　我們通過一個具體的例子來分析往該隊列插入和刪除元素的過程。首先插入一個元素a，不妨把先它插入到m_stack1。這個時候m_stack1中的元素有{a}，m_stack2為空。再插入兩個元素b和c，還是插入到m_stack1中，此時m_stack1中的元素有{a,b,c}，m_stack2中仍然是空的。

　　這個時候我們試著從隊列中刪除一個元素。按照隊列先入先出的規(guī)則，由于a比b、c先插入到隊列中，這次被刪除的元素應該是a。元素a存儲在m_stack1中，但并不在棧頂上，因此不能直接進行刪除。注意到m_stack2我們還一直沒有使用過，現(xiàn)在是讓m_stack2起作用的時候了。如果我們把m_stack1中的元素逐個pop出來并push進入m_stack2，元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。因此經(jīng)過兩次pop和push之后，m_stack1為空，而m_stack2中的元素是{c,b,a}。這個時候就可以pop出m_stack2的棧頂a了。pop之后的m_stack1為空，而m_stack2的元素為{c,b}，其中b在棧頂。

　　這個時候如果我們還想繼續(xù)刪除應該怎么辦呢?在剩下的兩個元素中b和c，b比c先進入隊列，因此b應該先刪除。而此時b恰好又在棧頂上，因此可以直接pop出去。這次pop之后，m_stack1中仍然為空，而m_stack2為{c}。

　　從上面的分析我們可以總結(jié)出刪除一個元素的步驟：當m_stack2中不為空時，在m_stack2中的棧頂元素是最先進入隊列的元素，可以pop出去。如果m_stack2為空時，我們把m_stack1中的元素逐個pop出來并push進入m_stack2。由于先進入隊列的元素被壓到m_stack1的底端，經(jīng)過pop和push之后就處于m_stack2的頂端了，又可以直接pop出去。

　　接下來我們再插入一個元素d。我們是不是還可以把它push進m_stack1?這樣會不會有問題呢?我們說不會有問題。因為在刪除元素的時候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進入隊列的，可以直接pop;如果m_stack2為空，我們把m_stack1中的元素pop出來并push進入m_stack2。由于m_stack2中元素的順序和m_stack1相反，最先進入隊列的元素還是處于m_stack2的棧頂，仍然可以直接pop。不會出現(xiàn)任何矛盾。

　　相關推薦：

　　2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習題匯總

　　2015軟件水平考試《程序員》知識點總結(jié)匯總