查看匯總:2015軟件水平考試程序員精選題匯總
用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目:某隊(duì)列的聲明如下:
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)在隊(duì)列中有兩個(gè)棧。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了:棧是一種后入先出的數(shù)據(jù)容器,因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行;隊(duì)列是一種先入先出的數(shù)據(jù)容器,我們總是把新元素插入到隊(duì)列的尾部,而從隊(duì)列的頭部刪除元素。
我們通過一個(gè)具體的例子來分析往該隊(duì)列插入和刪除元素的過程。首先插入一個(gè)元素a,不妨把先它插入到m_stack1。這個(gè)時(shí)候m_stack1中的元素有{a},m_stack2為空。再插入兩個(gè)元素b和c,還是插入到m_stack1中,此時(shí)m_stack1中的元素有{a,b,c},m_stack2中仍然是空的。
這個(gè)時(shí)候我們?cè)囍鴱年?duì)列中刪除一個(gè)元素。按照隊(duì)列先入先出的規(guī)則,由于a比b、c先插入到隊(duì)列中,這次被刪除的元素應(yīng)該是a。元素a存儲(chǔ)在m_stack1中,但并不在棧頂上,因此不能直接進(jìn)行刪除。注意到m_stack2我們還一直沒有使用過,現(xiàn)在是讓m_stack2起作用的時(shí)候了。如果我們把m_stack1中的元素逐個(gè)pop出來并push進(jìn)入m_stack2,元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。因此經(jīng)過兩次pop和push之后,m_stack1為空,而m_stack2中的元素是{c,b,a}。這個(gè)時(shí)候就可以pop出m_stack2的棧頂a了。pop之后的m_stack1為空,而m_stack2的元素為{c,b},其中b在棧頂。
這個(gè)時(shí)候如果我們還想繼續(xù)刪除應(yīng)該怎么辦呢?在剩下的兩個(gè)元素中b和c,b比c先進(jìn)入隊(duì)列,因此b應(yīng)該先刪除。而此時(shí)b恰好又在棧頂上,因此可以直接pop出去。這次pop之后,m_stack1中仍然為空,而m_stack2為{c}。
從上面的分析我們可以總結(jié)出刪除一個(gè)元素的步驟:當(dāng)m_stack2中不為空時(shí),在m_stack2中的棧頂元素是最先進(jìn)入隊(duì)列的元素,可以pop出去。如果m_stack2為空時(shí),我們把m_stack1中的元素逐個(gè)pop出來并push進(jìn)入m_stack2。由于先進(jìn)入隊(duì)列的元素被壓到m_stack1的底端,經(jīng)過pop和push之后就處于m_stack2的頂端了,又可以直接pop出去。
接下來我們?cè)俨迦胍粋(gè)元素d。我們是不是還可以把它push進(jìn)m_stack1?這樣會(huì)不會(huì)有問題呢?我們說不會(huì)有問題。因?yàn)樵趧h除元素的時(shí)候,如果m_stack2中不為空,處于m_stack2中的棧頂元素是最先進(jìn)入隊(duì)列的,可以直接pop;如果m_stack2為空,我們把m_stack1中的元素pop出來并push進(jìn)入m_stack2。由于m_stack2中元素的順序和m_stack1相反,最先進(jìn)入隊(duì)列的元素還是處于m_stack2的棧頂,仍然可以直接pop。不會(huì)出現(xiàn)任何矛盾。
相關(guān)推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |