您好,登錄后才能下訂單哦!
小編給大家分享一下C++如何使用一個(gè)棧實(shí)現(xiàn)另一個(gè)棧的排序算法,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
題目:
一個(gè)棧中元素類型為整型,現(xiàn)在想將該棧從頂?shù)降装磸男〉酱蟮捻樞蚺判?,只許申請(qǐng)一個(gè)輔助棧。
除此之外,可以申請(qǐng)新的變量,但不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)。如何完成排序?
算法C++代碼:
class Solution { public: //借助一個(gè)臨時(shí)棧排序源棧 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp = new stack<int>; while (!s.empty()) { int cur = s.top(); s.pop(); //當(dāng)源棧中棧頂元素大于臨時(shí)棧棧頂元素時(shí),將臨時(shí)棧中棧頂元素放回源棧 //保證臨時(shí)棧中元素自底向上從大到小 while (!sTemp->empty() && cur > sTemp->top()) { int temp = sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //將臨時(shí)棧中的元素從棧頂依次放入源棧中 while (!sTemp->empty()) { int x = sTemp->top(); sTemp->pop(); s.push(x); } } };
測(cè)試用例程序:
#include <iostream> #include <stack> using namespace std; class Solution { public: //借助一個(gè)臨時(shí)棧排序源棧 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp = new stack<int>; while (!s.empty()) { int cur = s.top(); s.pop(); //當(dāng)源棧中棧頂元素大于臨時(shí)棧棧頂元素時(shí),將臨時(shí)棧中棧頂元素放回源棧 //保證臨時(shí)棧中元素自底向上從大到小 while (!sTemp->empty() && cur > sTemp->top()) { int temp = sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //將臨時(shí)棧中的元素從棧頂依次放入源棧中 while (!sTemp->empty()) { int x = sTemp->top(); sTemp->pop(); s.push(x); } } }; void printStack(stack<int> s) { while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; } int main() { stack<int>* s = new stack<int>; s->push(5); s->push(7); s->push(6); s->push(8); s->push(4); s->push(9); s->push(2); cout << "排序前的棧:" << endl; printStack(*s); Solution::sortStackByStack(*s); cout << "排序后的棧:" << endl; printStack(*s); system("pasue"); }
運(yùn)行結(jié)果:
排序前的棧: 2 9 4 8 6 7 5 排序后的棧: 9 8 7 6 5 4 2
以上是“C++如何使用一個(gè)棧實(shí)現(xiàn)另一個(gè)棧的排序算法”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。