CodeUp 100000606 问题A数字交换（使用队列实现）

题目描述

输入10个整数，将其中最小的数与第一个数对换，把最大的数与最后一个数对换。写三个函数； ①输入10个数；②进行处理；③输出10个数。

输入

10个整数

输出

整理后的十个数，每个数后跟一个空格（注意最后一个数后也有空格）

样例输入

2 1 3 4 5 6 7 8 10 9 

样例输出

1 2 3 4 5 6 7 8 9 10 

思路

1. 找到最大值和最小值以及最大值最小值位置，新队列第一个位置用最小值代替，最后一个位置用最大值代替，最小值位置用原队头代替，最大值位置用原队尾代替。
   一个坑：如果最大值在队头，把最小值交换到队头时会改变最大值位置，因此后续需要用原队尾元素代替最小值位置，与原策略正好相反。反之，最小值在队尾时需要用原队头元素代替最大值位置。最大值在队头同时最小值在队尾时，无需特殊处理。
2. 也可不要第二个队列直接输出结果。

Code

C++

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int tmp, min = 10000000, max = -10000000, min_idx = 0, max_idx = 0;
    queue<int> q, result;
    // 读入数据并标记最大值，最小值，最大值位置，最小值位置。
    for ( int i=0; i<10; i++ ) {
        cin >> tmp;
        q.push(tmp);
        if ( tmp < min ) {
            min = tmp;
            min_idx = i;
        }
        if ( tmp > max ) {
            max = tmp;
            max_idx = i;
        }
    }
    // 保留原队列的头尾数据。
    int old_head = q.front(), old_back = q.back(), i = 0;
    // 按顺序输出旧队列到新队列，把最小值和最大值放在新队列头尾。原来最小值的位置用原队头数据代替，原来最大值位置用原队尾数据代替。
    // 如果最大值在第一位，交换以后原来的队尾会放在原最小值所在处，所以原队头队尾需要交换位置。
    // 如果最小值在最后一位，交换以后原来的队头会放在原最大值所在处，所以原队头队尾需要交换位置。
    // 如果最大值在队头且最小值在队尾，则不需要交换原队头队尾数据。这里交换两次还原。
    if ( max_idx == 0 ) swap(old_head, old_back);
    if ( min_idx == 9 ) swap(old_head, old_back);
    while ( !q.empty() ) {
        if ( i == 0 ) result.push(min);
        else if ( i == 9 ) result.push(max);
        else if ( i == min_idx ) result.push(old_head);
        else if ( i == max_idx ) result.push(old_back);
        else result.push(q.front());
        q.pop();
        i++;
    }
    // 按格式输出。
    while ( !result.empty() ) {
        cout << result.front() << ' ';
        result.pop();
    }
    cout << endl;
    return 0;
}