[CTCI]デュアルスタックソート
3359 ワード
ダブルスタックソート
タイトルの説明
スタックを昇順にソートするプログラムを作成してください(つまり、最大要素はスタックの上部にあります).追加のスタックを使用して一時データを格納することはできませんが、要素を別のデータ構造にコピーすることはできません.
int[]numbers(C++でvector)を指定します.最初の要素がスタックトップである場合は、ソートされたスタックを返します.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
テストサンプル:
タイトルの説明
スタックを昇順にソートするプログラムを作成してください(つまり、最大要素はスタックの上部にあります).追加のスタックを使用して一時データを格納することはできませんが、要素を別のデータ構造にコピーすることはできません.
int[]numbers(C++でvector
テストサンプル:
[1,2,3,4,5] ：[5,4,3,2,1]
1 class TwoStacks {
2 public:
3 vector<int> twoStacksSort(vector<int> numbers) {
4 // write code here
5 stack<int> stk;
6 int top = 0, tmp;
7 while (top != numbers.size()) {
8 tmp = numbers[top++];
9 while (!stk.empty() && stk.top() > tmp) {
10 numbers[--top] = stk.top();
11 stk.pop();
12 }
13 stk.push(tmp);
14 }
15 top = 0;
16 while (!stk.empty()) {
17 numbers[top++] = stk.top();
18 stk.pop();
19 }
20 return numbers;
21 }
22 };