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

## 생각

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chloe-codes1.gitbook.io/book-reviews/data-structures-the-fun-way/04_-_.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.