Reverse Rotate Operations

Overview

Reverse rotate operations shift all elements in a stack downward by one position. The last element (at the bottom) becomes the first element (at the top). These operations provide an efficient way to access elements in the lower half of the stack.

Available Operations

rra

Reverse rotate stack A downward

rrb

Reverse rotate stack B downward

rrr

Reverse rotate both stacks simultaneously

How It Works

The reverse rotate operation takes the bottom element and moves it to the top, shifting all other elements down:

Before 'rra':        After 'rra':
  [5]  ← top           [1]  ← top
  [3]                  [5]
  [8]                  [3]
  [1]  ← bottom        [8]  ← bottom

Think of it as a circular shift downward:

Bottom element moves to the top
All other elements shift down one position
The element that was second-to-last becomes the new bottom

If the stack has fewer than 2 elements, the reverse rotate operation does nothing.

Implementation

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

Core Reverse Rotate Function

ft_reverse_rotate.c

static void	reverse_rotate(t_list **stack)
{
	t_list	*last;
	t_list	*second_last;

	if (*stack == NULL || (*stack)->next == NULL)
		return ;
	last = *stack;
	second_last = NULL;
	while (last->next)
	{
		second_last = last;
		last = last->next;
	}
	second_last->next = NULL;
	last->next = *stack;
	*stack = last;
	return ;
}

The implementation works as follows:

Validation: Check if there are at least 2 elements
Traverse to End: Find both the last and second-to-last nodes
Detach Last Node: Set second_last->next to NULL
Move to Top: Link the last node to the current top
Update Head: Make the last node the new stack head

Public Operation Functions

ft_reverse_rotate.c

void	rra(t_list **a, bool print)
{
	reverse_rotate(a);
	if (!print)
		write(1, "rra\n", 4);
}

Reverse rotates stack A downward - last element becomes first.Parameters:

a: Pointer to stack A
print: If false, outputs “rra” to stdout

ft_reverse_rotate.c

void	rrb(t_list **b, bool print)
{
	reverse_rotate(b);
	if (!print)
		write(1, "rrb\n", 4);
}

Reverse rotates stack B downward - last element becomes first.Parameters:

b: Pointer to stack B
print: If false, outputs “rrb” to stdout

ft_reverse_rotate.c

void	rrr(t_list **a, t_list **b, bool print)
{
	reverse_rotate(a);
	reverse_rotate(b);
	if (!print)
		write(1, "rrr\n", 4);
}

Reverse rotates both stacks A and B simultaneously.Parameters:

a: Pointer to stack A
b: Pointer to stack B
print: If false, outputs “rrr” to stdout

Detailed Operation Flow

Single Stack Reverse Rotation

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

Step 2: Execute 'rra'
- Traverse to find last: [1]
- Find second_last: [8]

Step 3: Detach Last
- Set [8]->next = NULL
- [1] is now isolated

Step 4: Move to Top
- Set [1]->next = [5]
- [1] now points to old top

Step 5: Update Head
- Set stack head to [1]

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

Simultaneous Reverse Rotation

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

Both stacks reverse rotated in a single operation

Usage Examples

Example 1: Accessing Bottom Elements

Bringing the last element to the top:

Goal: Get element [1] from bottom to top

Stack A: 5 3 8 1    After 'rra':
Target: 1           Stack A: 1 5 3 8
                    [1] is now on top!
                    (only 1 operation vs 3 rotates)

Example 2: Efficient Positioning

When target is in the lower half:

Stack A: 2 5 9 [7] 3 1
Target: 7 (position 3 of 6)

Using reverse rotate:
rra → 1 2 5 9 7 3
rra → 3 1 2 5 9 7
rra → 7 3 1 2 5 9  (3 operations)

Using regular rotate would need:
ra → 5 9 7 3 1 2
ra → 9 7 3 1 2 5
ra → 7 3 1 2 5 9  (same 3 operations)

But for elements closer to bottom, rra is more intuitive

Example 3: Combined Operations

Optimizing with rrr:

Stack A: 5 3 1     Stack B: 9 7 2
Need: 1 at top A   Need: 2 at top B

Instead of:        Use:
rra                rrr
rrb                (saves one operation)

Result:
Stack A: 1 5 3     Stack B: 2 9 7

When to Use Reverse Rotate

Choose reverse rotate over regular rotate based on element position:

Position Calculation
Visual Guide

// Pseudo-code for choosing rotation direction
int target_index = find_index(stack, target_value);
int stack_size = stack_len(stack);

if (target_index <= stack_size / 2)
{
    // Target is in upper half
    // Use regular rotate (ra/rb)
    while (target_index-- > 0)
        ra(&stack);
}
else
{
    // Target is in lower half  
    // Use reverse rotate (rra/rrb)
    int rotations = stack_size - target_index;
    while (rotations-- > 0)
        rra(&stack);
}

Stack with 7 elements:

Position 0: [5]  ← Use ra (0 rotations)
Position 1: [3]  ← Use ra (1 rotation)
Position 2: [8]  ← Use ra (2 rotations)
Position 3: [1]  ← Median (equal cost)
Position 4: [9]  ← Use rra (3 rotations)
Position 5: [2]  ← Use rra (2 rotations)
Position 6: [7]  ← Use rra (1 rotation)

Rule: If index > size/2, use reverse rotate

The above_median flag in the node structure (see push_swap.h:26) is set during node initialization to indicate whether to use rotate or reverse rotate for optimal positioning.

Strategic Applications

Bottom-Up Processing

When the algorithm needs to process elements from the bottom of the stack:

Check bottom element:
rra (bring to top)
if (should_push)
    pb
else
    ra (put back)

Sorting Finalization

After sorting, position the minimum element at the top:

Find min position
if (min is in lower half)
{
    while (min not on top)
        rra
}

Now stack is correctly sorted

Cost Optimization

Minimize operations by choosing the shorter path:

int ra_cost = target_index;
int rra_cost = stack_size - target_index;

if (rra_cost < ra_cost)
    use_reverse_rotate();
else
    use_rotate();

Dual Stack Coordination

When both stacks need elements from the bottom:

if (both_need_reverse_rotation)
{
    int common = min(a_rra_needed, b_rrb_needed);
    while (common--)
        rrr(&a, &b);
    // Handle remaining individual rotations
}

Comparison: Rotate vs Reverse Rotate

Aspect	Rotate (ra/rb/rr)	Reverse Rotate (rra/rrb/rrr)
Direction	Top → Bottom	Bottom → Top
First element	Becomes last	Stays in place (shifts down)
Last element	Stays in place (shifts up)	Becomes first
Best for	Upper half elements	Lower half elements
Use case	Forward scanning	Backward scanning
Operation count	Lower for positions 0 to n/2	Lower for positions n/2 to n

Performance Characteristics

Time Complexity: O(n) - must traverse to find the last node
Space Complexity: O(1) - no additional memory allocation
Traversal: Visits each node once to find the end

Although reverse rotate has O(n) complexity, it’s often the most efficient choice for accessing elements in the lower half of the stack. The key is minimizing the total number of operations, not the complexity of individual operations.

Optimization Tips

Calculate Position

Always determine the target element’s position in the stack before deciding on rotation direction.

Compare Costs

Calculate operations needed for both ra and rra approaches:

ra_cost = index
rra_cost = stack_size - index
choose minimum

Use Dual Operations

When both stacks need reverse rotation, use rrr instead of separate rra and rrb calls.

Cache Calculations

Store position and rotation cost in the node structure to avoid recalculating during execution.

Rotate Operations

Shift stack elements upward

Push Operations

Transfer elements between stacks

Swap Operations

Exchange top two elements

Getting Started

Algorithm

Operations Reference

Implementation

Usage

Development

Reverse Rotate Operations

Overview

Available Operations

rra

rrb

rrr

How It Works

Implementation

Core Reverse Rotate Function

Public Operation Functions

Detailed Operation Flow

Single Stack Reverse Rotation

Simultaneous Reverse Rotation

Usage Examples

Example 1: Accessing Bottom Elements

Example 2: Efficient Positioning

Example 3: Combined Operations

When to Use Reverse Rotate

Strategic Applications

Comparison: Rotate vs Reverse Rotate

Performance Characteristics

Optimization Tips

See Also

Rotate Operations

Push Operations

Swap Operations

Build docs developers (and LLMs) love

Getting Started

Algorithm

Operations Reference

Implementation

Usage

Development

​Overview

​Available Operations

rra

rrb

rrr

​How It Works

​Implementation

​Core Reverse Rotate Function

​Public Operation Functions

​Detailed Operation Flow

​Single Stack Reverse Rotation

​Simultaneous Reverse Rotation

​Usage Examples

​Example 1: Accessing Bottom Elements

​Example 2: Efficient Positioning

​Example 3: Combined Operations

​When to Use Reverse Rotate

​Strategic Applications

​Comparison: Rotate vs Reverse Rotate

​Performance Characteristics

​Optimization Tips

​See Also

Rotate Operations

Push Operations

Swap Operations

Build docs developers (and LLMs) love

Overview

Available Operations

How It Works

Implementation

Core Reverse Rotate Function

Public Operation Functions

Detailed Operation Flow

Single Stack Reverse Rotation

Simultaneous Reverse Rotation

Usage Examples

Example 1: Accessing Bottom Elements

Example 2: Efficient Positioning

Example 3: Combined Operations

When to Use Reverse Rotate

Strategic Applications

Comparison: Rotate vs Reverse Rotate

Performance Characteristics

Optimization Tips

See Also