해당 게시물은 바킹독의 실전 알고리즘을 참고하여 작성하였습니다.
스택
스택: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
대충 프링글스 통을 생각하면 편하다.
스택은 구조적으로 먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조 라고 부르기도 한다.
성질로는
1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
스택은 특정 위치에서만 원소를 넣거나 뺄 수 있게 제한을 둔 대신 원소의 추가와 제거가 모두 O(1).
대신 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.
원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 따라서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아니다. 구현을 할 때, 배열을 기반으로 구현하여 해당 기능이 가능하도록 만들 수는 있긴 하다.
기능으로는
- 스택 내부의 데이터는 top을 통해서만 접근 가능하다
-> top은 가장 마지막에 들어온 데이터를 의미 - 스택에 데이터를 삽입할 때는 top 위에 삽입 => push
- 스택에서 데이터를 삭제할 때는 top에 위치한 데이터를 삭제 => pop
즉, 스택은 시간 순으로 데이터가 쌓이게 되므로 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 특징을 가진다.
활용으로는
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어줌
- 재귀함수를 빠져나와 백트래킹을 할 때 스택에 넣어두었던 임시 데이터를 빼줘야 함
- 스택은 이런 일련의 행위를 직관적으로 가능하게 해줌
- 또한 스택은 재귀 알고리즘을 iterative를 통해 구현할 수 있게 해줌
- 웹 브라우저 방문기록
- 가장 마지막에 열린 페이지부터 다시 보여줌. - 실행 취소
- 가장 마지막에 실행된 것부터 실행을 취소. - 역순 문자열 만들기
- 후위 표기법 계산
- 수식의 괄호 검사
큐
큐: 한 쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
스택에서는 먼저 들어간 원소가 나중에 나왔는데, 큐에서는 먼저 들어간 원소가 먼저 나오게 된다 -> FILO (First In Last Out)이라고 한 것과 비슷하게 FIFO (First In First Out)이라고 함.
성질로는
1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 앞/뒤의 원소 확인 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
큐에서 연산의 시간복잡도를 보면 스택처럼 원소의 추가와 제거가 모두 O(1)이다.
스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 제거되는 곳을 front, 즉 앞쪽이라고 한다.
4번 성질도 스택과 같은 맥락에서 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없으나, 배열을 가지고 직접 만들 땐 해당 기능이 가능하도록 구현가능하다.
활용으로는
- 버퍼: 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 데이터를 보관하는 메모리 영역으로 일반적으로 입출력 및 네트워크 관련 기능에서 이용함
- BFS
- 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용- 노드 하나를 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
- 노드를 접근할 순서대로 처리가능
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 프린터의 출력처리
- 프로세스 관리
- 캐시 구현
덱
덱은 Restricted Structure의 끝판왕이라는 자료구조인데, 양쪽 끝에서 삽입과 삭제 모두 가능하다. deque는 Double Ended Queue라는 뜻을 가지고 있으며, 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮다.
성질로는
1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 앞/뒤의 원소 확인 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
덱의 경우 파이썬에서 제공하는 collections의 라이브러리를 활용할 수 있다.
from collections import deque
mydeq = deque([1,2,3,4])
mydeq.appendleft(-10) # 왼쪽에 데이터 삽입
print(mydeq) # deque([-10, 1, 2, 3, 4])
mydeq.append(10) # 오른쪽에 데이터 삽입
print(mydeq) # deque([-10, 1, 2, 3, 4, 10])from collections import deque
mydeq = deque([1,2,3,4])
# 오른쪽에서 데이터 제거
print(mydeq.pop()) # 4
mydeq # deque([1, 2, 3])
# 왼쪽에서 데이터 제거
print(mydeq.popleft()) # 1
mydeq # deque([2, 3])덱(deque) 관련 파이썬 메서드
- append(item): item을 덱의 오른쪽에 삽입
- appendleft(item): Item을 덱의 왼쪽에 삽입
- pop(): 덱의 오른쪽 끝 요소를 반환하는 동시에 덱에서 제거
- popleft(): 덱의 왼쪽 끝 요소를 반환하는 동시에 덱에서 제거
- extend(list): 배열(list)을 순환하면서 덱의 오른쪽에 삽입
- extendleft(list): 배열(list)을 순환하면서 덱의 왼쪽에 추가
- remove(item): item을 덱에서 찾아 제거
- rotate(n): 덱의 n만큼 회전(양수일 경우 오른쪽, 음수일 경우 왼쪽)
