이번에는 자료 구조를 간단히 알려드리겠습니다.
내용이 길며 찾기 쉽게 목차가 있습니다.
ctrl + f로 글자찾기 로 찾으시면 편합니다.
목차
1. 자료구조
1-1. 배열
1-2. 리스트
1-3. 스택
1-4. 큐
1.자료 구조
데이터를 저장하고 조직하는 방법을 의미합니다.
종류가 여러가지이며
각 자료구조마다 저장방식이 다르고 꺼내는 방식또한다릅니다.
1-1. 배열(Array)
동일한 데이터 타입의 요소들이 연속적으로 저장되는 고정 크기의 데이터 구조입니다.
메모리에서 인접한 공간에 저장되며 , 요소에 직접 접근이 가능합니다.
예)
int arr[3] = {1,2,3};
int a = arr[0]; // a == 1;
특징은 고정 크기라는 점입니다
선언할때 데이터의 타입과 크기를 지정해줘야하는데 초기화는 선언과 동시에 할 수 있습니다.
장점은
빠른접근 , 메모리 사용이 효율 적입니다.
빠른접근이 뭐냐고 할 수있는데 아직 이해안해도 될 정도인 요소입니다만
(O(1) 시간 복잡도) 수학적인 내용이라 이건 좀더 배우고 해도 될거같습니다.
간단하게 좀더 빠르게 접근하냐 느리게접근하냐 차이라고 외우고 있습니다.
단점은
고정크기와 메모리 낭비입니다.
크기를 변경못한다는건 방크기가 정해지면 변경할 수 없다는 겁니다. 크기가 3이면 3개 넘게 넣을 수없습니다.
크기를 미리정해두면 필요이상의 메모리가 낭비됩니다.
방의 크기는 미리 정해졌는데 그 안에 든게 없다면 그건 낭비겠죠?
여기서 배열안에 있는 것을 바꿀 수 있습니다.
arr[0] = 5; // {5,2,3}으로 바뀔겁니다.
그리고 배열 사용할때 대괄호안에 0이 들어가있네요 첫번째 인데 1이아니고 0이네요
그러고 보니 for문 배울때도 int i = 0이였죠
우리는 1부터 시작하지만 c++에서는 0부터 시작합니다.
1-2. 리스트 (List)
순차적으로 저장되는 자료구조이며 일반적으로 크기가 동적입니다.
요소를 추가하거나 삭제 하는 것이 용이합니다.
C++에서는 std::list를 사용하여 리스트를 구현할 수 있습니다.
여기서 봐야할건 크기가 변할 수 있다는 것
추가 , 삭제가 가능한것
입니다.
이게 곧 장점이에요
추가하거나 삭제할수 있고
그만큼 메모리를 필요한 만큼 사용할 수 있습니다.
단점은
느린접근 시간입니다. 특정 요소에 접근하기 위해서는 순차적으로 탐색해야 합니다.
추가적인 메모리 사용도 있어서 노드가 포인터를 가지고 있어서 추가적인 메모리를 사용합니다.
단점은 당장 배워야할 건 아니니 넘기고 장점을 보면 좋을 것 같습니다.
예)
list<int> iList; // 선언 방식 list<변수> 리스트명;
iList .push_back(10); // 요소 추가 리스트의 끝에 10 추가
iList .push_front(5); // 리스트의 앞에 5 추가
출력하려면
for (int elem : iList ) {
cout << elem << " "; // 5 10 출력
}
cout << endl;
iList.pop_back(); // 마지막 요소 삭제 (10삭제)
iList.pop_front(); // 첫번째 요소 삭제 (5삭제)
iList.remove(5); // 값이 5인 요소 삭제
****
for (int elem : iList )
반복문의 조건을 이렇게 하면 해당 리스트에있는걸 처음부터 끝까지 꺼낸다는 뜻으로 보면 됩니다.
1-3 . 스택
LIFO (Last In , First Out) 구조로 마지막에 들어온 요소가 먼저 나가는 .
즉 최근에 추가도니 데이터가 가장 먼저 제거되는 자료 구조입니다.
스택은 위에서 배운 배열과 리스트와는 다릅니다.
ㅣ 0 ㅣ
ㅣ 0 ㅣ
ㅣ 0 ㅣ
ㅣ 0 ㅣ
----------
이라는 공간이있다고하면
스택에 순서대로 1234 값을넣으면
ㅣ 4 ㅣ
ㅣ 3 ㅣ
ㅣ 2 ㅣ
ㅣ 1 ㅣ
----------
으로 됩니다.
1은 맨아래에있으므로 꺼낼려면 4 3 2 전부 빼야 나옵니다.
즉 마지막에 온게 가장 먼저나가게 되고 먼저들어간 1은 맨 나중에 나오게 되겠죠
이런걸 어디가 써먹나 싶지만 인터넷에 뒤로가기로 예시로 들면 이해가 될겁니다.
전에 봤던페이지로 돌아가려면 뒤로가기 누르면 되니까요
stack<int> st;
//추가 방법
st .push(10);
st .push(20);
st .push(30);
st.top(); // 최상단 요소 30
st .pop(); //최상단 요소 제거 하고 그값을 반환 // 30이 사라짐
st.top(); // 최상단 요소 20
1-4 큐
FIFO(First In, First Out)
구조로 먼저들어온게 먼저나갑니다.
1234가 들어가면 1부터 나가는겁니다.
ㅣ 4 ㅣ
ㅣ 3 ㅣ
ㅣ 2 ㅣ
ㅣ 1 ㅣ
queue<int> Qu;
// 요소 추가
Qu .push(10);
Qu .push(20);
Qu .push(30);
Qu .front() ;// 10
// 요소 제거
Qu .pop(); // 10 나감
Qu .front() ;// 20
자료구조는 이것 말고도 더 있습니다.
하지만 이정도만 알아도 알 수 있는 게 있을겁니다
3줄 요약
요소를 저장하는 공간을 만들 수 있고
방법도 다양하며 그 방법마다 용도가 다르며
성능도 다르다.