題目描述

請編寫一個程序，按升序?qū)＿M行排序（即最大元素位于棧頂），要求最多只能使用一個額外的棧存放臨時數(shù)據(jù)，但不得將元素復制到別的數(shù)據(jù)結(jié)構(gòu)中。

給定一個int[]?numbers(C++中為vector&ltint>)，其中第一個元素為棧頂，請返回排序后的棧。請注意這是一個棧，意味著排序過程中你只能訪問到第一個元素。

測試樣例： [1,2,3,4,5] 返回：[5,4,3,2,1]


學習總結(jié)：1.棧的使用判斷是否為空用empty（）函數(shù)
　　　　　2.棧和向量的轉(zhuǎn)換，棧只能訪問到棧頂元素。push有參數(shù)，pop無參數(shù)。
　　　　　3.雙棧排序的使用技巧，先比棧頂，一次排完后保持臨時棧底元素最小。
class TwoStacks { public:vector<int> twoStacksSort(vector<int> numbers) {// write code here//只用到一個棧來暫存中間變量，這個比較有難度stack<int> num;stack<int> temp;int val;//只能訪問棧頂元素，先進行入棧，通過逆序?qū)⑾蛄窟M行入棧，第一個元素為棧頂元素for(int i = numbers.size()-1; i >= 0 ; i--){num.push(numbers[i]);}val = num.top();temp.push(val);num.pop();while(!num.empty()) {if(num.top() < temp.top()) { //兩個棧頂比較，則進行壓臨時棧操作val = num.top();num.pop();while(!temp.empty() && temp.top() > val) { //大于比較值，則統(tǒng)統(tǒng)出臨時棧 num.push(temp.top());temp.pop();}temp.push(val); //比較值進行入臨時棧 }else { //棧的退回，大于臨時棧頂元素回臨時棧 temp.push(num.top());num.pop();}}//最后返回的向量形式，所以進行轉(zhuǎn)換for(int j = 0; j < numbers.size(); j++) {numbers[j] = temp.top();temp.pop();}return numbers; } };

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiaohaigege/p/5381563.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的3.6双栈排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。