Stack 스택

Concept 개념

스택은 기본적으로 데이터를 들어온 순서대로 쌓는 자료구조이다. LIFO – Last In First Out(후입선출)의 구조로 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조이다. 일직선으로 이루어진 주차장을 상상해보면 된다. 물론 현실에 이러한 주차장을 만들지는 않겠지만, 가장 먼저 들어온 차는 이전에 들어온 차들이 순차적으로 나가기 전에는 주차장을 벗어날 수가 없다.

Main Operations 주요연산

ex) [5, 4, 2, 6, 39]

PUSH: 요소 삽입 가장 ex) [5, 4, 2, 6, 39] -> s.push(42) -> [5, 4, 2, 6, 39, 42]

POP: 스택 맨 위 요소 추출 ex) [5, 4, 2, 6, 39, 42] -> s.pop() -> [5, 4, 2, 6, 39]

PEEK/TOP: 가장 위에 있는 요소 확인, 추출 x

s.top()

s.top()

SWAP(C++ 11): 서로 다른 두 스택을 교환

int main()
{
    std::vector<std::string> v1{"1","2","3","4"},
                             v2{"Ɐ","B","Ɔ","D","Ǝ"};
 
    std::stack s1(std::move(v1));
    std::stack s2(std::move(v2));
 
    print("s1", s1);
    print("s2", s2);
 
    s1.swap(s2);
 
    print("s1", s1);
    print("s2", s2);
}

Output:

s1 [4]: 4 3 2 1
s2 [5]: Ǝ D Ɔ B Ɐ
s1 [5]: Ǝ D Ɔ B Ɐ
s2 [4]: 4 3 2 1

int main()
{
    std::vector<std::string> v1{"1","2","3","4"},
                             v2{"Ɐ","B","Ɔ","D","Ǝ"};
 
    std::stack s1(std::move(v1));
    std::stack s2(std::move(v2));
 
    print("s1", s1);
    print("s2", s2);
 
    s1.swap(s2);
 
    print("s1", s1);
    print("s2", s2);
}

Output:

s1 [4]: 4 3 2 1
s2 [5]: Ǝ D Ɔ B Ɐ
s1 [5]: Ǝ D Ɔ B Ɐ
s2 [4]: 4 3 2 1

EMPTY: ture 빈 경우, false 비어있지 않은 경우

std::stack<int> stack;
stack.empty()

SIZE: s.size()스택의 크기 반환

std::stack<int> stack;
stack.empty()

SIZE: s.size()스택의 크기 반환

Time Complexity 시간복잡도

기본적으로 가장 맨 위 요소가 아닌 다른 요소로 접근이 불가하기 때문에 O(1)의 시간 복잡도를 가진다.

Queue 큐

Concept 개념

스택과 거의 동일하지만 FIFO – First In First Out의 구조로 마치 편의점 냉장고에서 음료수가 나오는 것과 유사한 구조이다. 가장 먼저 들어간 것이 가장 먼저 나간다.

그리고 큐에는 다양한 형태의 큐가 존재한다.

1. 일반 큐(Queue)
2. 원형 큐 (Circular Queue)
3. 우선순위 큐 (Priority Queue)
4. 덱( Deque; Double Ended Queue)
5. 블로킹큐(Blocking Queue)
6. 워크스틸링(Workstealing Queue)

Main Operations 주요연산

POP(Dequeue): 앞(front) 요소 제거

PUSH(Enqueue): q.push(32) 뒤(rear)에 요소 삽입

EMPTY: 비어있는지 확인

FRONT/BACK: 첫번째와 마지막 요소 확인

Time Complexity 시간복잡도

이 또한 처음과 맨끝 요소 이외에 임의 접근이 불가하여 시간복잡도는 O(1)를 가진다.

List 리스트

Concept 개념

각 노드가 기차처럼 연결된 구조. 포인터를 사용하여 각 노드들을 연결한다. 포인터에 갯수에 따라 단방향 리스트와 양방향 리스트로 나뉜다.

양방향 리스트는 말그대로 이후와 이전 노드를 가리키는 포인터가 있어 앞, 뒤 어느 방향이든 접근 가능한 리스트 형태이다.

c++표준은 양방향 리스트

Main Operations 주요연산

push_front(x), push_back(x): 맨 앞/뒤 삽입

pop_front(), pop_back(): 맨 앞/뒤 제거

insert(it, x): 반복자 it 위치에 삽입

erase(it): 반복자 it 위치 제거

front(), back(): 맨 앞/뒤 값 확인

empty(), size(): 비었는지/크기 확인

Time Complexity 시간복잡도

인덱스로 임의 접근: O(n) (연결 리스트는 랜덤 액세스 불가)

push_front, push_back, pop_front, pop_back: O(1)

insert, erase (지점 반복자 주어짐): O(1) (해당 위치를 이미 알고 있을 때)

값 검색(find 등): O(n)

순회(iteration): O(n)

HashMap 해시맵

Concept 개념

키-값 쌍을 해시 함수로 버킷에 분배해 저장하는 자료구조. 키는 중복이 불가능하고 해싱을 통해 고유한 해시코드를 가지게 된다. 하지만, 데이터가 많아지는 경우 해시코드가 중복되기도 한다 이와 같은 경우 재해싱(rehashing)을 통해 문제를 해결할 수 있다. 데이터 순서는 보장 x, 키 값으로 빠른 탐색이 가능

Main Operations 주요연산

삽입: m.insert({key, value}), m.emplace(key, value), m[key] = value

• 주의: m[key]는 키가 없으면 디폴트 값으로 삽입한 뒤 참조를 반환

조회: m.find(key) (이터레이터 반환), m.at(key) (없으면 예외), m.count(key) (0/1)

삭제: m.erase(key)

기타: m.size(), m.empty(), m.clear(), m.load_factor(), m.rehash(n), m.reserve(n)

Time Complexity 시간복잡도

평균(Amortized): insert, find, erase → O(1)

최악(Worst-case; 해시 충돌 심함): O(n)

전체 순회: O(n)

리해시(rehash): 발생 시 재분배 비용이 들 수 있으나 평균화하면 상기 연산 평균 O(1) 유지 -> 최악의 경우에는 O(n)

Reference 출처

• cppreference.com
• gamza1013.tistory.com