C++使用一个栈实现另一个栈的排序算法示例

C++使用一个栈实现另一个栈的排序算法

本文将介绍如何使用一个栈（以下称为stack1）将另一个未排序的栈（以下称为stack2）进行排序，排序结果存放在stack2中。

实现思路

我们可以通过stack1不断从stack2中弹出元素，将弹出的元素插入到正确的位置，实现栈的排序。

具体步骤如下：

1. 创建一个临时变量temp，用于存储stack1中弹出的元素。

2. 如果stack2为空或者temp小于等于stack2.top()，则将temp直接压入stack2中。

3. 如果stack2.top()小于temp，则弹出stack2.top()，将其压入stack1中，重复步骤2，直到stack2为空或者temp小于等于stack2.top()为止，然后将temp压入stack2中。

4. 重复步骤1-3，直到stack1为空。

根据上述思路，我们可以写出以下排序算法：

void sort_stack(stack<int>& s)
{
    stack<int> tmp;
    while (!s.empty())
    {
        int cur_val = s.top();
        s.pop();

        while (!tmp.empty() && tmp.top() > cur_val)
        {
            s.push(tmp.top());
            tmp.pop();
        }
        tmp.push(cur_val);
    }
    s = tmp;
}

示例说明

示例1

假设stack2中的元素为[5, 3, 2, 8, 6]，我们可以将其排序，得到[2, 3, 5, 6, 8]。

stack<int> s{5, 3, 2, 8, 6};
sort_stack(s); // s中存放的结果为[2, 3, 5, 6, 8]。

示例2

假设stack2中的元素为[6, 6, 3, 4, 5, 5]，我们可以将其排序，得到[3, 4, 5, 5, 6, 6]。

stack<int> s{6, 6, 3, 4, 5, 5};
sort_stack(s); // s中存放的结果为[3, 4, 5, 5, 6, 6]。

注意事项

• 该算法时间复杂度为O(n^2)，仅适用于小数据量的排序。
• 本文示例中采用的是从栈顶开始排序，也可以从栈底开始排序，具体实现思路略有不同。