프로그래밍의 예술 - 스택과 큐

목차

1. 스택(Stack)이란?
2. 스택의 동작 원리
3. 스택의 구현 방법
4. 스택의 장단점
5. 큐(Queue)란?
6. 큐의 동작 원리
7. 큐의 구현 방법
8. 큐의 장단점
9. 스택과 큐의 활용 예시
10. 결론

스택(Stack)이란?

📌 스택(Stack) 은 컴퓨터 과학에서 사용되는 데이터 구조 중 하나로, 데이터 요소를 일시적으로 저장하고 접근하는 데 사용됩니다. 스택은 후입선출(LIFO, Last-In-First-Out)라는 원칙에 따라 동작하며, 최신 요소가 항상 맨 위에 위치하고 이 요소에만 접근할 수 있습니다. 스택은 간단하면서도 많은 프로그래밍 상황에서 유용하게 활용될 수 있습니다.

스택의 동작 원리

📌 스택은 세 가지 기본 동작을 수행할 수 있습니다:

1. Push: 스택에 데이터 요소를 추가합니다. 새로운 요소는 스택의 맨 위에 위치하게 됩니다.
2. Pop: 스택에서 맨 위에 있는 데이터 요소를 삭제합니다. 삭제된 요소는 반환됩니다.
3. Top: 스택의 맨 위에 있는 데이터 요소를 확인합니다. 삭제되지 않고 그대로 유지됩니다.

스택의 구현 방법

📌 스택은 배열이나 연결 리스트로 구현할 수 있습니다. 배열 구현 방식을 사용하면 정적 크기의 스택을 생성할 수 있으며, 연결 리스트 구현 방식을 사용하면 동적 크기의 스택을 생성할 수 있습니다.

배열을 사용한 스택 구현 예시

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if self.is_empty():
            return None
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

연결 리스트를 사용한 스택 구현 예시

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return None
        popped_item = self.top.data
        self.top = self.top.next
        return popped_item

    def top(self):
        if self.is_empty():
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

스택의 장단점

👍 장점:

• 간단한 구조로 구현이 쉽고 이해하기 쉽습니다.
• 데이터를 후입선출 방식으로 처리할 수 있어 필요한 데이터에 빠르게 접근할 수 있습니다.
• 재귀 알고리즘, 괄호 매칭, 웹 브라우저에서의 뒤로가기 등 다양한 상황에서 유용하게 활용될 수 있습니다.

👎 단점:

• 스택 크기가 고정되어 있을 경우, 스택 용량을 초과하는 데이터를 넣을 수 없습니다.
• 데이터 요소를 중간에 삽입하거나 삭제할 수 없습니다.

큐(Queue)란?

📌 큐(Queue) 는 스택과 마찬가지로 데이터 구조 중 하나로, 데이터 요소를 일시적으로 저장하고 접근하는 데 사용됩니다. 큐는 선입선출(FIFO, First-In-First-Out)라는 원칙에 따라 동작하며, 먼저 들어온 요소가 먼저 처리되는 순서를 가지고 있습니다. 큐는 데이터가 들어올 때는 뒤로 추가되고, 데이터가 처리될 때는 앞에서부터 삭제됩니다.

큐의 동작 원리

📌 큐는 두 가지 기본 동작을 수행할 수 있습니다:

1. Enqueue: 큐에 데이터 요소를 추가합니다. 새로운 요소는 큐의 뒤에 위치하게 됩니다.
2. Dequeue: 큐에서 맨 앞에 있는 데이터 요소를 삭제합니다. 삭제된 요소는 반환됩니다.

큐의 구현 방법

📌 큐는 배열이나 연결 리스트로 구현할 수 있습니다. 배열 구현 방식을 사용하면 정적 크기의 큐를 생성할 수 있으며, 연결 리스트 구현 방식을 사용하면 동적 크기의 큐를 생성할 수 있습니다.

배열을 사용한 큐 구현 예시

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.queue.pop(0)

    def front(self):
        if self.is_empty():
            return None
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

연결 리스트를 사용한 큐 구현 예시

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

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

    def enqueue(self, item):
        new_node = Node(item)
        if self.is_empty():
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.is_empty():
            return None
        dequeued_item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued_item

    def front(self):
        if self.is_empty():
            return None
        return self.front.data

    def is_empty(self):
        return self.front is None

큐의 장단점

👍 장점:

• 데이터를 선입선출 방식으로 처리할 수 있어 작업이 순차적으로 진행되어야 할 때 유용합니다.
• 빠른 데이터 접근 및 처리 속도를 제공합니다.
• 추적 작업, 프로세스 관리, 네트워크 패킷 처리 등 다양한 상황에서 유용하게 활용될 수 있습니다.

👎 단점:

• 크기가 고정된 배열을 사용하는 경우, 큐의 용량을 초과하는 데이터를 넣을 수 없습니다.
• 데이터 요소를 중간에 삽입하거나 삭제할 수 없습니다.