배열은 동적으로 크기를 조정할 수 있지만, 메모리를 확장해야 할 경우 추가 비용이 발생할 수 있다
연산
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
자료 구조를 효과적으로 사용하고 싶을 때 효율성만 고려 해야 하는 것은 아니지만, 선택한 자료구조의 속성이 알고리즘에 어떤 영향을 미칠지 고려하자~~