C++ STL 기본 컨테이너 구조(스택,큐,사전,우선순위 큐,집합) -1

저는 평범한 대학생이므로 내용중 틀린부분이 있을 수 있습니다. 알려 주시면 확인 후 바로 수정하겠습니다.

 

 

-오늘은 C++ STL에서 자주 사용되는 기본적인 5가지 컨테이너 구조에 대해 알아보겠습니다.

 

• 1.스택(stack)

-스택은 LIFO(last-in-first-out) 후입선출 규칙을 따르는 구조입니다.(마지막에 들어간 항목이 가장 먼저 나오는 자료구조)

 접시를 새로 씻고 나면 접시는 스택 맨 위에 추가되고 접시를 사용 할 때는 맨 위에 있는 새 접시를 사용 한다고 생각 하시면 될 것 같습니다.

 

-연산

push(x)	x라는 항목을 스택 맨 위에 삽입
pop()	스택 맨 위에 있는 항목을 삭제
empty()	스택이 비어있는지를 확인 후 true,false 값을 반환
size()	스택에 들어있는 원소의 개수를 반환

top()

스택 맨 위에 있는 항목을 리턴

 

자주 쓰이는 4가지 연산을 알아 보았습니다. 추가적으로 궁금한 연산은 아래의 사이트에서 확인하시면 될 것 같습니다.

http://www.cplusplus.com/reference/stack/stack/?kw=stack 

 

-스택은 구현하기가 아주 간단한 컨테이너기 때문에 순서가 별로 중요하지 않은 경우에 활용하면 좋습니다.

ex) 중첩된 구조를 처리할 때 -> 괄호로 싸여있는 공식 ( '(' 가 나오면 push, ')' 가 나오면 팝), 재귀호출(프로시저 시작 push, 프로시저 종료 pop)

     그래프의 깊이 우선 순회(DFS) -> 정점을 발견하면 push, 그 정점을 마지막으로 떠날 때 pop

 

다음은 테스트용 코드입니다.

스택을 사용하기 위해서는 <stack>을 추가해주어야 합니다.

 

 

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
	stack<int> s; //스택 생성 
	
	cout<<s.empty()<<endl; //초기 스택은 비어있으므로 1 출력 
	s.push(4); //4 푸시 
	s.push(2); //2 푸시 
	s.push(3); //3 푸시 
	cout<<s.top()<<endl; //가장위에 있는 값을 반환 
	s.pop(); //가장 위에 있는 값을 삭제 
	cout<<s.top()<<endl; 
	
	cout<<s.empty()<<endl;
	cout<<s.size()<<endl; //스택의 사이즈 반환 
	
	 
	return 0;
}

 

 

 

• 2.큐(queue)

-큐는 FIFO(first-in first-out) 선입선출 규칙을 따르는 자료 구조입니다.( 가장 먼저 들어간 것이 가장 먼저 나오는 자료구조)

 카드 놀이를 할때 카드를 꺼낼 때는 맨 위에서 꺼내고 카드를 집어넣을 때는 맨 밑부터 넣는 것을 생각 하시면 될 것 같습니다.

 (롤에서 게임을 잡을때 큐를 잡는다고 말 하는데 이것 또한 매칭을 돌리는 유저들을 큐에 집어놓고 순서대로 매칭 시켜주는 원리입니다.)

 

-연산

 

push(x)	x라는 항목을 큐의 맨 끝에 삽입
pop()	큐의 맨 앞에 있는 항목을 삭제
front()	큐의 맨 앞에 있는 항목을 리턴
back()	큐의 맨 뒤에 있는 항목을 리턴
empty(),size()	큐가 비어있는지 검사, 큐에 들어있는 원소의 개수 반환

 

자주 쓰이는 6가지 연산을 알아 보았습니다. 추가적으로 궁금한 연산은 아래의 사이트에서 확인하시면 될 것 같습니다.

http://www.cplusplus.com/reference/queue/queue/?kw=queue

 

-큐는 양쪽 끝에 대해 작업을 처리해야 하므로 스택보다는 구현이 힘듭니다. 큐의 구현법은 가장 간단하게 배열을 이용하여 한쪽 끝에 원소를 추가하고 pop 할때마다 배열 원소를 앞으로 한칸 씩 모두 당기는 방법입니다. 하지만 이러한 구현은 pop할 때마다 모든 원소를 옮겨야 하므로 시간 낭비가 매우 심합니다. 따라서 큐의 첫번째와 마지막 원소에 대한 인덱스를 따로 관리하며 원형 으로 큐를 사용하는 것이 공간을 재활용할 수 있어 효율적입니다.

+ 원형 큐를 사용할 때는 첫번째 원소와 마지막 원소의 위치가 겹치는 문제가 생길 수 있는데, 연결리스트를 사용하면 이 문제를 해결할 수 있습니다. 이런 이유로 배열보다 연결리스트를 써서 구현하는 것이 더 편한 몇 안되는 자료구조 가운데 하나입니다.

 

다음은 테스트용 코드입니다.

큐를 사용하기 위해서는 <queue>를 추가해주어야 합니다.

 

 

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	queue<int> q; //큐 생성 
	
	q.push(4); //4 삽입 
	q.push(3); //3 삽입 
	q.push(2); //2 삽입 
	
	q.pop(); //큐의 가장 앞에 있는 4를 삭제 
	cout<<q.front()<<endl; //큐의 가장 앞에 있는 원소 반환 
	cout<<q.back()<<endl; //큐의 가장 뒤에 있는 원소 반환 
	cout<<q.empty()<<endl; //큐가 비어있는지 검사 
	cout<<q.size()<<endl; //큐의 사이즈 반환 
	
	return 0;
}

 

 

• 3.사전(map)  

-사전은 스택이나 큐에서 위치를 기준으로 데이터를 가져오는 것과 달리 내용을 기준으로 가져 올 수 있습니다.

 

 

-연산

insert(make_pair(key,value))	사전에 key값에 맞는 value 값을 삽입
begin()	시작 iterator를 반환
end()	끝 iterator를 반환
empty(), size()	사전이 비어있는지, 사전의 크기를 반환
erase(key)	key 값에 맞는 value 값을 삭제

clear()

사전의 모든 원소 삭제

find(key)	key 값에 해당하는 iterator를 반환
count(key)	key 값에 해당하는 원소 갯수 반환

 

추가적인 연산은 아래의 사이트에서 확인하시면 될 것 같습니다.

http://www.cplusplus.com/reference/map/map/?kw=map

 

아래는 테스트 코드입니다.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(void) {
	map<string, int> m; //map 생성 
	
	//밑의 3가지 방법 모두 사용가능하다. 
	m.insert(pair<string, int>("abc", 4));  
	m.insert(make_pair("ab",5));
	m["abcd"] = 6;
	m["abcde"] = 8;
	
	cout<<m.size()<<endl;
	
	m.erase("abc"); //abc키값에 해당하는 value 삭제 
	
	
	
	cout << "abc : " << m.count("abc") << '\n';
	cout << "ab : " << m.count("ab")<< '\n';
	
	for(auto it = m.begin(); it!=m.end(); it++) { //iterator를 이용해서 map 순회 
		cout<<"key: " <<it->first << " value: "<< it->second<<endl;
	}
	
	m.clear(); //모든 원소제거 
	
	cout<<m.empty()<<endl;
	
	return 0; 
}

맵은 iterator 접근시 ->first 와같이 key값에 접근 가능하고 ->second 또는

(*it).first , (*it).second 와같이 접근하면 됩니다.

 

우선 순위큐와 집합은 2편에서 다루어보도록 하겠습니다.