Problem

Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place.

Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue.

Hint: Try working backwards from the end state.

Examples

Example 1:

1
2
3

Input: stack = [1, 2, 3, 4, 5]
Output: [1,5,2,4,3]
Explanation: We interleave first and last element first - 1, 5, then we interleave 2nd and 2nd last element, 2, 4 and then finally middle element 3.

Example 2:

1
2

Input: stack = [1, 2, 3, 4]
Output: [1,4,2,3]

Solution

Method 1 - Iterative

Here’s a method to interleave the stack using a single queue. Assume stack = [1,2,3,4,5]

  1. Pop all elements from the stack to the queue to reverse their order. q = [5, 4, 3, 2, 1]
  2. Push the first half elements back to the stack. s = [5,4], q = [3, 2, 1]
  3. If number of elements are odd, move 1 element to the end of queue. q = [2, 1, 3], s = [5, 4]
  4. Dequeue the first half of the elements from the stack and enqueue them into the queue, interleaving with the second half.
    • s.pop() ⇨ 4 ⇨ q.add() ⇨ q = [2, 1, 3, 4]; q.remove() ⇨ 2 ⇨ q.add() ⇨ [1, 3, 4, 2]; s = [5]
    • s.pop() ⇨ 5 ⇨ q.add() ⇨ q = [1, 3, 4, 2, 5]; q.remove() ⇨ 1 ⇨ q.add() ⇨ [3, 4, 2, 5, 1]; s = []
  5. Now, we elements to q, and reverse the stack: s = [1, 5, 2, 4, 3]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class InterleaveStack {

	public static void interleaveStack(Stack<Integer> stack) {
		Queue<Integer> queue = new LinkedList<>();
		int n = stack.size();
		int halfSize = n / 2;

		// Step 1: Move all elements from stack to queue
		while (!stack.isEmpty()) {
			queue.add(stack.pop());
		}

		// Step 2: Push first half elements back to stack
		for (int i = 0; i < halfSize; i++) {
			stack.push(queue.remove());
		}

		// Step 3: Queue the remaining elements to the end of the queue
		while (queue.size() > halfSize) {
			queue.add(queue.remove());
		}

		// Step 4: Interleave elements
		for (int i = 0; i < halfSize; i++) {
			queue.add(stack.pop()); // Move from stack to queue
			queue.add(queue.remove()); // Move front of queue to back
		}

		// Push everything back to stack
		while (!queue.isEmpty()) {
			stack.push(queue.remove());
		}

		// Reverse the stack to maintain original order on interleaved result
		reverseStack(stack);
	}

	private static void reverseStack(Stack<Integer> stack) {
		Queue<Integer> queue = new LinkedList<>();

		while (!stack.isEmpty()) {
			queue.add(stack.pop());
		}

		while (!queue.isEmpty()) {
			stack.push(queue.remove());
		}
	}

}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def interleave_stack(stack):
    queue = deque()
    n = len(stack)
    half_size = n // 2

    # Step 1: Move all elements from stack to queue
    while stack:
        queue.append(stack.pop())

    # Step 2: Push first half elements back to stack
    for _ in range(half_size):
        stack.append(queue.popleft())

    # Step 3: Queue the remaining elements to the end of the queue
    while queue:
        queue.append(queue.popleft())

    # Step 4: Interleave
    for _ in range(half_size):
        stack.append(queue.popleft())
        queue.append(stack.pop())

    while queue:
        stack.append(queue.popleft())

    return stack

Complexity

  • ⏰ Time complexity: O(n), where n is number of elements in stack.
  • 🧺 Space complexity: O(n)