Skip to main content

​
Overview

Rotate operations shift all elements in a stack upward by one position. The first element (at the top) becomes the last element (at the bottom). These operations are crucial for positioning target elements at the top of the stack for further manipulation.

​
Available Operations

ra

Rotate stack A upward

rb

Rotate stack B upward

rr

Rotate both stacks simultaneously

​
How It Works

The rotate operation takes the top element and moves it to the bottom, shifting all other elements up: 
Before 'ra':         After 'ra':
  [5]  ← top           [3]  ← top
  [3]                  [8]
  [8]                  [1]
  [1]  ← bottom        [5]  ← bottom
Think of it as a circular shift upward:
  • Top element moves to the bottom
  • All other elements shift up one position
  • The second element becomes the new top
If the stack has fewer than 2 elements, the rotate operation does nothing.

​
Implementation

The rotate operations are implemented in ft_rotate.c. Here’s the complete implementation:

​
Core Rotate Function

ft_rotate.c
static void	rotate(t_list **stack)
{
	t_list	*last;

	if (!*stack || !(*stack)->next)
		return ;
	last = *stack;
	while (last->next)
		last = last->next;
	last->next = *stack;
	*stack = (*stack)->next;
	(*stack)->prev = NULL;
	last->next->prev = last;
	last->next->next = NULL;
}
The implementation works as follows:
  1. Validation: Check if there are at least 2 elements
  2. Find Last Node: Traverse to the end of the linked list
  3. Attach Top to Bottom: Link the current top node to the last node
  4. Update Stack Head: Make the second element the new top
  5. Fix Pointers: Update prev and next pointers to maintain list integrity

​
Public Operation Functions

ft_rotate.c
void	ra(t_list **a, bool print)
{
	rotate(a);
	if (!print)
		write(1, "ra\n", 3);
}
Rotates stack A upward - first element becomes last.Parameters:
  • a: Pointer to stack A
  • print: If false, outputs “ra” to stdout

​
Detailed Operation Flow

​
Single Stack Rotation

Step 1: Initial State
Stack A: [5] → [3] → [8] → [1] → NULL
         top                  bottom

Step 2: Execute 'ra'
- Find last node: [1]
- Connect: [1]->next = [5]

Step 3: Update Head
- Make [3] the new top
- Set [3]->prev = NULL

Step 4: Finalize
- Set [5]->next = NULL (now last)
- Set [5]->prev = [1]

Step 5: Final State
Stack A: [3] → [8] → [1] → [5] → NULL
         top                  bottom

​
Simultaneous Rotation

Before 'rr':          After 'rr':
Stack A: 5 3 8 1     Stack A: 3 8 1 5
Stack B: 9 2 4       Stack B: 2 4 9

Both stacks rotated in a single operation

​
Usage Examples

​
Example 1: Positioning Target Element

Bringing a specific element to the top: 
Goal: Get element [1] to the top

Stack A: 5 3 8 1    After 'ra':      After 'ra':      After 'ra':
Target: 1           Stack A: 3 8 1 5 Stack A: 8 1 5 3 Stack A: 1 5 3 8
                                                        [1] is now on top!

​
Example 2: Circular Processing

Scanning through all elements: 
Process each element by rotating:

Stack A: 5 3 8 1
ra → Process 3
ra → Process 8  
ra → Process 1
ra → Process 5 (back to original)

​
Example 3: Optimized Dual Rotation

When both stacks need rotation:

Instead of:          Use:
ra                   rr
rb                   (saves one operation)

Stack A: 5 3 1  →    Stack A: 3 1 5
Stack B: 9 2    →    Stack B: 2 9

​
Strategic Applications

Rotate operations are essential for bringing elements to the top of the stack for:
  • Pushing to the other stack
  • Swapping with another element
  • Comparing with the top of the other stack
ra  (move target closer to top)
ra  (continue rotating)
pb  (now push the target element)
When dividing elements around a median value:
If top element < median:
  pb (push to B)
Else:
  ra (rotate in A)
This keeps larger elements in A while moving smaller ones to B.
After sorting, rotate to ensure the minimum element is at the top:
Find position of min element
Rotate until min is at top:
ra (repeat until min is on top)
When both stacks need rotation in the same direction:
Calculate common rotations:
While both need rotation:
  rr (rotate both)
Then handle remaining rotations:
  ra or rb (as needed)
This minimizes total operation count.

​
Rotation vs. Reverse Rotation

Choosing between rotate and reverse rotate depends on the position of your target element: 
Stack: 5 3 [8] 1 2
Target: 8 (position 2 of 5)

Use rotate (ra):
ra → 3 8 1 2 5
ra → 8 1 2 5 3 (2 operations)
When the target is in the upper half (index < size/2), use regular rotate.
Always calculate whether rotate or reverse rotate requires fewer operations. The above_median flag in the node structure helps track this.

​
Performance Characteristics

  • Time Complexity: O(n) - must traverse to find the last node
  • Space Complexity: O(1) - no additional memory allocation
  • Operation Count: Each rotation counts as one operation
While rotate is O(n) due to list traversal, it’s still efficient for the Push Swap algorithm. Consider the number of rotations needed, not just the complexity of each rotation.

​
See Also

Reverse Rotate

Shift stack elements downward

Push Operations

Transfer elements between stacks

Swap Operations

Exchange top two elements

Build docs developers (and LLMs) love

Get started for freeTalk to us