자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

스택

• 후입선출 구조 (Last In First Out)
• 아래 사진과 같이 가장 나중에 쌓은 top에 존재하는 데이터만 접근가능합니다.
  

스택관련 용어

• top : 가장 최신의 데이터
• push : 삽입하는 연산으로 top의 데이터가 변경됩니다.
• pop : 삭제하는 연산으로 top의 데이터가 삭제됩니다.

시간 복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(n)

활용되는 예시

• 브라우저 방문기록 (뒤로가기)
• 실행 취소
• 역순 문자열 (문자열 거꾸로 뒤집기)

큐

• 선입선출 구조 (First In First Out)
• 스택과 달리 삽입이 이루어지는 위치와 삭제가 이루어지는 위치가 다릅니다.
  

큐관련 용어

• front : 가장 최신의 데이터로 해당 위치로 삽입됩니다.
• rear : 가장 오래된 데이터로 해당 위치에서 삭제가 이루어집니다.
• enQueue : 삽입하는 연산으로 해당 데이터가 front의 데이터가 됩니다.
• deQueue : 삭제하는 연산으로 rear의 데이터가 삭제됩니다..

시간 복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(n)

활용되는 예시

• BFS 알고리즘
• 캐시 구현