栈中元素排序

我会带着你远行 2023-06-04 07:56 46阅读 0赞

题目描述：设计一个算法，将栈中的元素按升序排列。可另外借用一个栈来实现。

思路：从主栈中依次弹出栈顶元素压入辅助栈，每当将要压入的元素使得辅助栈中的元素不是升序排列，就将辅助栈里的元素重新压入原始栈，直到辅助栈里的元素都小于当前要压入的元素，然后再压入当前元素。

图解：假设当前主栈里的元素是\{0,5,6,4,2,3,1\}。过程图解如下：

（1）最开始时，将元素依次压入主栈中，此时辅助栈为空。

![20191007184349110.png][]

（2）将主栈栈顶元素1弹出并压如辅助栈中，此时主栈的栈顶元素变为3，辅助栈中有一个元素1。接着，将主栈中的栈顶元素3弹出并压入辅助栈中，此时主栈的栈顶元素为2，辅助栈中元素有1和3，其中3为栈顶元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70][]

（3）此时需要对主栈中的元素2进行排序，发现2小于辅助栈中的栈顶元素，如果直接压栈的话会导致辅助栈不再有序。那么此时我们需要先将主栈中的栈顶元素提取出来，称为当前元素，然后将辅助栈中比当前要压栈的元素大的元素弹出压入主栈中，直到辅助栈中的栈顶元素不再大于当前元素，即小于等于当前元素。之后再把当前元素压入辅助栈中。需要注意的是，从辅助栈弹出并压入主栈中的元素在当前元素压入辅助栈之后不需要从主栈中弹出并重新压入辅助栈。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1][]

（4）此时主栈的栈顶元素是之前从辅助栈中弹出的，接下来对其进行排序。发现此时3大于辅助栈的栈顶元素，即压入之后不会导致辅助栈的无序，所以可直接压入。接下来元素4和元素6也一样，依次从主栈中弹出并压入辅助栈中即可。之后，主栈中的元素有0和5，其中5为栈顶元素。辅助栈中的栈顶元素为6。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2][]

（5）接下来，对主栈的栈顶元素5进行排序。发现其比辅助栈的栈顶元素6小，直接压入便会导致辅助栈中元素失去以前的顺序而变得无序。所以与之前元素2的处理方法一样。先将主栈中的栈顶元素提取出来，记为当前元素，然后将辅助栈中栈顶元素6弹出并压入主栈中，然后将当前元素5压入辅助栈中作为栈顶元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 3][]

（6）然后直接将主栈栈顶元素6压入辅助栈中作为栈顶元素，规则同上。此时，主栈中只剩一个元素0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 4][]

（7）接下来处理主栈中的最后一个元素0，因为其小于辅助栈中的所有元素，所以需要将辅助栈中的元素依次弹出压入主栈中，然后将元素0压入辅助栈中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 5][]

（8）最后一步，将主栈中的元素依次弹出并压入辅助栈中，此时辅助栈中的元素按升序排列。主栈为空。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 6][]

相关代码如下：

//stack1为主栈，stack2为辅助栈
    stack<int> sort(stack<int> stack1)
    {
        stack<int> stack2;
        while (!stack1.empty())
        {
    	int temp = stack1.top();
    	stack1.pop();
    	//如果辅助栈不为空且当前元素比辅助栈栈顶元素小，则将辅助栈中元素弹出压入主栈中
    	while (!stack2.empty() && stack2.top() > temp)
    	{
    	    stack1.push(stack2.top());
    	    stack2.pop();
    	}
    	//如果辅助栈为空或者当前元素比辅助栈栈顶元素大，则将当前元素直接压入辅助栈中
    	stack2.push(temp);
        }
        return stack2;
    }

[20191007184349110.png]: /images/20230601/ae8ffc98e8a24a38bc96bcc508610494.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70]: /images/20230601/12cca91af9f6440e8e8d197f621bcde2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1]: /images/20230601/f1978a052c454786b912f631f18b23ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2]: /images/20230601/4a9f10b460b64482950aa8588c6c2b82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 3]: /images/20230601/ab8a75d6b0c94d0787471ebb4ebb16c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 4]: /images/20230601/b9812ab5d5aa4478aeba2bcde77bd840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 5]: /images/20230601/37b60e5e90a545669acdf230a35c39b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 6]: /images/20230601/031dc08ed19546cc8945fd4a326107cd.png