스택, 큐, 트리 직접 구현해보기

최근에 면접을 봤는데 스택과 큐의 차이에 대해서 질문이 들어왔다. 스택은 LIFO, 큐는 FIFO 이라고 말했다. 직접 구현해본 경험이 있냐는 질문에 있다고 했지만 더 설명하지 못 한 것이 후회되서 몇 자 적는다.

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

>> 스택, 큐, 트리 차이 

 스택 (Stack) 

• 후입선출(LIFO, Last-In-First-Out) 방식의 자료구조
  • 마지막에 추가된 요소가 가장 먼저 제거되는 구조
• 주요 연산
  • Push: 스택의 맨 위에 요소를 추가
  • Pop: 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환
  • 함수 호출, 괄호 매칭, 역순 문자열 생성 등의 알고리즘에서 사용
• 사용 예시
  • 뒤로가기: 실재로 두 번의 프로젝트에서 페이지를 이동 할 때마다 stack에 넣었고 뒤로가기를 누르면 stack의 마지막 부분이 pop되기 때문에 -2번째 인덱스의 페이지가 불러오도록 구현하였다.
  • 함수 호출, 괄호 매칭, 역순 문자열 생성 등의 알고리즘에서 사용

 큐 (Queue) 

• 선입선출(FIFO, First-In-First-Out) 방식의 자료구조
  • 이는 첫 번째로 추가된 요소가 가장 먼저 제거되는 구조
• 주요 연산
  • Enqueue: 큐의 끝에 요소를 추가
  • Dequeue: 큐의 앞에서 요소를 제거하고 그 값을 반환
• 사용 예시
  • 줄 서기: AI 기반 손글씨 제작 서비스에서 먼저 손글씨 제작을 요청한 사람이 먼저 제작이 될 수 있도록 구현하였다. 나중에 온 사람들은 그 뒤로 쌓이게 되며 앞에서 부터 차례대로 손글씨가 제작된다.  
  • 큐는 작업 스케줄링, 캐시 구현, 너비 우선 탐색(BFS) 알고리즘 등에 사용됩니다.

 트리 (Tree) 

• 계층적 관계
  • 비선형 자료구조이다.
• 노드(Node)들로 구성
  • 각 노드는 부모-자식 관계
  • 가장 상위 노드를 루트(Root) 노드
  • 루트 노드에서부터 시작하여 가지(branch)를 따라 내려가며 노드들을 탐색할 수 있다. 
  • 각 노드는 여러 자식 노드를 가질 수 있지만, 하나의 부모 노드만을 가질 수 있다(단방향).
  • 사이클(순환 구조)이 존재하지 않는다.
• 다양한 유형의 트리(이진 트리, AVL 트리, 레드-블랙 트리 등)가 있으며, 각각 특정 애플리케이션에 최적화되어 있다.
• 사용 예시
• 트리는 파일 시스템, 데이터베이스 인덱싱, HTML 문서의 DOM 구조 등에 사용됩니다.

>> 스택 구현하기 

# 스택 초기화
lastIndex = -1
size = 10
stack = [0 for _ in range(size)]

def newPush(element):
    global lastIndex

    if lastIndex == size:
        print("오버플로우")
        return
    lastIndex += 1
    stack[lastIndex] = element
    return

def newPop():
    global lastIndex
    if lastIndex == -1:
        print("언더플로우")
        return
    lastIndex -= 1
    return stack[lastIndex+1]

print("stack:", stack)

print("push:", end=" ")
for num in range(size):
    newPush(num+1)
    print(num+1, end=" ")
print()

print("stack:", stack)

print("pop:", end=" ")
for _ in range(size):
    print(newPop(), end=" ")
print()

• 출력

stack: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] push: 1 2 3 4 5 6 7 8 9 10  stack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] pop: 10 9 8 7 6 5 4 3 2 1

>> 큐 구현하기 

circle Q : size(필요한 저장 공간의 크기) + 1

size = 10
# +1을 해서 빈 공간을 만든다.
qSize = size + 1
circleQ = [0 for _ in range(qSize)]
# 시작 지점을 만든다.
left = right = 0

def fullQ():
    return (left + 1) % (qSize) == left

def enqueue(element):
    global right
    if fullQ():
        print("오버플로우")
        return
    right = (right + 1) % qSize
    circleQ[right] = element

def emptyQ():
    return left == right

def dequeue():
    global left
    if emptyQ():
        print("언더플로우")
        return
    left = (left + 1) % qSize
    return circleQ[left]

print("circleQ:", circleQ)
print("enqueue:", end=" ")
for num in range(size):
    enqueue(num+1)
    print(num+1, end=" ")
print()
print("circleQ:", circleQ)

print("dequeue:", end=" ")
for _ in range(size):
    print(dequeue(), end=" ")
print()

• 출력

circleQ: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] enqueue: 1 2 3 4 5 6 7 8 9 10  circleQ: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] dequeue: 1 2 3 4 5 6 7 8 9 10

 

line Q

size = 10
lineQ = [0 for _ in range(size)]
left = right = -1
def fullQ():
    return right == size - 1

def enqueue(element):
    global right
    if fullQ():
        print("오버플로우")
        return
    right += 1
    lineQ[right] = element
    return

def emptyQ():
    return left == right

def dequeue():
    global left
    if emptyQ():
        print("언더플로우")
        return
    left += 1
    return lineQ[left]

print("lineQ:", lineQ)
print("enqueue:", end=" ")
for num in range(size):
    enqueue(num+1)
    print(num+1, end=" ")
print()
print("lineQ:", lineQ)

print("dequeue:", end=" ")
for _ in range(size):
    print(dequeue(), end=" ")
print()

• 출력

lineQ: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] enqueue: 1 2 3 4 5 6 7 8 9 10  lineQ: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] dequeue: 1 2 3 4 5 6 7 8 9 10

>> 트리 구현하기 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

A = Node("A")
B = Node("B")
C = Node("C")

root = A
A.left = B
A.right = C

print("정점 노드:", A.data)
print("왼쪽 자식 노드:", A.left.data)
print("오른쪽 자식 노드:", A.right.data)

 

     A
    /  \
  B    C

• 출력

정점 노드: A 왼쪽 자식 노드: B 오른쪽 자식 노드: C

 

트리 순회

n = 13
tree = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6, 4, 7, 5, 8, 5, 9, 6, 10, 6, 11, 7, 12, 11, 13]

# 인덱스가 부모노드의 번호
nodeLeft = [0] * (n + 1)
nodeRight = [0] * (n + 1)

for i in range(n-1):
    p = tree[i*2]
    c = tree[i*2+1]
    if nodeLeft[p] == 0:
        nodeLeft[p] = c
    else:
        nodeRight[p] = c

for p in range(n):
    if p:
        print(f"{p}번", end=" ")
    else:
        print("정점", end=" ")
print()
print(nodeLeft)
print(nodeRight)

# 1. 전위순회 preorder V - L - R
def preorder(pNode):
    # t 노드가 존재한다면
    if pNode:
        # 데이터 처리(print)
        print(pNode, end=" ")
        # 왼쪽 방문
        preorder(nodeLeft[pNode])
        # 오른쪽 방문
        preorder(nodeRight[pNode])


# 2. 중위순회 inorder L - V - R
def inorder(pNode):
    if pNode:
        # 왼쪽 방문
        inorder(nodeLeft[pNode])
        # 데이터 처리(print)
        print(pNode, end=" ")
        # 오른쪽 방문
        inorder(nodeRight[pNode])


# 3. 후위순회 postorder L - R - V
def postorder(pNode):
    # t 노드가 존재한다면
    if pNode:
        # 왼쪽 방문
        postorder(nodeLeft[pNode])
        # 오른쪽 방문
        postorder(nodeRight[pNode])
        # 데이터 처리(print)
        print(pNode, end=" ")


print("전위순회(preorder):", end=" ")
preorder(1)
print()

print("중위순회(indorder):", end=" ")
inorder(1)
print()

print("후위순회(postorder):", end=" ")
postorder(1)
print()

• 출력

정점 1번 2번 3번 4번 5번 6번 7번 8번 9번 10번 11번 12번  [0, 2, 4, 5, 7, 8, 10, 12, 0, 0, 0, 13, 0, 0] [0, 3, 0, 6, 0, 9, 11, 0, 0, 0, 0, 0, 0, 0] 전위순회(preorder): 1 2 4 7 12 3 5 8 9 6 10 11 13  중위순회(indorder): 12 7 4 2 1 8 5 9 3 10 6 13 11  후위순회(postorder): 12 7 4 2 8 9 5 10 13 11 6 3 1

 

>> 세 줄 정리 

• 스택은 LIFO 방식으로, 가장 나중에 들어온 요소가 가장 먼저 나가는 구조다.
• 큐는 FIFO 방식으로, 가장 먼저 들어온 요소가 가장 먼저 나가는 구조다.
• 트리는 계층적 구조를 가지며, 노드 간에 부모-자식 관계를 통해 다양한 데이터 관계를 표현할 수 있다.