[4주차] 스택과 큐

[thgr8ganzi]

고고입니다.

[thgr8ganzi]

정리

• 스택과 큐를 연결리스트와, 배열로 나눠서 생각한게 흥미로웠어요
• 개인적으로 그래프 라는걸 잘 모르는데 이책을 공부하면서 미지의 세계를 알아가는것 같아서 좋았어요. 알고리즘 문제 나오면 풀수 있을것같아요!

[ainochi-kor]

정리

• 스택과 큐를 LIFO와 FIFO 형식으로 설명해서 코드로 풀어줄 때 좋았습니다. 인덱스가 배열의 끝을 넘어가는 것에 도달하면 어떻게 해결할지 의문을 주어서 어떤 방법으로 처리하면 좋을지 생각만 해보았네요.
• 스택과 큐가 중요한 이유에서 어떤 데이터 특성에 사용하면 좋을지 좋았습니다.

[ella-yschoi]

정리

• 저도 스택과 큐를 연결리스트/배열로 나누어 생각할 수 있어 좋았습니다.
• DFS는 '스페셜리스트'처럼 특정 경로를 깊이 탐색하고, BFS는 '제너럴리스트'처럼 여러 경로를 얕게 탐색한다고 느꼈습니다.

2024년 잘 마무리하시고 2025년에도 화이팅입니당! 😊

[yunseorim1116]

‘자료구조를 효과적으로 사용하고 싶을 때 효율성만 유일한 고려 대상인 것은 아니다.
선택한 자료구조의 속성이 알고리즘의 동작에 어떤 영향을 미칠지 고려해야 한다.

라는 문장이 가장 와닿았습니다.
역시 잘 사용하려면 이론도 잘 알아야...

정리

[ddongule]

2024년이 벌써 다 갔네요!!!!!!!!!!!!!!!!! 다들 해피뉴이어 되세요!!!!!!!!!!!!!!!!

연결리스트로 스택, 큐를 구현하는게 흥미로웠어요
이 저자가 이 책을 통해 말하고자 하는 바가 필요한 상황에 맞춘 자료구조를 잘 찾자..라는게 이번 챕터에서도 도드라졌던 것 같아요.
정리는 잠시 나갔다와서 올리겠습니다. 허헛

[sa02045]

기본 자료구조인 스택/큐를 다시 리뷰할 수 있었습니다. 곧 2025년이네요 해피뉴이어~ 🎉
인상깊은 구절은

• 어떤 자료구조를 선택하느냐에 따라 알고리즘의 작동방식이 달라질 수 있다.
• 알고리즘에 대한 자료구조를 선택할 때, 선택한 자료구조의 속성이 알고리즘 동작에 어떤 영향을 미칠지 고려해야한다.

배열로 스택 구현, 연결리스트로 스택 구현방법
- 연결리스트로 구현하는 것이 약간의 비용(메모리)을 지불하는 대신 유연성을 얻을 수 있음
배열로 큐 구현, 연결리스트로 큐 구현방법

• 선입후출 스택은 깊이우선탐색과 연관, 선입선출 큐은 넓이우선탐색과 연관
• 스택 -> 프로그래밍 언어의 함수 호출처리할 때
• 큐 -> 네트워크 처리처럼 먼저들어온 요청을 처리할 때

[iborymagic]

• 스택 = 후입선출 → 깊이 우선 탐색(DFS)에 활용 = 한 경로를 깊이 들어가면서 막다른 길에 도달할 때까지 탐색
  • 스택의 pop은 배열의 끝에서만 항목을 추가하거나 제거하기 때문에 다른 원소를 이동할 필요 X
• 큐 = 선입선출 → 너비 우선 탐색(BFS)에 활용 = 더 깊이 파고 들어가기 전에 인접한 경로를 얕게 탐색
• 원소를 삽입/제거하는 순서는 알고리즘 동작에 큰 영향
  • 큐는 삽입 순서를 보존해야할 때 사용
  • 스택은 최근 항목을 먼저 처리할 때 사용
• 자료구조의 속성이 알고리즘에 어떤 영향을 끼치는지 고려해야함
  • 스택 → 큐로 전환하면 DFS → BFS로 전환할 수 있는 것처럼
• 스택과 큐 모두, 배열이나 연결리스트 모두로 구현 가능
  • 연결리스트로 구현하면 유연성 ↑
    • 데이터와 함께 커지거나 작아짐
    • 배열이 꽉차는 것에 대해 걱정할 필요 X
    • 배열 크기를 늘리는 추가 비용 지불 필요 X
  • 하지만 비용 효율 ↓
    • 포인터를 사용하므로 메모리 비용 증가

스택과 큐는 약간 수학의정석에 있는 집합같은 존재랄까요?
짧아서 좋았읍니다 허허

[chloe-codes1]

내용 정리

스택

• 배열로 스택 구현

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

  • 연산

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

생각

자료 구조의 특성을 잘 알고 쓰자!

해피 유희열~~

[hanana1253]

나 왜 스터디하는 거 까먹었냐.. 어쩐지 주말이 여유롭더라니..

스택과 큐

• 데이터가 저장된 순서에 따라 데이터를 읽어올 수 있는 자료 구조
  • 스택: 후입 선출 자료구조, push와 pop으로 추가/제거
  • 큐: 선입 선출 자료구조, enqueue와 dequeue로 추가/제거
• 순서의 중요성: 삽입 순서 보존에는 큐, 최근 항목 먼저 처리에는 스택
• 스택은 깊이우선탐색(depth-first-search), 큐는 너비우선탐색(breadth-first-search)
  • 깊이우선탐색(DFS)
    • 막다른 골목에 도달할 때까지 한 가지 경로를 진행하고, 막다른 골목에 도달하면 마지막으로 방문했던 분기로 돌아가 다음 가능성 확인
    • 스택을 사용해 앞으로 탐색해야 할 목록을 유지, 다음으로 시도할 대상으로 최근에 삽입한 가능성을 가장 먼저 선택
  • 너비우선탐색(BFS)
    • 큐를 사용해 미래의 가능성을 저장
    • 가장 오래 기다린 가능성을 탐색하며 더 깊은 단계를 탐색하기 전에 같은 깊이의 여러 다른 방향으로 뻗어나감
  • 한 번에 하나의 가능성만 탐색하므로 DFS, BFS 모두 동일한 속도로 작동

느낀점

간단하지만 중요한 내용들이 잘 들어있군.

[sunhpark42]

일주일 늦었지만 그래도 읽은거 인증합니다다~~