벡터, 스택, 큐 간단히 알아보기

벡터(vector)

벡터: 요소가 추가되거나 제거될 때 크기가 커지거나 줄어들 수 있는 동적 배열 유형

• C++ 및 Java와 같은 많은 프로그래밍 언어의 핵심 개념
• python이나 javascript의 경우 ‘벡터’라는 용어는 직접 사용되지 않지만 동적 배열과 같은 데이터 구조의 개념과 기능은 존재

시간 복잡도

• 특정 인덱스에 있는 요소에 접근: O(1)
• 원소 찾기: O(N)
• 끝에 요소 삽입 또는 삭제: 평균 O(1) (amortized 시간 복잡도)
• 특정 인덱스에 요소 삽입 또는 삭제: O(N)

amortized 시간 복잡도 (분할 상환 시간 복잡도 = 할부)

• 끝에 요소 삽입 또는 삭제: O(1)
• 그러나 종종 배열(메모리)이 가득 차게 될 수 있으며 새 요소를 push() 할때 O(N)과 같이 더 많은 시간이 소요되는 작업이 드물게 발생.
• 그래서 최악의 상황으로 시간 복잡도를 고려하는 대신 작업을 평균화한 amortized 시간 복잡도 사용

스택(stack)

스택: 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO)을 가진 자료구조

추상 데이터 타입(ADT, Abstract Data Type)

• 추상 데이터 타입은 일련의 작업 및 동작은 설명하지만 직접 구현은 설명할 수 없는 데이터 타입
• 대부분의 프로그래밍 언어에는 스택이 내장 데이터 타입이나 클래스로 딸려 있지 않음. 구현은 사용자의 몫. 대부분의 언어가 배열을 지원하는 것과 극명하게 대조됨
• stack은 배열이나 연결 리스트 등 어떤 데이터 구조를 써도 상관 없음. LIFO 방식으로 동작하는 데이터 원소들의 리스트이기만 하면 된다.
• 앞서 나온 vector와 다음에 나올 queue도 마찬가지로 추상 데이터 타입

스택을 사용하는 응용프로그램

• Linter
  • 여는 괄호면 스택에 push, 닫는 괄호면 스택에서 pop 괄호의 종류가 다르거나 개수가 안맞으면 오류 생성
• 실행 취소 (Ctrl + Z)
• 웹페이지 방문 기록

큐(queue)

큐: 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)을 가진 자료구조

• stack과 queue 모두 임시 데이터를 처리하기 위해 디자인된 구조
• 데이터를 처리하는 순서만 제외하면 많은 면에서 스택과 비슷
• 또한 큐는 요청받은 순서대로 요청을 처리하므로 비동기식 요청을 처리하는 완벽한 도구이기도 하다.
• 이륙을 기다리는 비행기나 의사를 기다리는 환자처럼 정해진 순서대로 이벤트가 발생해야 하는 실세계 시나리오를 모델링하는 데 흔하게 쓰인다.