스택, 큐 개념정리
스택, 큐 개념정리
스택(stack)은 가장 마지막에 저장(push)된 데이터가 가장 먼저 삭제(pop)되는 후입선출(LIFO, Last In First Out)구조를 가진 자료구조이다.
스택은 한쪽 방향에서만 데이터의 삽입/삭제 연산이 가능하다.
스택 용어
- top(peek) : 가장 최근에 저장된 데이터이자 가장 먼저 삭제 될 데이터
- push : 데이터를 삽입하는 연산
- pop : 데이터를 삭제하는 연산
- stack overflow : 스택에 저장된 데이터가 정해진 스택의 크기보다 클 경우 생기는 오류
- stack underflow : 비어있는 스택에서 원소를 추출하려고 할 경우 생기는 오류
시간 복잡도
- 삽입/삭제 : O(1)
- 탐색 : O(n)
사용되는 예시
- 브라우저 방문기록
- 실행 취소(undo)
- 후위 표기법 계산
- 재귀 함수
큐(Queue)는 한쪽에서는 데이터의 삽입, 한쪽에서는 데이터의 삭제만 가능하고 가장 먼저 저장된 데이터가 가장 먼저 삭제되는 선입선출(FIFO,First In First Out) 구조를 가진 자료구조이다.
큐 용어
- front(프론트) : 데이터를 삭제하는 부분
- rear(리어) : 데이터를 삽입하는 부분
- enqueue(인큐 = push) : 데이터 삽입 연산
- dequeue(디큐 = pop) : 데이터 삭제 연산
시간 복잡도
- 삽입/삭제 : O(1)
- 탐색 : O(n)
사용되는 예시
- BFS 알고리즘
- 우선순위가 같은 작업 예약(프린트 대기열)
- 캐시(cache)
큐의 파생 및 종류
우선순위 큐(Priority Queue)는 각각의 요소는 값과 우선순위 2개의 값을 가지고 선형 큐(일반적인 큐)처럼 모두 같은 우선순위를 가지지 않고 우선순위가 높을수록 먼저 삭제되는 특징을 가진다.
만약 우선순위가 같을 경우 삽입순서가 빠른순으로 삭제된다.
삽입 및 삭제 시 우선순위에 따라 요소들을 정렬 해야하기 때문에 나중에 적을 힙(Heap)이라는 자료구조로 주로 구현된다.
시간 복잡도
- 삽입/삭제 : O(logn)
- 탐색 : O(1)
원형 큐(= 환형 큐, Circular Queue, Ring Buffer)는 원형으로 된 큐로 선형
덱(Deque = Double-ended Queue)은 Double ended Queue말 그대로 큐 2개를 겹쳐놓은것과 같이 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조이다.
TAGS.
