生活随笔
收集整理的這篇文章主要介紹了
程序员面试金典 - 面试题 03.05. 栈排序（两栈）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1. 題目
棧排序。 編寫程序，對棧進(jìn)行排序使最小元素位于棧頂。
最多只能使用一個其他的臨時棧存放數(shù)據(jù)，但不得將元素復(fù)制到別的數(shù)據(jù)結(jié)構(gòu)（如數(shù)組）中。
該棧支持如下操作：push、pop、peek 和 isEmpty。當(dāng)棧為空時，peek 返回 -1。
示例
1:輸入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]輸出：
[null
,null
,null
,1,null
,2]示例
2:輸入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]輸出：
[null
,null
,null
,null
,null
,true]
說明
:
棧中的元素數(shù)目在
[0, 5000]范圍內(nèi)。
2. 解題
- 用兩個棧，來回倒數(shù)據(jù)，保證其中一個為空
- 倒的過程中找到最小的放在非空的棧的頂端
class SortedStack {stack
<int> s
;stack
<int> temp
;int nextMin
;
public:SortedStack() {}void push(int val
) {if(isEmpty())s
.push(val
);else if(temp
.empty()){if(s
.top() < val
)swap(val
,s
.top());s
.push(val
);}else {if(temp
.top() < val
)swap(val
,temp
.top());temp
.push(val
);}}void pop() {if(isEmpty())return;if(temp
.empty()){s
.pop();while(!s
.empty()){nextMin
= s
.top();s
.pop();if(!temp
.empty() && nextMin
> temp
.top())swap(nextMin
, temp
.top());temp
.push(nextMin
);}}else {temp
.pop();while(!temp
.empty()){nextMin
= temp
.top();temp
.pop();if(!s
.empty() && nextMin
> s
.top())swap(nextMin
, s
.top());s
.push(nextMin
);}}}int peek() {if(isEmpty())return -1;if(temp
.empty())return s
.top();else return temp
.top();}bool isEmpty() {return s
.empty()&&temp
.empty();}
};
總結(jié)
以上是生活随笔為你收集整理的程序员面试金典 - 面试题 03.05. 栈排序（两栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
