Chapter 4: 스택과 큐

내용 정리

스택

• 배열로 스택 구현

  • 배열은 동적으로 크기를 조정할 수 있지만, 메모리를 확장해야 할 경우 추가 비용이 발생할 수 있다

  • 연산

    • append()

      • 배열의 끝에 요소를 추가하며 빠르게 동작한다

    • pop()

      • 배열의 마지막 요소를 제거만 하면 되므로 간단하다

  • e.g.

    from typing import List
    
    class ArrayStack:
        def __init__(self) -> None:
            self.stack: List[int] = []
    
        def push(self, value: int) -> None:
            self.stack.append(value)
    
        def pop(self) -> int:
            if not self.stack:
                raise IndexError("Stack is empty")
            return self.stack.pop()
    
        def peek(self) -> int:
            if not self.stack:
                raise IndexError("Stack is empty")
            return self.stack[-1]

• 연결 리스트로 스택 구현

  • 연결 리스트는 동적으로 크기를 확장하거나 축소할 수 있어 배열 크기 제한 걱정 X

  • 연산

    • push()

      • 연결 리스트의 맨 앞에 새로운 노드를 추가한다

    • pop()

      • 맨 앞 노드를 제거하고 값을 반환한다

  • e.g.

    from typing import Optional
    
    class Node:
        def __init__(self, value: int) -> None:
            self.value: int = value
            self.next: Optional["Node"] = None
    
    class LinkedListStack:
        def __init__(self) -> None:
            self.head: Optional[Node] = None
    
        def push(self, value: int) -> None:
            new_node = Node(value)
            new_node.next = self.head
            self.head = new_node
    
        def pop(self) -> int:
            if not self.head:
                raise IndexError("Stack is empty")
            value = self.head.value
            self.head = self.head.next
            return value
    
        def peek(self) -> int:
            if not self.head:
                raise IndexError("Stack is empty")
            return self.head.value

큐

• 배열로 큐 구현

  • 큐는 배열의 append()와 pop(0)를 사용해 구현할 수 있다

  • but, pop(0)은 배열의 모든 요소를 앞으로 이동시키므로 비효율적!

  • e.g.

    from typing import List
    
    class ArrayQueue:
        def __init__(self) -> None:
            self.queue: List[int] = []
    
        def enqueue(self, value: int) -> None:
            self.queue.append(value)
    
        def dequeue(self) -> int:
            if not self.queue:
                raise IndexError("Queue is empty")
            return self.queue.pop(0)
    
        def peek(self) -> int:
            if not self.queue:
                raise IndexError("Queue is empty")
            return self.queue[0]

• 연결 리스트로 큐 구현

  • 연결 리스트는 동적으로 크기를 조정할 수 있으며, 큐의 머리(head)와 꼬리(tail)를 유지해 효율적으로 동작한다

  • 연산

    • enqueue()

      • tail에 노드를 추가한다

    • dequeue()는

      • head에서 노드를 제거한다

  • e.g.

    class LinkedListQueue:
        def __init__(self) -> None:
            self.head: Optional[Node] = None
            self.tail: Optional[Node] = None
    
        def enqueue(self, value: int) -> None:
            new_node = Node(value)
            if self.tail:
                self.tail.next = new_node
            self.tail = new_node
            if not self.head:
                self.head = self.tail
    
        def dequeue(self) -> int:
            if not self.head:
                raise IndexError("Queue is empty")
            value = self.head.value
            self.head = self.head.next
            if not self.head:
                self.tail = None
            return value
    
        def peek(self) -> int:
            if not self.head:
                raise IndexError("Queue is empty")
            return self.head.value

순서의 중요성

원소를 삽입하거나 제거하는 순서는 알고리즘 동작에 큰 영향을 미치므로 자료구조 선택은 중요하다

• DFS

  • 스택을 사용해 경로를 깊게 탐색하며, 한 경로를 끝까지 탐색한 뒤 돌아온다

  • e.g.

    from typing import Dict, List, Set
    
    def dfs(graph: Dict[str, List[str]], start: str) -> None:
        visited: Set[str] = set()
        stack: List[str] = [start]
    
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                print(node)
                for neighbor in graph.get(node, []):
                    stack.append(neighbor)

• BFS

  • 큐를 사용해 경로를 넓게 탐색하며, 같은 깊이의 모든 경로를 차례로 탐색한다

  • e.g.

    from collections import deque
    from typing import Dict, List, Set, Deque
    
    def bfs(graph: Dict[str, List[str]], start: str) -> None:
        visited: Set[str] = set()
        queue: Deque[str] = deque([start])
    
        while queue:
            node = queue.popleft()
            if node not in visited:
                visited.add(node)
                print(node)
                for neighbor in graph.get(node, []):
                    queue.append(neighbor)

스택과 큐가 중요한 이유

• 두 자료 구조는 모두 객체를 저장하고, 배열 or 연결 리스트로 구현 가능하고, 삽입 / 제거를 효율적으로 처리할 수 있다는 점이 동일하다

• but, 데이터 처리 방식에 있어서 차이가 난다

  • 스택은 저장된 최신 데이터를 반환하므로, 최근 항목을 처리해야할 때 GOOD

  • 큐는 저장된 가장 오래된 데이터를 반환하므로, 도착 순서대로 항목을 처리해야할 때 GOOD

• 자료 구조를 효과적으로 사용하고 싶을 때 효율성만 고려 해야 하는 것은 아니지만, 선택한 자료구조의 속성이 알고리즘에 어떤 영향을 미칠지 고려하자~~

생각

스택과 큐의 특성을 잘 알고 쓰자!