메모리의 영역을 어떻게 처리하느냐에 따라 구분할 수 있다.
Stack
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO 구조. (Last In First Out)
push/pop/top
자료가 없을 때 pop 하는 경우 stack underflow 발생.
스택 크기 이상의 자료 push 하는 경우 stack overflow 발생.
시간 복잡도 : O(1)
장점 : 데이터 삽입, 삭제가 빠르다.
단점 : 맨 위 데이터만 접근이 가능하기 때문에 탐색이 어렵다.
재귀 알고리즘, 역추적 또는 DFS(깊이 우선 탐색) 구현 시 사용.
ex) 괄호 짝 맞추기, 역순 문자열 만들기, 후위 표기식으로 변환 등
Queue
먼저 넣은 자료를 먼저 뺄 수 있는 FIFO 구조. (First In First Out)
push/pop/front/back/empty/size
선형 큐를 배열로 구현했을 경우, 데이터 제거시 한 칸씩 이동시켜야 한다.
자료가 배열의 끝까지 저장되어 있어서 back을 더 이상 이동할 수 없는 경우 overflow 발생.
시간 복잡도 : O(1)
장점 : 데이터 삽입, 삭제가 빠르다.
단점 : 빈 메모리가 있어도 꽉 차있다고 판단할 가능성이 있다.
-> Circular Queue
단점 : 크기가 제한적이다.
-> Linked List Queue
입력된 순서대로 데이터 처리 또는 BFS(너비 우선 탐색) 구현 시 사용.
ex) BFS 문제, 대기 순서, 프로세스 관리
Deque
양쪽 끝에서 자료를 넣고 뺄 수 있는 구조. (= Stack + Queue)
push_front/push_back/pop_front/pop_back/front/back
Scroll: 입력 제한 - 입력은 한쪽에서만 발생, 출력은 양쪽에서 발생
Shelf: 출력 제한 - 입력은 양쪽에서 발생, 출력은 한쪽에서만 발생
시간 복잡도 : O(1)
장점 : 데이터 삽입, 삭제가 빠르다. 크기가 가변적이다. index로 임의 원소 접근이 가능하다.
단점 : 중간에서의 삽입, 삭제가 어렵다. 구현이 어렵다.
데이터 검색을 거의 하지 않고 랜덤하게 접근하거나 복잡한 스케쥴링 시 사용.
ex) 우선순위 조절
