넓고 얕은 자료구조 & 알고리즘/자료구조론
스택(stack) & 큐(Queue) 1분 요약 정리
팡펑퐁
2023. 3. 4. 02:34
728x90
스택(stack)
- 삽입과 삭제가 한 쪽 끝에서만 이루어지는 데이터 구조이다.
- 가장 먼저 들어간 데이터가 가장 마지막에 나오는 후입 선출(LIFO, Last In First Out) 방식이다.
- 삽입/삭제의 복잡도는 O(1)이다.
- 활용
- 재귀 알고리즘을 사용할 때 유용하다.
- 재귀적으로 함수를 호출 할 때, 데이터를 스택에 넣었다가, 재귀 함수를 빠져나올 때 스택에 넣어둔 데이터를 빼는 방식을 사용할 수 있기 때문이다.
- 웹 브라우저 방문 기록
- 실행 취소
- 재귀 알고리즘을 사용할 때 유용하다.
큐(Queue)
- 한 쪽에서는 삽입이, 다른 한 쪽에서는 삭제가 이루어진다.
- 가장 먼저 들어간 데이터가 가장 먼저 삭제되는 선입선출(FIFO, First In First Out) 방식이다.
- 삽입 연산(enQueue)이 이루어지는 곳을 리어(rear), 삭제 연산(deQueue)이 이루어지는 곳을 프론트(front)라고 한다.
- 보통 연결리스트(LinkedList)를 사용하여 구현한다.
- 원형 큐, 우선순위 큐, 데크(Deque) 등이 있다.
- 활용
- 주로 데이터가 입력된 순서대로 처리하는 상황에 사용된다.
- 우선순위 예약
- 은행 업무
- 콜센터 대기 시간
- 프로세스 관리
참고 :
728x90