[자료구조 / C++ STL] 자료구조를 구현해 놓은 STL

▶ 자료구조의 종류

• 연결리스트
• 스택
• 큐
• 덱
• 트리
• 우선순위 큐

 

 

▶ 연결 리스트(linked list) (양방향 리스트로 구현되어 있음!)

[ADT]

• 리스트 생성
• 양 끝에 요소 삽입/삭제
• 임의의 위치에 요소 삽입/삭제
• 리스트의 각 요소 출력

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list <int> li; // 리스트 생성
	list <int>::iterator iter = li.begin(); // 리스트의 위치를 가리키는 포인터
	for(int i=0; i<10; i++)
   	{
		li.push_front(i); // 리스트에 값을 앞으로 넣음
    	}
	
	for(iter=li.begin(); iter!=li.end(); iter++)
	{
		cout<<*iter<<endl; // 리스트의 위치를 가리키는 포인터를 그릇으로 위치를 옮겨가며 출력
	}
}

 

 

[리스트의 기본 함수]

리스트의 생성

• list <자료형> li[변수명];  → 리스트 생성
• list <자료형> li[변수명](갯수,값);  → 리스트 초기화하여 생성
• list <자료형>::iterator iter(변수명) → 리스트의 위치를 가리키는 포인터 ( 값을 담는 그릇 )

iterator(반복자) -> 자료구조에서 쓰이는 포인터 같은 느낌 !

• begin(): beginning iterator를 반환
• end(): end iterator를 반환 ( 맨 끝 원소가 아니라 맨 끝의 다음 원소임)

추가 및 삭제

• push_front(element): 리스트 제일 앞에 원소 추가
• pop_front(): 리스트 제일 앞에 원소 삭제 (값 반환 안함)
• push_back(element): 리스트 제일 뒤에 원소 추가
• pop_back(): 리스트 제일 뒤에 원소 삭제 (값 반환 안함)
• insert(iterator, element): iterator가 가리키는 부분 “앞”에 원소를 추가
• erase(iterator): iterator가 가리키는 부분에 원소를 삭제(주의!)

조회

• *[iterator의 변수명]: iterator가 가리키는 원소에 접근
• front(): 첫번째 원소를 반환
• back(): 마지막 원소를 반환

기타

• empty(): 리스트가 비어있으면 true 아니면 false를 반환
• size(): 리스트 원소들의 수를 반환
• sort(): 모든 원소를 오름차순으로 정렬
• reverse(): 원소들의 순차열을 뒤집음
• remove(k): k와 같은 원소들을 리스트에서 모두 제거
• unique(): 인접한 원소중에 중복되는 것 있으면 유일하게 만듬(중복 삭제)
• li2.swap(li1): li1과 li2를 바꿈
• li2.splice(iter2, li1): li2에서 iter2가 가리키는 곳에 li1의 모든 원소를 잘라 붙임 (li2.splice(iter2,li1,iter1)도 가능)

 

 

[주의 할점]

erase(iterator) 하면 가리키고 있던 iterator가 다음 가리킬 곳을 잃어버려서 세그멘테이션 오류를 발생시킨다.

그러므로 erase의 반환값이 erase한 값의 다음값이므로

for( Iterator = List.begin(); Iterator != List.end(); ) 
{
    Iterator = List.erase(Iterator);
}

이런 식으로 iterator에 값을 대입해주면 된다!

 

[반복자의 특징]

list<int>::iterator begin_iter = l.begin(); // auto begin_iter = l.begin()도 가능
list<int>::iterator end_iter = l.end(); // auto end_iter = l.end()도 가능


begin_iter++; // 2번째를 가리키는 iterator
li.insert(begin_iter, 2);


end_iter--; // 마지막 원소를 가리키는 iterator
li.erase(end_iter);

☆ 이런식으로 반복자를 포인터 사용하듯이 ++, -- 연산하여 가리키는 위치를 움직일 수 있다 !!

 

 

[원소 출력하는법]

for(iter=li.begin(); iter!=li.end(); iter++)
{
	cout<<*iter<<endl; // 리스트의 위치를 가리키는 포인터를 그릇으로 위치를 옮겨가며 출력
}

 

 

[리스트끼리 연산 대소비교 가능]

 

---

▶ 스택 (Stack)

 

[스택의 기본 함수]

 

스택의 생성

• stack <자료형> li[변수명];  → 스택 생성

추가 및 삭제

• push(데이터) → 스택에 데이터 추가
• pop() → 스택에 데이터 삭제 

조회

• top() → 제일 최상위 데이터(다음에 나올 데이터) 반환 (반환만 하고 값이 사라지진 않음 !)

기타

• size() → 스택에 현재 사이즈 반환
• empty() → 스택이 비어있으면 true(1) 안 비어있으면 false(0) 반납
• swap(stack1, stack2) → stack1 과 stack2의 내용을 바꿈

 

[사용 예시]

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack <int> s;
	
	for(int i=0; i<10; i++)
	{
		s.push(i);
	}
	
	for(int i=0; i<10; i++)
	{
		s.pop(i);
	}
}

스택 생성, 스택에 i값 삽입, 스택 안에 있는 요소 삭제

 

---

▶ 큐(Queue)

 

[ADT]

• 리스트 생성
• 데이터 삽입/삭제
• 큐의 첫번째/마지막 데이터 반환
• 큐의 사이즈 반환
• 큐가 비어있는지 확인

 

[큐의 기본 함수]

큐의 생성

• queue <자료형> q[변수명];  → 리스트 생성

추가 및 삭제

• push(데이터) → 큐에 데이터 추가
• pop() → 선입선출이므로 가장 처음에 들어간것 삭제

조회

• front() → 큐의 첫번째 데이터를 반환
• back() → 큐의 마지막 데이터를 반환

기타

• size() → 큐의 현재 사이즈를 반환한다
• empty() → 큐가 현재 비어있는지 확인
• swap(q1, q2) → q1과 q2의 데이터를 바꿈

 

[사용예시]

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	// 큐 생성
	queue<int> que;
    
    //큐의 전체요소 출력하기
	while (!que.empty()) 
    {
		cout << que.front() << " ";
		que.pop();
	}
}

 

[큐를 원형으로 돌리는법]

for(int i=0; i<num; i++)
	{
		q.push(q.front());
		q.pop();
	}

첫번째 큐 값을 꽁무니로 밀어넣고 첫번째 큐값 삭제

 

 

---

▶ 덱(Deque) = 리스트와 굉장히 유사함

[Deque의 특징]

1. 크기가 가변적이다.

2. 앞과 뒤에서 삽입과 삭제가 좋다.

3. 중간에 데이터 삽입, 삭제가 용이하지 않다.(스택,큐도 마찬가지)

4. 구현이 쉽지 않다.

5. 랜덤 접근이 가능하다.(?)

 

[덱의 기본 함수]

 

덱의 생성

• deque<자료형> dq[변수명];  → 덱 생성

iterator(반복자) -> 자료구조에서 쓰이는 포인터 같은 느낌 !

• begin(): beginning iterator를 반환
• end(): end iterator를 반환 ( 맨 끝 원소가 아니라 맨 끝의 다음 원소임)

추가 및 삭제

• push_front(element): 덱 제일 앞에 원소 추가
• pop_front(): 덱 제일 앞에 원소 삭제
• push_back(element): 덱 제일 뒤에 원소 추가
• pop_back(): 덱 제일 뒤에 원소 삭제 
• clear(): 모든 원소 삭제
• insert(iterator, element): 특정위치에 원소 삽입(iterator의 앞에 삽입)
• erase(iterator): iterator가 가리키는 부분에 원소를 삭제(주의!)
• assign(n, elemant): 원소 n개를 elemant로 초기화

조회

• *[iterator의 변수명]: iterator가 가리키는 원소에 접근
• dq[인덱스]: 배열처럼 인덱스값을 이용하여 조회할수 있다
• front(): 첫번째 원소를 반환
• back(): 마지막 원소를 반환
• at(숫자): 특정 인덱스 원소의 참조 반환 (배열처럼 0이 맨앞임)

기타

• empty(): 덱이 비어있으면 true 아니면 false를 반환
• size(): 덱 원소들의 수를 반환
• resize(숫자): 숫자 크기의 저장공간 재확보

 

[주의 할점]

erase(iterator) 하면 가리키고 있던 iterator가 다음 가리킬 곳을 잃어버려서 세그멘테이션 오류를 발생시킨다.

그러므로 erase의 반환값이 erase한 값의 다음값이므로

for( Iterator = List.begin(); Iterator != List.end(); ) 
{
    Iterator = List.erase(Iterator);
}

이런 식으로 iterator에 값을 대입해주면 된다!

 

 

---

▶ 트리 (Tree)

 

[map과 pair을 이용하는 방법]

 

트리의 구성 원리 -> map과 pair을 이용

map<char, pair<char, char>> tree; //key가 부모노드로 value 두쌍이 각각 좌우 자식노드
tree['A'] = make_pair('B', 'C'); //A는 부모노드 B는 왼쪽 자식노드 C는 오른쪽 자식노드
tree['B'] = make_pair('D', NULL);//왼쪽 자식노드는 D 오른쪽은 없음
tree['C'] = make_pair(NULL,NULL);//말단이어서 자식노드 없음
tree['D'] = make_pair(NULL,NULL);//말단이어서 자식노드 없음

 

트리의 조회 -> first가 왼쪽 자식노드, second가 오른쪽 자식노드

tree['A'].first; //A의 왼쪽 자식노드 조회
tree['A'].second //A의 오른쪽 자식노드 조회

 

 

트리의 전/중/후위순회 -> 재귀적인 사고를 이용

void preorder(char node) {//전위순회
	cout << node << " "; //현재 노드의 데이터 출력
	if (m[node].first != NULL) { //왼쪽 자식이 있다면
		preorder(m[node].first);
	}
	if (m[node].second != NULL) { //오른쪽 자식이 있다면
		preorder(m[node].second);
	}
}
void inorder(char node) {//중위순회
	if (m[node].first != NULL) { //왼쪽 자식이 있다면
		inorder(m[node].first);
	}
	cout << node << " "; //현재 노드의 데이터 출력
	if (m[node].second != NULL) { //오른쪽 자식이 있다면
		inorder(m[node].second);
	}
}
void postorder(char node) { //후위순회
	if (m[node].first != NULL) { //왼쪽 자식이 있다면
		postorder(m[node].first);
	}
	if (m[node].second != NULL) { //오른쪽 자식이 있다면
		postorder(m[node].second);
	}
	cout << node << " "; //현재 노드의 데이터 출력
}

 

<헷갈렸던점>

map은 key 기준으로 오름차순으로 정렬하지만 사용자가 설정하면 사용자 설정에 따른다

#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<int, pair<int, int>> tree;
	tree[1]=make_pair(2,3);
	tree[2]=make_pair(4,NULL);
	tree[3]=make_pair(NULL, NULL);
	tree[4]=make_pair(NULL, NULL);
	
	cout<<tree[tree[1].first].first<<endl; //왼쪽으로 2번 이동
}

실행결과 = 4

 

 

map에 대한 추가 설명

https://ssocoit.tistory.com/25

[C++ STL] Map 사용설명서

 

 

---

▶ 우선순위 큐 (Priority Queue) → 큐와 연산은 비슷함

 

[우선순위 큐의 기본 함수]

 

우선순위 큐의 생성

• priority_queue <자료형, 구현체, 비교연산자> pq;

자료형 : int, double 등의 기본자료형 뿐만 아니라 구조체, 클래스 등 다양하게 사용할 수 있다.

구현체 : 보통 vector<자료형> 으로 구현한다. (stl에서 힙을 구현하기 좋은 자료형이면 다 가능하다고 한다. vector를 include하지 않아도 동작한다.)

비교연산자 : 비교를 위한 함수 삽입

->비교연산자에 들어가는 것은 비교 함수가 아닌 비교 클래스가 들어가야 합니다.

 

평범한 우선순위 큐의 생성(최대힙이 default)

 priority_queue<int> pq;

 

오름차순인 우선순위 큐의 생성(최소힙)

priority_queue <int, vector<int>, greater<int>> pq;

 

 

우선순위 큐 사용자 정의 비교함수 작성(struct 구조 + 연산자 오버라이딩 ()을 이용해서 사용자 정의 함수를 이용한다

->비교해야할 요소가 3개 이상인 경우 반드시 연산자 오버라이딩을 해야한다

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

struct cmp //struct 구조 + operator() 해서 안에 함수 구현
{
	bool operator()(int a, int b)
	{
		if(abs(a)==abs(b))
			return a>b;
		else
			return abs(a)>abs(b);
	}
};


int main()
{
	int N; cin>>N;
	priority_queue <int, vector<int>, cmp> pq;
	
	for(int i=0; i<N; i++)
	{
		int x; cin>>x;
		if(x==0)
		{
			if(!pq.empty())
			{
				cout<<pq.top()<<"\n";
				pq.pop();
			}
			else
			{
				cout<<0<<"\n";
			}
		}
		else
			pq.push(x);
	}
}

 

생성자를 사용한 우선순위 큐 생성

int arr[]={10, 40, 30, 20, 50};
priority_queue <int> pq (arr, arr+5);

 

 

greater<pair<int, int>를 이용한 우선순위 큐

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq

이렇게 정의를 하면 pq.first를 내림차순으로 정렬한 후에 pq.first에서 같은 값이 있으면 pq.second에서 내림차순으로 pq.first가 같은것끼리 정렬한다

 

ex) 절댓값 힙 문제풀이

https://kyunstudio.tistory.com/243

[C++] 백준 11286 - 절댓값 힙(힙, 최소 힙)

 

추가 및 삭제

• push(): 우선순위 큐에 데이터를 추가한다
• emplace(): 우선순위 큐에 구조를 추가한다.
• pop(): 우선순위 큐 내부에서 제일 우선순위가 높은 데이터를 삭제한다

조회

• top(): 우선순위 큐 내부에서 제일 우선순위가 높은 데이터를 보여준다.

기타

• empty(): 우선순위 큐가 비어있으면 true 아니면 false를 반환
• size(): 우선순위 큐 원소들의 수를 반환
• swap(): 두개의 우선순위 큐의 내부를 서로 바꾼다

 

 

[push()와 emplace()의 차이점]

push는 오브젝트로 제작후 큐안에 넣어주지만 emplace는 오브젝트를 생성하지 않고 바로 값을 넣는다

priority_queue< pair<char, int> > pqueue; 
pqueue.emplace('a', 24); //바로 값을 삽입
pqueue.push(make_pair('b', 25)); //오브젝트를 만들고 값을 삽입

[주의 할점]

vector를 정렬하는데 사용된 비교함수와 우선순위 큐를 오름차순으로 정렬하는데 사용된 사용자 정의 함수의 부호가 서로 다름

bool operator()(int a, int b) //우선순위 큐의 오름차순 정의 함수
{
	return a>b;
}

bool cmp(int a, int b)//vector의 오름차순 정의 함수
{
	return a<b;
}