用一个栈实现另一个栈的排序

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i;
    int n,x;
    stack<int> s,help;
    cin>>n;
    vector<int> arr(n,0);
    for(i=0;i<n;i++)
    {
        cin>>x;
        arr.at(i)=x;
    }
    for(i=n-1;i>=0;i--)
        s.push(arr.at(i));
    while(!s.empty())
    {
        int temp=s.top();
        s.pop();
        while(!help.empty()&&help.top()>temp)
        //这里一开始第二条件使用help.top()>=temp,结果
        //超时严重，应该是测试数据有极端测试数据，导致程序
        //交换过多导致的
        {
            s.push(help.top());
            help.pop();
        }
        help.push(temp);
    }
    while(!help.empty())
    {
        if(help.size()==1) cout<<help.top();
        else cout<<help.top()<<" ";
        help.pop();
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        br.readLine();
        String[] secondLine = br.readLine().split(" ");
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> help = new LinkedList<>();
        for (String s : secondLine) {
            stack.push(Integer.parseInt(s));
        }
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && cur > help.peek()) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pop());
            if (!stack.isEmpty()) {
                res.append(" ");
            }
        }
        System.out.println(res);
    }
}

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            while (!help.isEmpty() && help.peek() > temp) {
                stack.push(help.pop());
            }
            help.push(temp);
        }
        while (!help.isEmpty()) {
            int temp = help.pop();
            stack.push(temp);
            System.out.print(temp + " ");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();
        while (n-- > 0) {
            stack.push(sc.nextInt());
        }
        sortStackByStack(stack);
    }

}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num.begin(),num.end(),greater<int>());
    for(int i=0;i<n;i++)
        cout<<num[i]<<" ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<int> S1, S2;
    int n, x, t;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        S1.push(x);
    }
    while(!S1.empty()){
        x = S1.top();
        S1.pop();
        if(S2.empty())
            S2.push(x);
        else{
            t = S2.top();
            while(!S2.empty() && t>x){
                S2.pop();
                S1.push(t);
                t = S2.top();
            }
            S2.push(x);
        }
    }
    while(!S2.empty()){
        cout<<S2.top()<<" ";
        S2.pop();
    }
    return 0;
}

package main

import (
	"fmt"
)

func main() {
	num := 0
	fmt.Scan(&num)

	s := Stack{}

	for i := 0; i < num; i++ {
		v := 0
		fmt.Scan(&v)
		s.Push(v)
	}

	sortStack(&s)

	for !s.IsEmpty() {
		fmt.Print(s.Pop())
		fmt.Print(" ")
	}

	fmt.Println("")
}

func sortStack(s *Stack) {
	t := Stack{}

	for !s.IsEmpty() {
		top := s.Pop()

		for !t.IsEmpty() && top > t.Top() {
			s.Push(t.Pop())
		}

		t.Push(top)
	}

	for !t.IsEmpty() {
		s.Push(t.Pop())
	}
}

type Stack struct {
	data []int
}

func (s *Stack) Push(v int) {
	s.data = append(s.data, v)
}

func (s *Stack) Pop() int {
	top := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return top
}

func (s *Stack) IsEmpty() bool {
	return len(s.data) == 0
}

func (s *Stack) Top() int {
	return s.data[len(s.data)-1]
}

import java.util.*;
public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        Stack<Integer> stackA = new Stack<Integer>();
        Stack<Integer> stackB = new Stack<Integer>();
        while(sc.hasNextInt()){
            stackA.push(sc.nextInt());
        }
        while(!stackA.isEmpty()){
            int temp=stackA.pop();
            while( !stackB.isEmpty() && stackB.peek()>temp){
                stackA.push(stackB.pop());
            }
            stackB.push(temp);
        }
        while(!stackB.isEmpty()){
            System.out.print(stackB.pop()+" ");
        }
    }
}

# 输入的元素个数
n = int(input())
# 用列表模仿栈
stack = []
number = input().split()
number.reverse()
for i in range(len(number)):
    stack.append(int(number[i]))
# 辅助的栈
help = []
while len(stack) != 0:
    a = stack.pop()
    while len(help) != 0 and help[-1] < a:
        stack.append(help.pop())
    help.append(a)
while len(help) != 0:
    stack.append(help.pop())
# 输出栈顶到栈底
for i in range(len(stack)):
    print(stack.pop(), end=' ')

十一点吃个🍎 👉🏻map竟然忘记返值

let line=readline()
let stack=[],help=[]
while(line=readline()){
    stack=line.split(' ')

   stack= stack.map(item=>parseInt(item))
//     console.log(stack)
    while(stack.length){
        let cur=stack.pop()
        if(help.length==0||help[help.length-1]<cur){
            help.push(cur)
        }else{
            while(help.length){
                var helpcur=help[help.length-1]
                if(helpcur>cur){
                    stack.push(help.pop())
                }else break                   
            }
            help.push(cur)
        }
    }
    console.log(help.reverse().join(' '))
}

解题思路：
遍历给定的栈，将当前的栈中的元素压入辅助栈中，当压入辅助栈的序列不是递增序列时，就把辅助栈中的元素重新压入原来的栈，直到辅助栈的序列为递归序列。

/*
 * @Description: 用一个栈实现另一个栈的排序
 * @Author: 
 * @Date: 2020-10-27 16:03:00
 * @LastEditTime: 2020-10-27 16:27:22
 * @LastEditors: Please set LastEditors
 */
#include<iostream>
#include<stack>
using namespace std;

int main(){

    int N, num;
    cin >> N;
    stack<int> s1; //表示第一个栈
    stack<int> s2; //表示第二个栈
    for(int i = 0;i < N;i++){
        cin >> num;
        s1.push(num);
    }
    while(!s1.empty()){
        s2.push(s1.top());
        s1.pop();
    }
    //此时s2中的从栈顶到栈底的元素与输入的元素一致
    //下面为用s1将s2进行排序
    while(!s2.empty()){
        int temp = s2.top();
        s2.pop();
        while(!s1.empty() && temp < s1.top()){
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(temp);
    }
    //输出s1
    while(!s1.empty()){
        cout << s1.top() << " ";
        s1.pop();
    }
    //system("pause");
    return 0;
}