TIL_20210119

Data Structure

_Computer science의 가장 기본이 되는 자료구조.

자료구조는 이론의 영역인 만큼 이해하는 것이 중요합니다.

 

자료 (Data)

문자, 숫자, 소리, 그림, 영상, 단어 등의 형태로 된 의미 단위입니다.

자료를 의미있게 정리하면 '정보'가 됩니다. 이 세상의 모든 것이 Data가 될 수 있습니다.

이런 Data의 처리를 연산 속도가 아주 빠른 컴퓨터에게 맡기면 굉장히 효율적으로 사용할 수 있습니다. 

데이터의 종류는 크게 원시 타입(primitive type), 사용자 정의 타입(custom type) 2 종류로 나뉘며

원시 타입에는 정수, 실수, 문자, 논리(참/거짓) 등이 포함되고 사용자 정의 타입에는 구조체, 클래스 등이 포함됩니다.

이러한 데이터 타입들은 하나의 데이터를 어떻게 해석할지 정의한 것입니다.

 

자료 구조 (Data Structure)

여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것,

데이터를 정리하고 유용하게 활용할 수 있게 정의해 놓은 것

 

왜 자료구조에 대해 공부해야 할까요?

컴퓨터가 존재하지 않던 시절에는 자료를 보관하기 위해서 직접 자료를 모아 사용해야 했습니다.

컴퓨터가 등장하고 기존의 1차원적인 기록방식(대표적으로 책) 을 그대로 사용하기엔 기록해야 할 정보의 양이 너무 많았고 컴퓨터를 활용하여 자료를 정리하고 유용하게 활용할 수 있게 도와주는 자료구조가 등장하게 되었습니다.

대부분의 자료구조는 특정한 상황에 문제를 해결하는 데 특화되어 있습니다. 각 자료구조마다 데이터를 정리하는 방식이 다르고, 당면한 문제의 성격에 따라서 제일 효율적으로 처리할 수 있는 자료구조가 존재합니다.

단적인 예를 들어 제일 기본적이고 1차원적인 자료구조인 배열에서 천만 개의 데이터 중 하나를 찾으려면 최대 천만 번의 검색을 해야 하지만 그러한 상황에 특화된 자료구조를 사용한다면 최대 25번 미만의 연산으로 원하는 데이터를 찾아낼 수 있습니다. (어떤 자료구조인지는 공부 후에 서술하겠습니다)

 

 

Stack

 

Stack의 자료구조 형태

Stack은 쌓여있는 접시 더미와 같이 작동합니다.

새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같습니다.

제일 나중에 들어온 자료가 제일 먼저 나간다고 해서 LIFO(Last in, First out) 형식이라고도 부릅니다.

Stack은 할당된 공간이 있습니다. Stack 영역이라고 부르는데 프로그램이 자동으로 사용하는 임시 메모리 영역입니다.

함수 호출 시 생성되는 지역 변수와 매개변수가 저장되는 영역이고, 함수 호출이 완료되면 사라집니다.

 

Stack에서 자료가 들어오고 나가는 곳은 하나이며, 위의 사진과 같이 Stack 자료구조의 가장 위에서 이루어집니다.

한 번에 하나의 데이터만 처리가 가능합니다. 사용 예시로는 Ctrl + z (실행 취소) / 웹 브라우저 뒤로 가기 등이 있습니다.

 

Stack의 메소드

Stack 자료구조에서 가장 최근에 입력된 데이터를 top이라고 지칭하며 스택은 top 에서만 삽입, 삭제, 읽기 동작이 발생합니다.

 

Push - Stack에 새로운 데이터를 삽입하고 top 값을 하나 증가시킵니다.

Pop - Stack 내부에서 top이 가리키고 있는 자료를 삭제한 후 top 값을 하나 감소시킵니다.

Peek - Stack에서 top이 가리키는 데이터(반환 우선순위 1순위)를 읽습니다. top 값의 변화는 없습니다.

 

 

Overflow

 

Stack / Heap Overflow

Stack 영역은 Heap 영역(클래스, 클로저 등이 동적 할당되는 메모리 공간) 과 같은 공간을 공유합니다.
Heap 영역이 메모리 위쪽 주소부터 할당되면 Stack 영역은 아래쪽부터 할당되는 식으로
같은 메모리 공간을 공유하기 때문에 각 영역이 상대 공간을 침범하는 일이 발생될 수 있습니다.
Heap 영역이 Stack 영역을 침범하면 Heap Overflow, Stack 영역이 Heap 영역을 침범시 Stack Overflow 라고 합니다.

 

Queue

 

Queue의 자료구조 형태

Queue는 줄이라는 의미를 가지고 있습니다. 줄을 서고 줄을 선 순서대로 나옵니다.

먼저 들어간 게 먼저 나오는 FIFO(First in, First out) 구조입니다. (선입선출이라는 익숙한 단어로 표현이 가능합니다)

데이터가 나가는 위치는 가장 앞이고 들어오는 위치는 가장 뒤입니다.

어떠한 작업 / 데이터 를 순서대로 실행 / 사용하기 위해 대기시킬 때 사용합니다.

Stack과 같이 한 번에 하나의 데이터만 처리가 가능합니다.

가장 오래전에 입력된 데이터를 front라고 하며 가장 최근에 입력된 데이터를 rear라고 합니다.

데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어지기 때문에 queue를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나, front 노드와 rear 노드를 관리하는 연결 리스트를 이용할 수 있습니다.

Queue는 자료를 받아들이는 배열의 크기에 제한을 두지 않기 때문에 자료가 계속해서 들어오고 나가고를 반복하면 front와 rare가 밀려 배열의 앞쪽에 텅 빈 공간이 생기게 됩니다. (자료를 제거할 때 front가 증가하기 때문) 그 약점을 보완하고자 우선순위 Queue / 환형 Queue(순환 Queue) 등이 존재합니다.

우선순위 Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 제거됩니다. (데이터의 근거와 목적에 맞게 우선순위를 결정하고 판단하는 것은 개발자의 몫입니다) 우선순위 Queue는 응급실의 모습과 비슷합니다. 응급한 환자가 우선순위가 올라가는 것처럼, 개발자가 먼저 처리하고 싶은 데이터의 우선순위를 정하게 됩니다. 우선순위 Queue 안에서 우선순위가 똑같은 자료가 중복되었을 경우 들어간 순서대로 제거됩니다. (우선순위 Queue는 heap 영역을 사용합니다) (추후 보완하여 서술하겠습니다)

 

Queue의 메소드

Insert - Queue에 새로운 데이터를 삽입하고 리스트의 끝 부분을 가리키는 rear값을 하나 증가시킵니다. (그렇기 때문에 rear의 default는 다음에 데이터가 들어오게 될 index를 가리킵니다)

Remove - Queue에서 데이터를 제거하고 front 값을 하나 증가시킵니다. front가 rear보다 커지면 더 이상 제거할 데이터가 없는 빈 Queue가 되었다는 것을 의미합니다.

Peek - Stack의 경우과 같이 Queue에서 front가 가리키는 데이터를 읽기만 하고 front 값을 변경시키지 않습니다.