題目：請(qǐng)編寫(xiě)一個(gè)程序，按升序?qū)＿M(jìn)行排序，要求最多只能使用一個(gè)額外的棧存放臨時(shí)數(shù)據(jù)，但不得將元素復(fù)制到別的數(shù)據(jù)結(jié)構(gòu)中。
思路：首先申請(qǐng)一個(gè)棧sta來(lái)存放數(shù)據(jù)棧，再申請(qǐng)一個(gè)輔助棧help來(lái)存放臨時(shí)數(shù)據(jù)，然后比較sta彈出的棧頂?shù)闹祌es與help棧頂元素的大小。
當(dāng)sta棧不為空時(shí)：
1、如果help.empty()或者res<=help.top()，那么就把res的值壓入help棧中；
2、如果help不為空并且res>help.top()，那么就把help中棧頂?shù)闹祻棾霾喝雜ta棧，最后把res的值壓入help棧中。
具體可看如下過(guò)程圖：
示例代碼：
#include<iostream>#include<string>#include<stack>//pop,top,push#include<vector>using namespace std;class TwoStacks {public: vector<int> twoStacksSort(vector<int> numbers) { stack<int> sta; for(vector<int>::reverse_iterator riter=numbers.rbegin();riter!=numbers.rend();riter++) sta.push(*riter); StackSort(sta); vector<int> res; while(!sta.empty()) { res.push_back(sta.top()); sta.pop(); } return res; } void StackSort(stack<int> &sta) { stack<int> help; while(!sta.empty()) { int res=sta.top(); sta.pop(); if(help.empty()||res<=help.top()) help.push(res); else { while(!help.empty()&&res>help.top()) { sta.push(help.top()); help.pop(); } help.push(res); } } while(!help.empty()) { sta.push(help.top()); help.pop(); } }};int main(){ int a[5]={1,2,3,4,5}; TwoStacks A; vector<int> arr(a,a+5),res; res=A.twoStacksSort(arr); for(vector<int>::iterator iter=res.begin();iter!=res.end();iter++) cout<<*iter<<" "; return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
