Stack Queue
- Data structure
- 2021년 6월 3일
1. 스택
Last In First Out으로 최근에 추가한 항목이 가장 먼저 제거되는 데이터 방식
1) 함수
- pop() : 스택에서 가장 위에 있는 항목을 제거
- push() : item하나를 스택의 가장 윗 부분에 추가
- peek() : 스택의 가장 위에있는 항목을 제거없이 값만 반환
- isEmpty() : 스택이 비었는지 검사
2) 사용 예
- 재귀 알고리즘
- 웹 방문기록
- 실행 취소
2. 큐
First In First Out으로 가장 먼저 추가한 데이터가 먼저 제거되는 데이터 방식
1) 함수
- add(inQueue)() : 큐의 끝 부분에 데이터 추가
- remove(deQueue)() :큐의 첫번째 항목을 제거
- peek() : 큐의 가장 위에있는 항목을 제거없이 값만 반환
- isEmpty() : 큐가 비었는지 검사
2) 사용 예
- 프로세스 관리
- 너비 우선 탐색(BFS)
- 캐시 구현
- 우선순위 큐
- 덱
3. 우선순위 큐 ( Priority Queue )
우선순위의 개념을 큐에 도입한 자료 구조.
일반적인 큐는 FIFO의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.
1) 구현 방법
- 배열
- 리스트
- 힙(Heap)
| 표현 방법 | 삽 입 | 삭 제 |
|---|---|---|
| 순서 없는 배열 / 리스트 | O(1) | O(n) |
| 정렬된 배열 / 리스트 | O(n) | O(1) |
| 힙 | O(logn) | O(logn) |
4. 덱 ( Deque )
Double-ended queue의 약자로 양 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.
일반 큐와의 차이점은 push,pop 할 수 있는 방향이 양방향이라는 것이 차이점이다.
