[알고리즘 개념] 선형 구조 - 스택, 큐, 덱

자료구조 중 선형구조 - 그 안에서도 스택 Stack, 큐 Queue, 덱 Deque에 대하여 정리해 보았다.

선형구조

• 데이터를 저장하는 기본 형태
• 일렬로 나열되어 있다.
• 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조이다.

1. 스택 stack

후입선출 (LIFO, Last In First Out) 구조를 가진 자료 구조
마지막에 들어온 자료부터 다시 꺼내 쓰게 되는 것으로, 한 방향에서만 데이터의 삽입과 삭제가 가능하다.

기본 연산

• push : 스택에 원소를 추가
• pop : 스택에 가장 마지막으로 들어온 원소를 제거하고 그 값을 반환
• peek : 스택에 가장 마지막으로 들어온 원소를 조회

# 예시) 주로 list로 구현된다.

stack = []
stack.append(3) # 3 push
stack.append(2) # 2 push
stack.append(5) # 5 push
stack.pop() # pop -> 5 가 제거됩니다
print(stack[-1]) # peek / python의 음수 인덱스를 활용

장단점

• 데이터의 삽입삭제, top 원소 접근 빠름 - O(1)
• 히스토리 역추적하기 좋음
• 탐색(접근)이 어려움 : 전체 원소를 pop 해가며 확인하는 방법 뿐
• index 접근이나 중간 데이터에 대한 수행이 어려움

사용 예시

• 재귀 함수 (알고리즘)
• 역추적 및 역실행 (실행취소, 문자열 뒤집기)
• DFS 탐색 (순서대로 전체를 탐색)
• 중간 데이터에 대한 작업이 아닌 한 방향 작업일 때

---

2. 큐 queue

선입선출 (FIFO, First In First Out) 구조를 가진 자료 구조
대기 줄과 같이 줄 선 순서대로 앞에서부터 진행된다.
(우선순위 큐와 원형큐라는 종류가 더 있고, 여기서는 선형큐에 대한 내용만 포함한다.)

기본 연산 _ 파이썬 collections.deque

• enqueue : 큐에 원소를 추가
• dequeue : 큐에 가장 먼저 들어온 원소를 제거하고 그 값을 반환
• peek : 큐에 가장 먼저 들어온 원소를 조회

# 예시) 파이썬의 큐의 기본 연산은 deque에서 지원하고 있음

from collections import deque

deck = deque()          # 신규 덱(큐) 생성 ([])
deck.append(1)          # 1 enqueue
deck.append(3)          # 3 enqueue
b = deck.popleft()      # dequeue -> 가장 먼저 들어온 1이 제거됩니다
print(b[0])             # peek

장단점

• 데이터의 삽입삭제 빠름 - O(1)
• 입력된 순서대로 데이터 처리할 때 좋음
• index 접근이나 중간 데이터에 대한 수행이 어려움

사용 예시

• 입력 순서에 따른 데이터 처리
• BFS 탐색 (가까운 노드부터 탐색)

---

3. 덱 deque

양방향에서 데이터 조작을 할 수 있는 자료구조, 스택 + 큐 라고 생각하면 편하다.

기본 연산_파이썬 collections.deque

• append : 오른쪽 끝에 원소 추가
• appendleft : 왼쪽 끝에 원소 추가
• pop : 오른쪽 끝 원소 제거 후 값 반환
• popleft : 왼쪽 끝 원소 제거 후 값 반환

from collections import deque

deck = deque()          # 신규 데크 생성 ([])
deck.append(1)          # 오른쪽 끝에 1을 삽입 ([1])
deck.appendleft(2)      # 왼쪽 끝에 2를 삽입 ([2, 1])
deck.append(3)          # 오른쪽 끝에 3을 삽입 ([2, 1, 3])
a = deck.pop()          # 오른쪽 끝에서 삭제 후 a에 그 값을 저장 ([2, 1])
print(a)                # 3
b = deck.popleft()      # 왼쪽 끝에서 삭제 후 b에 그 값을 저장 ([1])
print(b)                # 2

장단점

• 데이터의 삽입삭제 빠름 - O(1)
• index 접근하여 처리 가능함
• 중간에서의 삽입 삭제는 어려움

사용 예시

• 회문 판별 (어느 방향에서 읽든 동일한 문자열을 확인할 때)
• 앞 뒤에서 삽입,삭제를 해야할 때

---

자료
[자료구조] 2. 스택(Stack)과 큐(Queue), 덱(Deque)
스택, 큐, 덱 정리 (Stack / Queue / Deque)
[Java/자료구조] 선형구조 - 큐(Queue), 스택(Stack), 덱(Deque) 이해하기 - 1
[알고리즘] 자료구조 개념 / 스택, 큐, 덱, 힙 ( Stack, Queue, Deque, Heap)