Java: Queue of Stacks

  • 0

    Obviously, not super-efficient, but, I think, a good use of standard library + fairly easy to understand.

    The idea:

    • Use a queue (first in, first out) to capture the order of words (should be preserved);
    • Use a stack (first in, last out) to capture the order of individual characters within the given word (should be reversed);

    Here's the implementation:

    public String reverseWords(String s) {
      // Stores all currently processed words
      Queue<Stack<Character>> contents = 
        new LinkedList<Stack<Character>>();
      // Points to the current word
      Stack<Character> cur = null;
      for (Character ch : s.toCharArray()) {
        if (!Character.isWhitespace(ch)) {
          // We're starting with the new word
          if (cur == null) {
            cur = new Stack<>();
        } else {
          // We're done with the current word (encountered a whitespace)
          cur = null;
      StringBuilder sb = new StringBuilder();
      while (contents.size() > 0) {
        Stack<Character> item = contents.remove();
        // Making sure we don't put a whitespace in the beginning
        if (sb.length() > 0) {
          sb.append(" ");
        while (item.size() > 0) {
      return sb.toString();

    Runtime and space complexity is O(N).

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.