스택 (Stack)
- LIFO (Last In First Out)
- array나 linked list를 이용해 구현 가능
- 연산
- push (O(1))
- pop (O(1))
- top (O(1))
- empty (O(1))
- ...
- 응용
- 브라우저 방문 기록 (뒤로가기)
- 실행 취소 (undo)
- 후위표기법 계산
- 역순 문자열 만들기
- 함수 호출, 재귀함수 호출
- 보통 크기를 고정시켜서 사용하는데 꽉 찼을 때 push하게 되면 넘치게 되는데 이것이 stack overflow
- 반대로 비어있는 스택에서 pop하려고 하면 stack underflow
큐 (Queue)
- FIFO (First In First Out)
- array나 linked list를 이용해 구현 가능
- 연산
- enqueue (O(1))
- dequeue (O(1))
- front (O(1))
- empty (O(1))
- ...
- 응용
- 어떤 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용
- 은행 업무
- 프로세스 관리
- cache 구현
- BFS 구현?
- 바리에이션
- 원형 큐
- 우선순위 큐 (heap tree?)
- 원소에 우선순위가 있어서 우선순위가 높은 원소부터 dequeue
- 데크 (Deque)
참고
hi