[요약] 자료 구조 - 3 [스택, 큐, 데크, 트리, 이진 트리]

※ 주의 ※
이 블로그는 어디까지나 CS관련 지식을 정리하는 것이 목적입니다. 제가 이해한 내용이 잘못 된 것 같다면 댓글로 남겨주세요. 여러분의 관심이 저의 지식 함양에 도움이 됩니다.

>> 스택의 개념과 연산 

• 스택의 개념
  • 스택(Stack): 접시를 쌓듯이 자료를 차곡차곡 쌓아 올리는 형태의 자료구조입니다.
  • 후입선출(Last-In, First-Out, LIFO): 가장 최근에 삽입된 원소가 가장 먼저 삭제됩니다. 즉, 마지막에 삽입된 원소가 맨 위에 쌓이고, 가장 먼저 삭제됩니다.
• 스택의 기본 연산
  1. 삽입 연산 (Push)
     • 스택의 top 위치에서 원소를 추가합니다.
     • 절차:
       1. top을 1 증가시킨 후, 원소를 top 위치에 저장합니다.
       2. 포화 상태 여부를 확인하여 추가적인 처리를 합니다.
  2. 삭제 연산 (Pop)
     • 스택의 top 위치에서 원소를 삭제하고 반환합니다.
     • 절차:
       1. 공백 상태 여부를 확인합니다.
       2. top 위치의 원소를 반환한 후, top을 1 감소시킵니다.

>> 순차 자료구조를 이용한 스택의 구현 

• 구현 방법: 1차원 배열을 사용하여 스택을 구현합니다.
• 변수:
  • top: 스택의 마지막 원소에 대한 인덱스를 저장합니다.
  • 공백 상태: top = -1 (스택이 비어 있는 상태)
  • 포화 상태: top = n-1 (스택이 가득 찬 상태, 배열의 크기 n)
• 절차:
  • Push:
    • top을 1 증가시킵니다.
    • 배열의 top 위치에 새로운 원소를 저장합니다.
    • 포화 상태를 확인하여 필요한 경우 에러 처리를 합니다.
  • Pop:
    • 공백 상태를 확인하여 스택이 비어 있는지 확인합니다.
    • top 위치의 원소를 반환합니다.
    • top을 1 감소시킵니다.

코드 예제 (Python):

class Stack:
    def __init__(self, size):
        self.stack = [None] * size
        self.top = -1
        self.size = size

    def push(self, value):
        if self.top >= self.size - 1:
            print("Stack overflow")
            return
        self.top += 1
        self.stack[self.top] = value

    def pop(self):
        if self.top == -1:
            print("Stack underflow")
            return None
        value = self.stack[self.top]
        self.top -= 1
        return value

# 예시 사용
s = Stack(5)
s.push(10)
s.push(20)
print(s.pop())  # 출력: 20
print(s.pop())  # 출력: 10
print(s.pop())  # 출력: Stack underflow

>> 연결 자료구조를 이용한 스택의 구현 

• 구현 방법: 단순 연결 리스트를 사용하여 스택을 구현합니다.
• 변수:
  • top: 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수로 초기 상태는 top = None입니다.
• 절차:
  
  • Push:
    1. 새로운 노드를 생성합니다.
    2. 새 노드의 링크 필드를 현재의 top 노드를 가리키게 설정합니다.
    3. top을 새 노드를 가리키도록 업데이트합니다.
  • Pop:
    1. 공백 상태를 확인하여 스택이 비어 있는지 확인합니다.
    2. top 노드의 값을 저장합니다.
    3. top을 새 top 노드를 설정합니다 (기존 top 노드의 링크 필드로).
    4. 기존 top 노드를 삭제합니다.

코드 예제 (Python):

>> 역순 문자열 만들기 

• 스택의 후입선출(LIFO) 성질을 이용하여 문자열을 역순으로 만드는 방법은 다음과 같습니다:
  1. 문자열을 스택에 삽입: 문자열의 각 문자를 순서대로 스택에 삽입합니다. 스택은 후입선출 구조이므로, 마지막에 삽입된 문자가 가장 먼저 삭제됩니다.
  2. 스택에서 삭제하여 문자열 생성: 스택에서 문자를 하나씩 삭제(pop)하면서 역순으로 문자열을 구성합니다.
  3. 결과 출력: 삭제된 문자를 모아서 역순 문자열을 출력합니다.

알고리즘 예제:

def reverse_string(s):
    stack = []
    # 문자열의 각 문자를 스택에 삽입
    for char in s:
        stack.append(char)
    
    # 스택에서 문자를 꺼내어 역순 문자열 생성
    reversed_str = ''
    while stack:
        reversed_str += stack.pop()
    
    return reversed_str

# 예시 사용
input_str = "hello"
print(reverse_string(input_str))  # 출력: "olleh"

>> 프로그램 호출과 복귀에 따른 수행 순서 

• 시스템 스택은 프로그램에서의 호출과 복귀를 관리하는 데 중요한 역할을 합니다:
• 함수 호출:
  • 함수가 호출될 때, 호출한 함수의 지역 변수, 매개변수, 복귀 주소 등을 스택 프레임에 저장합니다.
  • 이 스택 프레임은 시스템 스택에 삽입(push)됩니다.
• 함수 실행 종료:
  • 함수의 실행이 완료되면, 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장된 복귀 주소를 확인합니다.
  • 복귀 주소를 이용하여 호출한 지점으로 복귀합니다.
• 전체 프로그램 종료:
  • 모든 함수 호출과 복귀가 완료되면, 시스템 스택은 공백 상태가 됩니다.

>> 수식의 괄호 검사와 후위 표기법 

• 괄호 검사:
  • 괄호 검사는 후입선출 구조의 스택을 사용하여 수행합니다.
    • 왼쪽 괄호: 스택에 삽입(push)합니다.
    • 오른쪽 괄호: 스택에서 왼쪽 괄호를 꺼내어야 합니다. 만약 스택이 비어있거나 올바른 왼쪽 괄호가 없으면 괄호가 잘못된 것입니다.
    • 수식이 끝나면: 스택이 비어 있어야 하며, 비어 있지 않으면 괄호가 맞지 않는 것입니다.
• 후위 표기법(Postfix Notation):
  • 후위 표기법은 연산자를 피연산자 뒤에 표기하는 방법입니다. 중위 표기법을 후위 표기법으로 변환하기 위해 스택을 사용합니다.
    1. 왼쪽 괄호: 스택에 삽입합니다.
    2. 피연산자: 출력합니다.
    3. 연산자: 스택에 삽입합니다. 스택에 있는 연산자들 중 우선순위가 높은 것을 먼저 출력합니다.
    4. 오른쪽 괄호: 스택에서 연산자를 꺼내어 출력합니다. 왼쪽 괄호는 무시합니다.
    5. 수식이 끝나면: 스택에 남아 있는 모든 연산자를 꺼내어 출력합니다.

후위 표기법 변환 알고리즘 예제:

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    postfix = ''
    
    for char in expression:
        if char.isalnum():  # 피연산자는 출력
            postfix += char
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                postfix += stack.pop()
            stack.pop()  # '(' 제거
        else:  # 연산자
            while stack and stack[-1] in precedence and precedence[char] <= precedence[stack[-1]]:
                postfix += stack.pop()
            stack.append(char)
    
    while stack:
        postfix += stack.pop()
    
    return postfix

# 예시 사용
infix_expr = "A+B*C"
print(infix_to_postfix(infix_expr))  # 출력: "ABC*+"

>> 큐의 개념과 특징 

• 큐는 선입선출(First-In, First-Out, FIFO) 원칙을 따르는 자료구조로, 특정 순서로 삽입된 데이터가 먼저 삭제됩니다. 큐의 개념과 특징은 다음과 같습니다:
  1. 순서 유지: 큐는 데이터가 삽입된 순서대로 삭제됩니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.
  2. 삽입과 삭제 위치: 큐는 한쪽 끝(Rear)에서 데이터가 삽입되고, 반대쪽 끝(Front)에서 데이터가 삭제됩니다.
  3. 비교: 스택과 비슷하지만, 스택은 후입선출(Last-In, First-Out, LIFO) 방식으로, 큐는 선입선출 방식으로 동작합니다.

>> 순차 큐의 구현 

• 순차 큐는 1차원 배열을 사용하여 구현됩니다.
• 배열 크기: 큐의 크기는 배열의 크기와 같습니다.
• 변수:
  • front: 큐의 첫 번째 원소의 인덱스를 저장합니다.
  • rear: 큐의 마지막 원소의 인덱스를 저장합니다.
• 상태 표현:
  • 초기 상태: front = rear = -1
  • 공백 상태: front = rear
  • 포화 상태: rear = n-1 (여기서 n은 배열의 크기입니다.)

>> 원형 큐의 구현 

• 원형 큐는 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하여 사용합니다. 원형 큐는 순차 큐의 포화 상태 문제를 해결합니다.
• 구조:
  • 초기 공백 상태: front = rear = 0
  • 포인터 이동: front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음 자리인 인덱스 0으로 이동할 때는 나머지 연산자 %를 사용합니다.
    • 예: 3 % 4 = 3
• 사용 조건: 공백 상태와 포화 상태를 구분하기 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈 자리로 둡니다.

•  

>> 원형 큐의 장점 

• 효율성: 큐의 공간을 더 효율적으로 사용할 수 있습니다. 원형 큐는 배열의 끝과 시작이 연결되어 있어, 배열의 공간이 낭비되지 않습니다.
• 문제 해결: 순차 큐에서 발생할 수 있는 포화 상태 문제를 해결합니다.

>> 연결 큐의 이해와 구현 

• 연결 큐의 개념
  • 연결 큐(Linked Queue): 단순 연결 리스트를 이용하여 큐를 구현한 구조입니다. 큐는 FIFO(First-In-First-Out) 방식으로 원소가 삽입된 순서대로 삭제됩니다.
• 연결 큐의 구현
  • 큐의 원소: 단순 연결 리스트의 노드로 구성됩니다.
  • 큐의 원소의 순서: 노드의 링크 포인터로 연결되어 있습니다.
  • 변수:
    • front: 큐의 첫 번째 노드를 가리키는 포인터 변수입니다.
    • rear: 큐의 마지막 노드를 가리키는 포인터 변수입니다.
• 상태 표현:
  • 초기 상태와 공백 상태: front = rear = None (큐가 비어있는 상태)
• 연산:
  • Enqueue (삽입):
    1. 새로운 노드를 생성하고 데이터를 저장합니다.
    2. rear의 링크 포인터를 새 노드로 설정합니다.
    3. rear 포인터를 새 노드를 가리키도록 업데이트합니다.
    4. 공백 상태일 때는 front도 새 노드를 가리키도록 설정합니다.
  • Dequeue (삭제):
    1. 공백 상태를 확인합니다.
    2. front 포인터가 가리키는 노드를 삭제하고, front를 다음 노드를 가리키도록 업데이트합니다.
    3. 큐가 비어있다면 rear도 None으로 설정합니다.

코드 예제 (Python):

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.rear is None:  # 큐가 비어 있을 때
            self.front = new_node
        else:
            self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:  # 큐가 비어 있을 때
            print("Queue underflow")
            return None
        value = self.front.value
        self.front = self.front.next
        if self.front is None:  # 큐가 비어 있으면
            self.rear = None
        return value

# 예시 사용
q = LinkedQueue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())  # 출력: 10
print(q.dequeue())  # 출력: 20
print(q.dequeue())  # 출력: Queue underflow

>> 데크의 개념과 구현 

• 데크의 개념
  • 데크(Deque, Double-Ended Queue): 큐의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. 큐의 양쪽 끝에서 연산을 수행할 수 있도록 확장된 형태입니다.
• 데크의 구현
  • 구현 방법: 양방향으로 연산이 가능한 이중 연결 리스트를 사용합니다. 이중 연결 리스트는 노드가 앞과 뒤로 연결되어 있어 양쪽 끝에서 연산이 가능합니다.
• 연산:
  • 삽입 연산 (양쪽 끝):
    • Front 삽입: 새 노드를 생성하고 front 포인터의 이전 노드와 연결합니다. front를 새 노드로 업데이트합니다.
    • Rear 삽입: 새 노드를 생성하고 rear 포인터의 다음 노드와 연결합니다. rear를 새 노드로 업데이트합니다.
  • 삭제 연산 (양쪽 끝):
    • Front 삭제: front 포인터가 가리키는 노드를 삭제하고 front를 다음 노드로 업데이트합니다.
    • Rear 삭제: rear 포인터가 가리키는 노드를 삭제하고 rear를 이전 노드로 업데이트합니다.

코드 예제 (Python):

class DequeNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None

    def append_front(self, value):
        new_node = DequeNode(value)
        if self.front is None:
            self.front = new_node
            self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node

    def append_rear(self, value):
        new_node = DequeNode(value)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            new_node.prev = self.rear
            self.rear.next = new_node
            self.rear = new_node

    def pop_front(self):
        if self.front is None:
            print("Deque underflow")
            return None
        value = self.front.value
        self.front = self.front.next
        if self.front is not None:
            self.front.prev = None
        else:
            self.rear = None
        return value

    def pop_rear(self):
        if self.rear is None:
            print("Deque underflow")
            return None
        value = self.rear.value
        self.rear = self.rear.prev
        if self.rear is not None:
            self.rear.next = None
        else:
            self.front = None
        return value

# 예시 사용
d = Deque()
d.append_rear(10)
d.append_front(20)
print(d.pop_front())  # 출력: 20
print(d.pop_rear())   # 출력: 10
print(d.pop_front())  # 출력: Deque underflow

>> 큐의 응용 

• 프린터 버퍼 큐 (Printer Buffer Queue): CPU에서 프린터로 전송된 데이터를 순서대로 프린터에서 출력하기 위해 사용됩니다. 큐의 선입선출(FIFO) 구조를 활용하여 데이터를 관리합니다.
• 스케줄링 큐 (Scheduling Queue): CPU 사용을 요청한 프로세서들의 순서를 스케줄링 하기 위해 사용됩니다. 큐를 사용하여 프로세서의 실행 순서를 관리합니다.
• 시뮬레이션 큐잉 시스템: 대기행렬과 대기시간 등을 모델링하기 위해 큐잉 이론(Queue theory)을 사용합니다. 시뮬레이션에서 다양한 시스템의 동작을 분석할 때 유용합니다.

>> 트리의 개념 

• 트리의 정의
  • 트리(Tree): 원소들 간에 1관계를 가지는 비선형 자료구조입니다. 각 원소는 계층 구조를 가지며, 상위 원소에서 하위 원소로 확장되는 트리 모양을 하고 있습니다.
• 주요 특징
  • 계층형 자료구조: 원소들이 계층적으로 구성되어 있으며, 각 노드는 상위 노드와 하위 노드 간의 관계를 가집니다.
  • 비선형 구조: 노드 간의 관계가 선형이 아니라 계층적인 구조를 가지며, 일반적으로 트리의 형태는 뿌리(root)에서 시작하여 잎(leaf)으로 확장됩니다.

>> 이진 트리의 이해와 종류 

• 일반적인 이진 트리
  • 이진 트리(Binary Tree): 모든 노드가 최대 두 개의 자식 노드만을 가질 수 있는 트리입니다.
  • 차수: 각 노드의 차수는 0, 1, 또는 2입니다. 차수는 자식 노드의 수를 의미합니다.
  • 노드의 구성: 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만을 가집니다.
  • 공백 노드: 노드가 없는 곳에도 공백 노드를 추가하여 구조를 완전하게 유지할 수 있습니다.
• 이진 트리의 종류
  1. 포화 이진 트리 (Full Binary Tree):
     • 정의: 모든 레벨이 완전히 채워진 이진 트리입니다.
     • 특징: 높이 hhh일 때 최대 2h+1−12^{h+1} - 12h+1−1개의 노드를 가집니다.
  2. 완전 이진 트리 (Complete Binary Tree):
     • 정의: 높이 hhh이고 노드 수 nnn개를 가지며, 노드의 위치가 포화 이진 트리에서의 노드 1번부터 nnn번까지의 위치와 일치합니다.
     • 특징: 노드가 왼쪽에서 오른쪽으로 채워지는 형태를 가집니다.
  3. 편향 이진 트리 (Skewed Binary Tree):
     • 정의: 모든 노드가 왼쪽 또는 오른쪽으로만 자식 노드를 가지는 트리입니다.
     • 특징: 높이 hhh일 때 h+1h+1h+1개의 노드를 가집니다. 모든 자식 노드가 한쪽 방향으로만 치우쳐 있습니다.

>> 순차 및 연결 자료구조를 이용한 이진 트리 구현 

• 순차 자료구조를 이용한 이진 트리 구현
• 배열 기반 이진 트리:
  • 설명: 1차원 배열을 사용하여 이진 트리를 구현합니다. 각 노드는 배열의 인덱스로 표현됩니다.
  • 구성:
    • 인덱스 0: 비워둡니다 (일반적으로 배열 인덱스 1부터 사용).
    • 인덱스 1: 루트 노드.
    • 인덱스 iii: 부모 노드. 왼쪽 자식 노드는 2i2i2i, 오른쪽 자식 노드는 2i+12i + 12i+1로 인덱싱됩니다.

코드 예제 (Python):

class ArrayBinaryTree:
    def __init__(self, size):
        self.tree = [None] * size
        self.size = size
    
    def insert(self, index, value):
        if index < self.size:
            self.tree[index] = value
    
    def get_left_child_index(self, index):
        return 2 * index
    
    def get_right_child_index(self, index):
        return 2 * index + 1

# 예시 사용
bt = ArrayBinaryTree(10)
bt.insert(1, 'A')  # 루트 노드
bt.insert(2, 'B')  # 왼쪽 자식
bt.insert(3, 'C')  # 오른쪽 자식
print(bt.tree)  # 출력: [None, 'A', 'B', 'C', None, None, None, None, None, None]

• 연결 자료구조를 이용한 이진 트리 구현
• 포인터 기반 이진 트리:
  • 설명: 각 노드는 데이터 필드와 왼쪽, 오른쪽 자식 노드를 연결하는 포인터를 가집니다.
  • 구성:
    • 데이터 필드: 노드의 값을 저장합니다.
    • 왼쪽 링크 필드: 왼쪽 자식 노드를 가리킵니다.
    • 오른쪽 링크 필드: 오른쪽 자식 노드를 가리킵니다.
    • 자식 노드가 없으면 링크 필드에 NULL을 저장합니다.

코드 예제 (Python):

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class LinkedBinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert(node.right, value)

# 예시 사용
bt = LinkedBinaryTree()
bt.insert(10)
bt.insert(5)
bt.insert(15)

>> 이진 트리 순회의 개념 

• 이진 트리 순회는 모든 노드를 중복 없이 빠짐없이 방문하는 연산입니다. 각 노드를 방문하고 처리하는 방식에 따라 여러 종류의 순회 방법이 있습니다. 이진 트리 순회의 기본 작업은 다음과 같습니다:
  • D (현재 노드 방문 처리): 현재 노드를 처리하는 작업
  • L (왼쪽 서브 트리로 이동): 현재 노드의 왼쪽 자식 노드로 이동하는 작업
  • R (오른쪽 서브 트리로 이동): 현재 노드의 오른쪽 자식 노드로 이동하는 작업

>> 이진 트리 순회 방법 

• 전위 순회 (Pre-order Traversal)
  • 순서: D → L → R
  • 설명: 현재 노드를 방문한 후, 왼쪽 서브 트리로 이동하고, 그 다음 오른쪽 서브 트리로 이동합니다.
  • 특징: 루트 노드가 가장 먼저 처리됩니다. 이 순회 방법은 트리의 구조를 우선적으로 고려합니다.

예시 (Python):

def pre_order_traversal(node):
    if node:
        print(node.value, end=' ')
        pre_order_traversal(node.left)
        pre_order_traversal(node.right)

• 중위 순회 (In-order Traversal)
  • 순서: L → D → R
  • 설명: 왼쪽 서브 트리로 이동한 후 현재 노드를 방문하고, 오른쪽 서브 트리로 이동합니다.
  • 특징: 노드가 정렬된 순서로 방문됩니다. 이 방법은 이진 탐색 트리에서 원소를 정렬된 순서로 처리할 때 유용합니다.

예시 (Python):

def in_order_traversal(node):
    if node:
        in_order_traversal(node.left)
        print(node.value, end=' ')
        in_order_traversal(node.right)

• 후위 순회 (Post-order Traversal)
  • 순서: L → R → D
  • 설명: 왼쪽 서브 트리로 이동하고, 오른쪽 서브 트리로 이동한 후 현재 노드를 방문합니다.
  • 특징: 현재 노드가 가장 마지막에 처리됩니다. 주로 트리의 노드를 삭제하거나, 트리 구조의 최종 상태를 처리할 때 사용됩니다.

예시 (Python):

def post_order_traversal(node):
    if node:
        post_order_traversal(node.left)
        post_order_traversal(node.right)
        print(node.value, end=' ')

>> 이진 트리 순회의 응용 

1. 폴더 용량 계산
   • 설명: 컴퓨터의 폴더 구조가 이진 트리 형태일 때, 전위 순회를 사용하여 각 폴더를 순회하면서 폴더의 용량을 합산할 수 있습니다. 이는 전체 용량을 계산하는 데 유용합니다.
2. 스레드 이진 트리 (Threaded Binary Tree)
   • 설명: 재귀 호출 없이 순회할 수 있도록 수정한 이진 트리입니다. 재귀 호출의 깊이 문제를 해결하기 위해 사용됩니다. 일반적인 이진 트리에서는 재귀 호출이 스택을 사용하므로 깊이가 깊어질수록 비효율적일 수 있습니다.
   • 특징: 노드에 스레드를 추가하여 순회 시 부모 노드와 자식 노드 간의 링크를 쉽게 따라갈 수 있도록 합니다.

예시 (Python):

class ThreadedTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.is_threaded = False

def threaded_in_order_traversal(root):
    current = root
    while current:
        while current.left and not current.is_threaded:
            current = current.left
        print(current.value, end=' ')
        if current.right:
            current = current.right
        else:
            while current and not current.right:
                current = current.right