스택을 위한 구조체 | Struct for Stack

스택을 위한 구조체 ❘ Struct for Stack

이 세 가지 구조체(s_node, s_stack, t_var)는 정렬 알고리즘을 구현하기 위해 함께 작동하도록 설계하였습니다. 

t_node 구조체
t_node 구조체는 이중 연결 리스트의 단일 노드를 나타냅니다:
val: 노드의 정수 값을 저장합니다.
left와 right: 각각 이전 노드와 다음 노드를 가리키는 포인터입니다.
이 구조체는 리스트의 양방향 순회를 가능하게 하며, 이는 효율적인 스택 연산에 중요합니다.

 

t_stack 구조체
t_stack 구조체는 스택을 나타냅니다:
top: 스택의 최상위 노드를 가리킵니다.
bottom: 스택의 최하위 노드를 가리킵니다.
이 구조체는 t_node를 사용하여 스택 데이터 구조를 생성합니다. 스택의 양 끝에 대한 포인터를 유지하여 양쪽 끝에서 효율적인 push와 pop 연산이 가능합니다.

 

t_var 구조체
t_var 구조체는 정렬 알고리즘에 필요한 모든 변수를 담는 컨테이너 역할을 합니다:
max_size: 스택의 최대 크기를 나타낼 것으로 보입니다.
pivot_arr: 피벗 값들의 배열로, 퀵소트와 유사한 알고리즘에서 사용될 수 있습니다.
stack_a와 stack_b: 두 개의 t_stack 구조체를 가리키는 포인터로, 정렬 과정에서 사용되는 두 스택을 나타냅니다.
list: 원본 숫자 리스트를 저장하는 배열입니다.
list_size: 원본 리스트의 크기입니다.
a_size와 b_size: 각각 스택 A와 스택 B의 현재 크기입니다.

 

관계
t_node와 t_stack:
각 t_stack은 t_node 요소들로 구성됩니다.
t_stack의 top과 bottom 포인터는 t_node 구조체를 가리킵니다.
t_stack과 t_var:
t_var는 두 개의 t_stack 구조체에 대한 포인터(stack_a와 stack_b)를 포함합니다.
이들은 Push_swap과 같은 알고리즘에서 사용되는 두 스택을 나타냅니다.
t_var와 전체 알고리즘:
t_var는 정렬 알고리즘에 필요한 모든 데이터를 캡슐화합니다.
두 스택, 원본 리스트, 그리고 피벗 값과 같은 추가 정보를 관리합니다.
이러한 구조는 스택 연산과 정렬 알고리즘의 효율적인 구현을 가능하게 하며, 정렬 과정 전반에 걸쳐 데이터를 관리하고 조작하는 포괄적인 방법을 제공하기 위해 구현되었습니다.

 

var->stack_a->top->right = var->stack_a->bottom; 구문은 초기 빈 스택 상태를 설정하는 것입니다. 실제로 데이터가 스택에 추가되면 연결 구조가 변경됩니다. 데이터가 추가될 때의 과정을 설명하겠습니다:

초기 상태:
top->right는 bottom을 가리킵니다.
bottom->left는 top을 가리킵니다.

첫 번째 데이터 노드 추가 시:
새 노드 new_node가 생성됩니다.
top->right는 이제 new_node를 가리킵니다.
new_node->left는 top을 가리킵니다.
new_node->right는 bottom을 가리킵니다.
bottom->left는 new_node를 가리킵니다.

추가 데이터 노드 삽입 시:
새 노드는 항상 top->right와 그 다음 노드 사이에 삽입됩니다.
top->right는 항상 가장 최근에 추가된 데이터 노드를 가리키게 됩니다.
따라서, 데이터가 스택에 추가되면 top->right는 가장 최근에 추가된 데이터 노드를 가리키게 되며, 더 이상 직접적으로 bottom을 가리키지 않습니다. bottom은 스택의 마지막 데이터 노드의 right가 가리키게 됩니다.
이러한 구조는 스택의 push와 pop 연산을 O(1) 시간 복잡도로 효율적으로 수행할 수 있게 해줍니다.

 

이 구현에서 right 포인터는 항상 스택의 아래쪽(bottom 방향)을 가리키게 됩니다. 이 구조의 주요 특징을 정리하면 다음과 같습니다:

방향성:
right 포인터: 스택의 bottom 방향을 가리킵니다.
left 포인터: 스택의 top 방향을 가리킵니다.

노드 연결:
각 노드의 right는 자신보다 나중에 추가된 (스택의 아래쪽에 있는) 노드를 가리킵니다.
각 노드의 left는 자신보다 먼저 추가된 (스택의 위쪽에 있는) 노드를 가리킵니다.

스택 구조:
top 노드: 스택의 가장 위에 있는 더미 노드입니다.
bottom 노드: 스택의 가장 아래에 있는 더미 노드입니다.
실제 데이터 노드들: top과 bottom 사이에 위치합니다.

연산 특성:
Push 연산: 새 노드는 항상 top과 top->right 사이에 삽입됩니다.
Pop 연산: top->right가 가리키는 노드를 제거합니다.
이러한 구조는 스택의 양 끝에서의 빠른 접근과 효율적인 연산을 가능하게 합니다. right가 항상 아래쪽을 가리키는 이 설계는 스택의 LIFO(Last In, First Out) 특성을 효과적으로 구현할 수 있게 해줍니다.

 

 

 

These three structures (s_node, s_stack, and s_var) are designed to work together in implementing a sorting algorithm. Let's break down their relationships and purposes:

t_node Structure
The t_node structure represents a single node in a doubly-linked list:
val: Stores the integer value of the node.
left and right: Pointers to the previous and next nodes, respectively.
This structure allows for bidirectional traversal of the list, which is crucial for efficient stack operations.

 

t_stack Structure
The t_stack structure represents a stack:
top: Points to the topmost node of the stack.
bottom: Points to the bottommost node of the stack.
This structure uses the t_node to create a stack data structure. It maintains pointers to both ends of the stack, allowing for efficient push and pop operations at either end.

 

t_var Structure
The t_var structure serves as a container for all variables needed in the sorting algorithm:
max_size: Likely represents the maximum size of the stacks.
pivot_arr: An array of pivot values, possibly used in a quicksort-like algorithm.
stack_a and stack_b: Pointers to two t_stack structures, representing the two stacks used in the sorting process.
list: An array to store the original list of numbers.
list_size: The size of the original list.
a_size and b_size: Current sizes of stack A and stack B, respectively.

 

Relationships
t_node and t_stack:
Each t_stack is composed of t_node elements.
The top and bottom pointers in t_stack point to t_node structures.
t_stack and t_var:
t_var contains pointers to two t_stack structures (stack_a and stack_b).
These represent the two stacks used in algorithms like Push_swap.
t_var and overall algorithm:
t_var encapsulates all necessary data for the sorting algorithm.
It manages both stacks, the original list, and additional information like pivot values.
This structure allows for efficient implementation of stack operations and sorting algorithms, providing a comprehensive way to manage and manipulate the data throughout the sorting process.

 

 

The statement var->stack_a->top->right = var->stack_a->bottom; sets up the initial state of an empty stack. When data is actually added to the stack, the connection structure changes. Here's an explanation of the process when data is added:

Initial state:
top->right points to bottom.
bottom->left points to top.

When the first data node is added:
A new node new_node is created.
top->right now points to new_node.
new_node->left points to top.
new_node->right points to bottom.
bottom->left points to new_node.

 

When additional data nodes are inserted:
New nodes are always inserted between top->right and the next node.
top->right always points to the most recently added data node.
Therefore, as data is added to the stack, top->right points to the most recently added data node and no longer directly points to bottom. bottom is pointed to by the right of the last data node in the stack.

 

This structure allows for efficient push and pop operations with O(1) time complexity.
In this implementation, the right pointer always points towards the bottom of the stack. The main features of this structure can be summarized as follows:

 

Directionality:
right pointer: Points towards the bottom of the stack.
left pointer: Points towards the top of the stack.

 

Node connections:
Each node's right points to the node added after it (lower in the stack).
Each node's left points to the node added before it (higher in the stack).

 

Stack structure:
top node: A dummy node at the very top of the stack.
bottom node: A dummy node at the very bottom of the stack.
Actual data nodes: Located between top and bottom.

 

Operation characteristics:
Push operation: New nodes are always inserted between top->right and the next node.
Pop operation: Removes the node pointed to by top->right.
This structure enables quick access and efficient operations at both ends of the stack. The design where right always points downwards effectively implements the LIFO (Last In, First Out) characteristic of the stack.