스텍, 큐, 덱 이란?
- 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료 구조 이다.
- (배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 거내는 연산이 제공 된다.
- 그러나, 매우 제한적인 규칙 (LIFO, FIFO) 등을 따른다.
스택(Stack) : LIFO - 후입 선출
- 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다.
LIFO (Last In, First Out) 원칙
- top : 가장 최근에 스택에 삽입된 자료의 위치
- stack.push : top에 새로운 데이터 추가
- stack.pop : 가장 최근에 삽입된 데이터가 스택에서 삭제
- stack underflow : 스택이 비어있을 때, stack.pop을 시도하는 것
- stack overflow : 스택의 크기가 비어있을 때(스택이 꽉 차 있을때), stack.push를 시도하는 것
시간 복잡도
- top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.
장단점
- top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
- top위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능 하다.
탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.
활용
- 재귀 알고리즘
- DFS 알고리즘
- 작업 실행 취소와 같은 역추적 작업이 필요할 때
- 괄호 검사, 후위 연산법, 문자역 역순 출력 등
큐(Queue) : FIFO - 선입 선출
- 큐는 가장 최근에 저장된 값, 다음에 저장되며, 가장 오래전에 저장된 값부터 나간다.
FIFO (First In, First Out) 원칙 - 선착순
- rear : 데이터가 삽입되는 곳
- front : 데이터가 제거되는 곳
- 데이터 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행하여야 한다.
선형 큐 (Linear Queue)
- 선형 배열을 사용하여 구현된 큐
- 삽입을 위해서는 계속해서 요소들을 이동시켜야 함
front, rear는 증가만 하는 방식, 실제로는 front 앞쪽에 공간이 있더라고 삽입할 수 없는 경우가 발생할 수 있음
원현 큐 (Circular Queue)
- 선형 큐의 단점을 보완
- front : 맨 첫번째 요소 바로 앞을 가리킴
- rear : 마지막 요소 가리킴
- 큐 공백(empty) 상태 : front == rear
- 큐 포화(full) 상태 : front == (rear + 1) % MAX_QUEUE_SIZE
- 공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워 둠
시간 복잡도
- front, rear의 위치로 데이터 삽입 삭제가 바로 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.
장단점
- front, rear를 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
- front, rear 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능 하다.
탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.
활용
- 데이터를 입력된 순서대로 처리해야 할 때
- BFS 알고리즘
- 프로세스 관리
- 대기 순서 관리
덱(Deque) : Double - Ended Queue
- 양쪽 front, rear에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조 이다.
- 선언 이추 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.
- 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다.
시간 복잡도
- 삽입 삭제 연산 - O(1)
- index를 통한 요소 탐색 - O(1)
장단점
- 데이터의 삽입 삭제가 빠르고 앞,뒤에서 삽입 삭제가 모두 가능하다
- 가변적 크기
- index를 통해 임의의 원소에 바로 접근이 가능하다
- 중간에서 삽입 삭제가 어렵다
- 스택, 큐에 비해 비교적 구현이 어렵다
활용
- 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
- 데이터의 크기가 가변적일 때
https://github.com/yuseogi0218