プログラマー面接金典-3.6ダブルスタックソート
1875 ワード
一、テーマの説明
スタックを昇順にソートするプログラムを作成してください(つまり、最大要素はスタックの上部にあります).追加のスタックを使用して一時データを格納することはできませんが、要素を別のデータ構造にコピーすることはできません.
int[]numbers(C++でvector<int>)が与えられ、最初の要素がスタックトップである場合は、ソートされたスタックに戻ります.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
テストサンプル:
二、テーマの考え方
この考え方はフォーラムの中のある大神のやり方を参考にして、2つのスタック、1つの初期スタック、1つのソートスタックを作成します.まずnumbers内の要素をすべて初期スタックに追加し、ポップアップ初期スタックのスタックトップ要素を次のルールでソートスタックに追加します.ターゲットは、スタックの下部からスタックの上部への要素の順序付けを生成することです.
1.ソートスタックが空の場合、またはソートスタックのトップ要素が初期スタックのトップ要素より小さい場合、初期スタックの要素をソートスタックに直接追加できます.
2.並べ替えスタックのスタックトップ要素が初期スタックトップ要素より大きい場合、初期スタックトップ要素は変数popintとしてポップアップされ、並べ替えスタックのpopintより大きい要素を初期スタックに追加し、popinを並べ替えスタックに押し込み、最後に初期スタックに押し込んだ要素を並べ替えスタックに押し込む.
三、コード
スタックを昇順にソートするプログラムを作成してください(つまり、最大要素はスタックの上部にあります).追加のスタックを使用して一時データを格納することはできませんが、要素を別のデータ構造にコピーすることはできません.
int[]numbers(C++でvector<int>)が与えられ、最初の要素がスタックトップである場合は、ソートされたスタックに戻ります.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
テストサンプル:
[1,2,3,4,5]
:[5,4,3,2,1]
二、テーマの考え方
この考え方はフォーラムの中のある大神のやり方を参考にして、2つのスタック、1つの初期スタック、1つのソートスタックを作成します.まずnumbers内の要素をすべて初期スタックに追加し、ポップアップ初期スタックのスタックトップ要素を次のルールでソートスタックに追加します.ターゲットは、スタックの下部からスタックの上部への要素の順序付けを生成することです.
1.ソートスタックが空の場合、またはソートスタックのトップ要素が初期スタックのトップ要素より小さい場合、初期スタックの要素をソートスタックに直接追加できます.
2.並べ替えスタックのスタックトップ要素が初期スタックトップ要素より大きい場合、初期スタックトップ要素は変数popintとしてポップアップされ、並べ替えスタックのpopintより大きい要素を初期スタックに追加し、popinを並べ替えスタックに押し込み、最後に初期スタックに押し込んだ要素を並べ替えスタックに押し込む.
三、コード
import java.util.*;
public class TwoStacks {
public ArrayList twoStacksSort(int[] numbers) {
// write code here
Stack bufer=new Stack();
Stack sorted=new Stack();
ArrayList result=new ArrayList();
for(int i=0;i<=numbers.length-1;i++)
bufer.push(numbers[i]);
//sorted.push(numbers[numbers.length-1]);
int popint=0;
while(!bufer.empty()){
if(sorted.empty()||sorted.peek()<=bufer.peek())
sorted.push(bufer.pop());
else{
int count=0;
popint=bufer.pop();
while(!sorted.empty() && sorted.peek()>popint){
bufer.push(sorted.pop());
count++;
}
sorted.push(popint);
for(int i=0;i