您好,登錄后才能下訂單哦!
隊列是先進先出,而棧是先進后出;
考慮到我們?nèi)m斣氐谋憷?,我們在實現(xiàn)時使得棧頂?shù)扔陉犃蓄^;
由于棧的pop彈出棧頂元素,而隊列的pop也是彈出棧頂元素,所以我們需要特別處理的是插入操作。
由于往棧中添加元素相當(dāng)于往隊列頭添加元素,因此我們需要在兩個隊列中進行元素的轉(zhuǎn)移,比較簡單的實現(xiàn)是:
1.q1和q2在任一時刻至少有一個為空,即如果有元素,所以元素只在同一個隊列中。
2.當(dāng)有元素需要插入時,將插入的元素插入到空的隊列中,并將另一非空隊列的元素轉(zhuǎn)移到該隊列中,于是插入的元素添加到了隊列頭中。
(當(dāng)然,你可以換一種思路,把隊列尾與棧頂對應(yīng)起來,這樣子需要特別處理的是pop操作以及top操作,相比起來,本文的做法更加簡便,因為只需要對插入操作特別處理)
具體C++代碼實現(xiàn)如下:
class Stack {public: // Push element x onto stack. void push(int x) { if (!q1.empty()) { q2.push(x); while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } } else { q1.push(x); while (!q2.empty()) { q1.push(q2.front()); q2.pop(); } } } // Removes the element on top of the stack. void pop() { if (q1.empty()&&q2.empty()) throw new exception("stack is empty"); else if (!q1.empty()) q1.pop(); else q2.pop(); } // Get the top element. int top() { if (!q1.empty()) return q1.front(); else return q2.front(); } // Return whether the stack is empty. bool empty() { return (q1.empty()&&q2.empty()); }private: queue<int> q1, q2; };
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。