> For the complete documentation index, see [llms.txt](https://chloe-codes1.gitbook.io/book-reviews/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chloe-codes1.gitbook.io/book-reviews/data-structures-the-fun-way/04_-_.md).

# Chapter 4: 스택과 큐

## 내용 정리

### 스택

* 배열로 스택 구현
  * 배열은 동적으로 크기를 조정할 수 있지만, 메모리를 확장해야 할 경우 추가 비용이 발생할 수 있다
  * 연산
    * `append()`
      * 배열의 끝에 요소를 추가하며 빠르게 동작한다
    * `pop()`
      * 배열의 마지막 요소를 제거만 하면 되므로 간단하다
  * e.g.

    ```python
    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.

    ```python
    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.

    ```python
    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.

    ```python
    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.

    ```python
    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.

    ```python
    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
* 자료 구조를 효과적으로 사용하고 싶을 때 효율성만 고려 해야 하는 것은 아니지만, 선택한 자료구조의 속성이 알고리즘에 어떤 영향을 미칠지 고려하자\~\~

## 생각

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