Overview
자료 구조
[DS] Array
Array(배열) 정적 배열 (Static Array) 기본적인 배열을 의미한다. C++에서 간단하게 선언이 가능하다. 1차원 int arr0[3]; int arr1[10] = { 0, }; int arr2 = { 1,2,3,4 }; 2차원 int arr0[3][7]; int arr1[10][10] = { { 0, }, }; int arr2 = { { 1,2}, { 3,4 } }; 3차원 이상의 배열도 [ ]를 추가하여 선언이 가능하다.
[DS] Single Linked List
Single Linked List (단순 연결 리스트) 1. 개념 하나의 노드에 필요한 정보를 담고 다음에 해당하는 노드를 가리키고 있는 자료구조로 포인터를 이용해 자료들을 선형으로 연결한 자료구조이다. [ 배열 ] 과 비교했을 때 추가 및 삭제가 쉽다는 장점이 있지만 접근할 때 O(n)만큼 걸린다는 단점이 있습니다.
[DS] Queue
Queue(큐) 1. 개념 Queue는 FIFO(First In First Out)의 원리로 동작하는 자료구조이다. 동일한 자료의 집합을 다룬다는 면에서 Stack과 비슷하지만 가장 먼저 들어간 자료가 가장 늦게 나온다는 점이 다르다. 넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야 하는 자료를 임시작으로 저장하는 용도로 흔히 사용한다.
[DS] Stack
Stack(스택) 1. 개념 가장 늦게 들어간 자료가 가장 먼저 나가는 구조이다. 후입선출(LIFO, Last In First Out)이라고도 부른다. Stack에 데이터를 넣는 행동을 push, 데이터를 빼는 행동을 pop이라 한다. Stack의 가장 위 데이터를 가르키는 포인터를 top이라고 한다.
[C++ STL] Queue
Queue 내부적으로는 deque, list로 구성되어 있다. queue구조로 동작하도록 멤버 함수를 제공해준다. <queue> 헤더파일에 존재한다. std namespace를 사용하면 편리하다. 기본 생성자
[C++ STL] Vector
개념 vector는 자동으로 메모리가 할당되는 배열이라고 생각하면 됩니다. template를 사용하기 때문에 데이터 타입은 마음데로 넣을 수 있습니다. Stack과 비슷한 구조를 가지고 있으며, 맨 뒤에서 삽입과 삭제가 가능합니다. 중간의 값을 삭제하거나 삽입이 가능하지만, 배열기반이므로 삽입과 삭제가 빈번하게 일어난다면 효율이 떨어집니다.