Skip to main content

​
Overview

Push operations move the top element from one stack to another. These operations are fundamental to the Push Swap algorithm, as they enable the distribution and consolidation of elements between stacks A and B during the sorting process.

​
Available Operations

pa

Push the top element from stack B to stack A

pb

Push the top element from stack A to stack B

​
How It Works

A push operation removes the top element from the source stack and places it at the top of the destination stack: 
Before 'pb':         After 'pb':
Stack A: 5 3 8 1    Stack A: 3 8 1
Stack B: -          Stack B: 5

Before 'pa':         After 'pa':
Stack A: 3 8 1      Stack A: 5 3 8 1
Stack B: 5          Stack B: -
If the source stack is empty, the push operation does nothing.

​
Implementation

The push operations are implemented in ft_push.c. Here’s the complete implementation:

​
Core Push Function

ft_push.c
static void	push(t_list **dst, t_list **src)
{
	t_list	*push_node;

	if (!*src)
		return ;
	push_node = *src;
	*src = (*src)->next;
	if (*src)
		(*src)->prev = NULL;
	push_node->prev = NULL;
	if (!*dst)
	{
		*dst = push_node;
		push_node->next = NULL;
	}
	else
	{
		push_node->next = *dst;
		push_node->next->prev = push_node;
		*dst = push_node;
	}
}
The implementation follows these steps:
  1. Validation: Check if the source stack is empty
  2. Extract: Save reference to the top node and update source stack head
  3. Update Source: Adjust the new top node’s prev pointer to NULL
  4. Insert into Destination:
    • If destination is empty: Make the node the only element
    • If destination has elements: Insert at the top and update links

​
Public Operation Functions

ft_push.c
void	pa(t_list **a, t_list **b, bool print)
{
	push(a, b);
	if (!print)
		write(1, "pa\n", 3);
}
Pushes the top element from stack B to stack A.Parameters:
  • a: Pointer to stack A (destination)
  • b: Pointer to stack B (source)
  • print: If false, outputs “pa” to stdout

​
Detailed Operation Flow

​
Pushing to an Empty Stack

Step 1: Initial State
Stack A: 3 8 1
Stack B: (empty)

Step 2: Execute 'pb'
- Extract node [3] from stack A
- Stack A becomes: 8 1

Step 3: Insert into empty stack B
- Make [3] the head of stack B
- Set next pointer to NULL

Step 4: Final State
Stack A: 8 1
Stack B: 3

​
Pushing to a Non-Empty Stack

Step 1: Initial State
Stack A: 8 1
Stack B: 3

Step 2: Execute 'pb'
- Extract node [8] from stack A
- Stack A becomes: 1

Step 3: Insert at top of stack B
- Set [8]->next = [3]
- Set [3]->prev = [8]
- Make [8] the new head

Step 4: Final State
Stack A: 1
Stack B: 8 3

​
Usage Examples

​
Example 1: Distributing Elements

Moving elements to stack B for processing: 
Initial:             After 'pb':          After 'pb':
Stack A: 5 2 8 1    Stack A: 2 8 1      Stack A: 8 1
Stack B: -          Stack B: 5          Stack B: 2 5

​
Example 2: Returning Elements

Bringing sorted elements back to stack A: 
Initial:             After 'pa':          After 'pa':
Stack A: 1          Stack A: 2 1        Stack A: 5 2 1
Stack B: 2 5        Stack B: 5          Stack B: -

​
Example 3: Empty Stack Handling

Initial:             After 'pa':
Stack A: 1 2 3      Stack A: 1 2 3
Stack B: (empty)    Stack B: (empty)

Result: No change (source stack is empty)

​
Common Patterns

​
Pattern 1: Partition Strategy

Push smaller elements to B, keeping larger ones in A:
pb  (if current element < median)
pb
rr  (rotate both to continue processing)

​
Pattern 2: Consolidation

Bring all elements back to A after sorting:
pa
pa
pa
(repeat until B is empty)

​
Pattern 3: Selective Transfer

Move specific elements for targeted sorting:
ra  (rotate to position target element)
pb  (push to B)
rrb (adjust position in B)

​
Strategic Use

Push operations are essential for:
Splitting the input into manageable subsets by pushing elements between stacks based on criteria (e.g., value ranges, median comparisons).
Using stack B as a temporary holding area while organizing elements in stack A, then retrieving them in the optimal order.
Implementing multi-phase sorting where elements are pushed to B, sorted, and then pushed back to A in the correct order.
Moving elements that are expensive to sort in their current position to a better location for processing.

​
Performance Characteristics

  • Time Complexity: O(1) - constant time operation
  • Space Complexity: O(1) - no additional memory allocation
  • Stack Modification: Changes the size of both stacks
When designing your sorting algorithm, minimize the number of push operations by being strategic about which elements to move and when. Each push operation counts toward your total operation count.

​
See Also

Swap Operations

Exchange top two elements

Rotate Operations

Shift stack elements upward

Reverse Rotate

Shift stack elements downward

Build docs developers (and LLMs) love

Get started for freeTalk to us