[자료구조] 벡터, 스택, 큐

1. 벡터(Vector)란?

: 동적으로 요소를 할당할 수 있는 동적 배열이다. 동적 할당의 핵심은 컴파일 시점에 원소의 개수를 '모른다는 것'이다. 즉 코드를 작성하는 시점에 원소의 개수를 알지 못하는 상태이다.

1) 벡터의 특징

• Random Access

  O(1))

• 삽입 : push_back()

  O(n))

• 삭제 : pop_back() 연산

  O(n))

2) 벡터의 장/단점

• Random Access
  : 요소에 인덱스를 사용하여 빠르게 접근할 수 있는 빠른 랜덤 액세스(Random Access) 기능을 제공
• 동적인 크기 조정
  : 크기가 동적으로 조정
• 메모리 관리
  : 벡터는 동적 할당을 통해 메모리를 관리합니다. 크기가 조절되면 내부적으로 메모리 재할당이 이루어지므로, 개발자가 메모리를 신경 쓸 필요가 없다.

3) 벡터의 사용

#include <vector>
#include <algorithm>
vector<int> numbers;

int main(){
	// 뒤에서부터 원소 삽입
	numbers.push_back(4);
    numbers.push_back(5);
	numbers.push_back(6);
    
    // 뒤에서 원소 삭제
    numbers.pop_back();
    
    // 벡터의 사이즈 (원소의 개수) 
    int size = numbers.size();
    
    // numbers의 두 번째 요소 삭제
    numbers.erase(numbers.begin()+1);
    
    // numbers 요소 정렬(default : 오름차순)
    sort(numbers.begin(),numbers.end());
    
    // number의 특정 원소의 위치(index) 찾기
    auto it = find(numbers.begin(),numbers.end(),3);
    if(it!=numbers.end()){
    	int index = distance(numbers.begin(),it);
    }
}

2. 스택(Stack)

LIFO (Last In First Out) : 가장 늦게 삽입된 원소가 가장 먼저 나오는 성질을 가진 자료구조

1) 스택이란?

2) 스택의 장/단점

① 장점

• 간단한 데이터 구조
• 메모리 할당과 해제의 오버헤드가 적음
• 역순 문자열 처리, 함수 호출 스택 등에 유용

② 단점

• 중간 요소에 접근하려면 상위 요소를 순차적으로 제거해야함
• 중간 요소를 삽입or제거 연산이 비효율적

3) 스택의 활용

#include <iostream>
#include <stack>

using namespace std;
int main(){
	stack<int> myStack;
    
    // 원소 삽입
    myStack.push(10);
    
    // 원소 삭제(위에서부터)
    while(!myStack.empty())
    	myStack.pop();
        
    return 0;
}

3. 큐(Queue)

FIFO (First In First Out) : 가장 먼저 삽입된 원소가 가장 먼저 나오는 성질을 가진 자료구조

1) 큐란?

2) 큐의 장/단점

① 장점

• 데이터의 순서를 유지하며, 처리할 수 있습니다.

② 단점

• 큐의 크기가 커질수록 중간 요소에 접근하는 데 시간이 더 걸림
• 메모리 관리의 어려움이 있을 수 있음

3) 큐의 활용

#include <iostream>
#include <queue>
int main(){
	queue<int> myQueue;
    
    // 원소 삽입
    myQueue.push(10);
    myQueue.push(10);
    myQueue.push(10);
    
    // 앞에서부터 원소 삭제
    while(!myQueue.empty
    	myQueue.pop();
        
    return 0;
}