스택 큐 덱 개념 정리

스택

한쪽 끝에서 자료를 넣고 빼는 자료구조
push로 top에 넣고 pop을 통해 가장 최근에 삽입된 데이터를 스택에서 삭제한다.
LIFO(후입선출)

시간복잡도

삽입: Insertion O(1)
삭제: Deletion O(1)(pop) / O(N)(remove)
검색: Search O(N)

활용

재귀 알고리즘
DFS 알고리즘
작업 실행 취소와 같은 역추적 작업이 필요할 때
괄호 검사, 후위 연산법, 문자열 역순 출력 등

큐

양쪽 끝에서 데이터의 삽입과 삭제가 이루어지는 자료구조
데이터가 들어오는 곳을 rear, 데이터가 나가는 곳을 front라고 하며
큐의 자료를 뽑아낼 때 empty인지 확인해야하고 넣을 때도 full인지 확인해야 한다.
FIFO(선입선출)

시간복잡도

삽입: Insertion O(1)
삭제: Deletion O(1)(dequeue) / O(N)(remove)
검색: Search O(N)

활용

데이터를 입력된 순서대로 처리해야 할 때
BFS 알고리즘
프로세스 관리
대기 순서 관리

덱

큐의 양 끝이 rear인 동시에 front 인 자료구조
데이터의 양쪽 끝에서 삽입 삭제가 가능하다.

시간복잡도

삽입: Insertion O(1)
삭제: Deletion O(1)(pop) / O(N)(remove)
검색: Search O(N)

활용

데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
데이터의 크기가 가변적일 때