[자료구조] stack 과 queue

stack

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

특징

인덱스를 지원하지 않는다.

삽입/삭제 연산은 O(1) 이다.
연결리스트로 구현되어있기 때문이다.

사용 사례

• 재귀 알고리즘
• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

queue

먼저 삽입한 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조

특징

인덱스를 지원하지 않는다.

삽입/삭제 연산은 O(1) 이다.
연결리스트로 구현되어있기 때문이다.

사용 사례

• 너비 우선 탐색(BFS)
  • 처리해야할 노드의 리스트를 저장하는 용도로 사용
  • 노드를 처리하면서 해당 노드와 인접한 노드들을 다시 queue에 삽입한다.
• 프린터의 출력처리
• 프로세스 스케줄링
• 캐시 시스템
  • 캐시란 데이터나 연산 결과를 임시로 저장하여 빠른 접근 속도를 제공하는 메모리이다.
  • 가장 최근에 사용한 데이터를 가장 먼저 사용할 수 있다.
  • 큐의 삽입/삭제 시간이 O(1)이기 때문에 빠른 데이터 처리가 가능하다.
  • 만약 검색 연산이 빈번한 경우 해시 테이블을 사용하는 것이 좋다.