Pfthb

 Stream<String> a = Stream.of("one", "three", "five");
 Stream<String> b = Stream.of("two", "four", "six");

What do I need to do for the output to be the below?

// one
// two
// three
// four
// five
// six

I looked into concat but as the javadoc explains, it just appends one after the other, it does not interleave / intersperse.

Stream<String> out = Stream.concat(a, b);
out.forEach(System.out::println);

Creates a lazily concatenated stream whose elements are all the
elements of the first stream followed by all the elements of the
second stream.

Wrongly gives

 // one
 // three
 // five
 // two
 // four
 // six

Could do it if I collected them and iterated, but was hoping for something more Java8-y, Streamy :-)

Note

I don't want to zip the streams

“zip” operation will take an element from each collection and combine them.

the result of a zip operation would be something like this: (unwanted)

 // onetwo
 // threefour
 // fivesix

I’d use something like this:

public static <T> Stream<T> interleave(Stream<T> a, Stream<T> b) Spliterator.SIZED);
 ch 

It retains the characteristics of the input streams as far as possible, which allows certain optimizations (e.g. for count()and toArray()). Further, it adds the ORDERED even when the input streams might be unordered, to reflect the interleaving.

When one stream has more elements than the other, the remaining elements will appear at the end.

A much dumber solution than Holger did, but may be it would fit your requirements:

private static <T> Stream<T> interleave(Stream<T> left, Stream<T> right) 
 Spliterator<T> splLeft = left.spliterator();
 Spliterator<T> splRight = right.spliterator();

 T single = (T) new Object[1];

 Stream.Builder<T> builder = Stream.builder();

 while (splRight.tryAdvance(x -> single[0] = x) && splLeft.tryAdvance(builder)) 
 builder.add(single[0]);
 

 return builder.build();

As you can see from the question comments, I gave this a go using zip:

Stream<String> a = Stream.of("one", "three", "five");
Stream<String> b = Stream.of("two", "four", "six");

Stream<String> out = interleave(a, b);


 public static <T> Stream<T> interleave(Stream<T> streamA, Stream<T> streamB) 
 return zip(streamA, streamB, (o1, o2) -> Stream.of(o1, o2)).flatMap(s -> s);
 

 /**
 * https://stackoverflow.com/questions/17640754/zipping-streams-using-jdk8-with-lambda-java-util-stream-streams-zip
 **/
 private static <A, B, C> Stream<C> zip(Stream<A> streamA, Stream<B> streamB, BiFunction<A, B, C> zipper) streamB.isParallel();
 return iteratorToFiniteStream(iteratorC, parallel);
 

 private static <T> Stream<T> iteratorToFiniteStream(Iterator<T> iterator, boolean parallel) 
 final Iterable<T> iterable = () -> iterator;
 return StreamSupport.stream(iterable.spliterator(), parallel);
 

This may not be a good answer because

(1) it collects to map, which you don't want to do I guess and

(2) it is not completely stateless as it uses AtomicIntegers.

Still adding it because

(1) it is readable and

(2) community can get an idea from this and try to improve it.

Stream<String> a = Stream.of("one", "three", "five");
Stream<String> b = Stream.of("two", "four", "six");

AtomicInteger i = new AtomicInteger(0);
AtomicInteger j = new AtomicInteger(1);

Stream.of(a.collect(Collectors.toMap(o -> i.addAndGet(2), Function.identity())),
 b.collect(Collectors.toMap(o -> j.addAndGet(2), Function.identity())))
 .flatMap(m -> m.entrySet().stream())
 .sorted(Comparator.comparing(Map.Entry::getKey))
 .forEach(e -> System.out.println(e.getValue())); // or collect

Output

one
two
three
four
five
six

@Holger's edit

Stream.concat(a.map(o -> new AbstractMap.SimpleEntry<>(i.addAndGet(2), o)),
 b.map(o -> new AbstractMap.SimpleEntry<>(j.addAndGet(2), o)))
 .sorted(Map.Entry.comparingByKey())
 .forEach(e -> System.out.println(e.getValue())); // or collect

One solution with Iterator

final Iterator<String> iterA = a.iterator();
final Iterator<String> iterB = b.iterator();

final Iterator<String> iter = new Iterator<String>() 
 private final AtomicInteger idx = new AtomicInteger();
 @Override
 public boolean hasNext() 
 @Override
 public String next() 
 return idx.getAndIncrement() % 2 == 0 && iterA.hasNext() ? iterA.next() : iterB.next();
 
;

 // Create target Stream with StreamEx from: https://github.com/amaembo/streamex 
 StreamEx.of(iter).forEach(System.out::println);

 // Or Streams from Google Guava
 Streams.stream(iter).forEach(System.out::println);

Or simply by the solution in abacus-util provided by me:

 AtomicInteger idx = new AtomicInteger();
 StreamEx.merge(a, b, (s1, s2) -> idx.getAndIncrement() % 2 == 0 ? Nth.FIRST : Nth.SECOND).forEach(Fn.println());