careercup-スタックとキュー3.6

2891 ワード

3.6スタックを昇順にソートするプログラムを作成します(つまり、最大要素はスタックの上部にあります).一時的なデータを格納するには、追加のスタックしか使用できませんが、配列などの他のデータ構造に要素をコピーしてはいけません.このスタックは、push、pop、peek、isEmptyの操作をサポートします.
 
に答える
 
追加のスタックを使用して、挿入ソートをシミュレートします.元のスタックのデータを順次スタックから出て、追加スタックのスタックトップ要素と比較し、追加スタックが空の場合、直接データをスタックに圧縮します.そうでなければ、追加スタックのスタックトップ要素が元のスタックからポップアップされた要素より小さい場合、追加スタックのスタックトップ要素が元のスタックに押し込まれます.このようにして、追加スタックが空またはスタックトップ要素が要素より大きいまで検索すると、要素は追加スタックに押し込まれます.
C++実装コード:
#include<iostream>

#include<stack>

using namespace std;



void stackSort(stack<int> &st)

{

    stack<int> t;

    while(!st.empty())

    {

        int data=st.top();

        st.pop();

        while(!t.empty()&&t.top()<data)

        {

            st.push(t.top());

            t.pop();

        }

        t.push(data);

    }

    while(!t.empty())

    {

        st.push(t.top());

        t.pop();

    }

}



int main()

{

    stack<int> st;

    int arr[10]={2,4,6,1,3,5,7,8,9,0};

    for(int i=0;i<10;i++)

        st.push(arr[i]);

    stackSort(st);

    while(!st.empty())

    {

        cout<<st.top()<<" ";

        st.pop();

    }

    cout<<endl;

}