颠倒字符串中的单词（split、双端队列）

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

给你一个字符串 s ，颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路：
1.用split分割，reverse反转，join拼接三个Java内置函数解决

缺点：面试时这么写，面试官可能就会说：面试就先到这吧（狗头）。

调用函数不是本题的初衷。

代码如下：

import java.util.Arrays;
import java.util.Collections;

public class Main {
    
    public static void main(String[] args) {
    
        String s = "excample a gg";
        System.out.println(reverseWords(s));
    }
    public static String reverseWords(String s) {
    
        //除去开头和末尾空白字符
        s = s.trim();

        String[] words = s.split(" +");

        Collections.reverse(Arrays.asList(words));

        return String.join(" ", words);
    }
}

用双端队列，由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。

代码如下：

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    
    public static void main(String[] args) {
    
        String s = " example a gg ";
        System.out.println(reverseWords(s));
    }
    public static String reverseWords(String s) {
    
        int left = 0;
        int right = s.length()-1;

        //去除字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' '){
    
            left++;
        }
        //去除字符串尾部的空白字符
        while (left <= right && s.charAt(right) == ' '){
    
            right--;
        }

        Deque<String> d = new ArrayDeque<String>();//双端队列

        StringBuilder word = new StringBuilder();

        while (left <= right) {
    
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
    
                // 将单词压到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);//word置空
            } else if (c != ' ') {
    //考虑字符串内部有空格的情况
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());

        return String.join(" ", d);

    }
}