Skip to main content

​
Overview

Swap operations exchange the positions of the first two elements at the top of a stack. These are the simplest operations in Push Swap and are commonly used to make quick adjustments when elements are nearly in the correct position.

​
Available Operations

sa

Swap the first 2 elements of stack A

sb

Swap the first 2 elements of stack B

ss

Execute sa and sb simultaneously

​
How It Works

The swap operation takes the first two elements of a stack and exchanges their positions: 
Before swap:        After swap:
  [5]  ← top          [3]  ← top
  [3]                 [5]
  [8]                 [8]
  [1]                 [1]
If the stack has fewer than 2 elements, the swap operation does nothing.

​
Implementation

The swap operations are implemented in ft_swap.c. Here’s the core implementation:

​
Core Swap Function

ft_swap.c
static void	swap(t_list **stack)
{
	if (!*stack || !(*stack)->next)
		return ;
	*stack = (*stack)->next;
	(*stack)->prev->prev = *stack;
	(*stack)->prev->next = (*stack)->next;
	if ((*stack)->next)
		(*stack)->prev = (*stack)->prev;
	(*stack)->next = (*stack)->prev;
	(*stack)->prev = NULL;
}
The implementation:
  1. Checks if there are at least 2 elements in the stack
  2. Updates the stack head pointer to point to the second element
  3. Adjusts the doubly-linked list pointers to swap positions
  4. Maintains proper prev and next relationships

​
Public Operation Functions

ft_swap.c
void	sa(t_list **a, bool print)
{
	swap(a);
	if (!print)
		write(1, "sa\n", 3);
}
Swaps the first two elements of stack A and outputs “sa” to stdout.

​
Usage Examples

​
Example 1: Correcting Top Two Elements

When the top two elements of stack A are in the wrong order: 
Initial state:       After 'sa':
Stack A: 3 1 2 4    Stack A: 1 3 2 4
Stack B: -           Stack B: -

Result: Top two elements now in correct relative order

​
Example 2: Simultaneous Swap

When both stacks need their top elements swapped: 
Initial state:       After 'ss':
Stack A: 5 2 1      Stack A: 2 5 1
Stack B: 9 7 3      Stack B: 7 9 3

Result: Both stacks have their top two elements swapped

​
Example 3: Edge Case - Single Element

Initial state:       After 'sa':
Stack A: 5          Stack A: 5
Stack B: -          Stack B: -

Result: No change (less than 2 elements)

​
When to Use

Swap operations are most effective when:
  • The top two elements are in the wrong order but close to their target positions
  • Finalizing an almost-sorted stack
  • Making minor adjustments after rotation operations
  • Combining with other operations in optimization strategies
Using ss instead of separate sa and sb operations saves one operation in your total count, which is crucial for optimizing sorting algorithms.

​
Time Complexity

  • Time Complexity: O(1) - constant time operation
  • Space Complexity: O(1) - no additional space required
Swap operations are among the most efficient operations available, requiring only pointer manipulation without traversing the stack.

​
See Also

Push Operations

Move elements between stacks

Rotate Operations

Shift all elements up by one position

Build docs developers (and LLMs) love

Get started for freeTalk to us