1. 자료구조 - 배열, 스택, 큐, 덱

* 개인적으로 이해한 내용을 기반으로 정리한 글이기 때문에 정확하지 않은 내용에 대한 피드백 적극 수용

 

자료구조란?

컴퓨터가 데이터를 효과적으로 활용하기 위해 정형화 시킨 자료 처리 단위

 

※ 컴퓨터가 작업을 수행하는 과정

목적 : 사용자의 요청수행 혹은 프로그램 화면 출력

수행에 필요한 데이터를 RAM에 올라온 상태에서 CPU를 통해 작업을 처리한다

(캐시나 다른 방식도 있지만 현재로써는 제외한다)

 

배열

사용자가 입력한 데이터를 메모리에 순차적으로 하나씩 쌓는것

순차적 = 연속적인 메모리 공간 할당

 

장점 : 데이터 접근에 용이, 빠른 속도 (바로 다음칸에 다음 데이터가 존재)

단점 : 공간 할당 (인덱스 에러, 메모리 낭비)

 

 

※ 배열과 리스트 차이

배열 - 한번 선언하면 변수를 지우기전 까지 메모리 크기 고정 = 메모리 낭비

리스트 - 필요할때마다 공간 할당 가능 = 관리 편함, 검색 불편

 

 

 

이제 배열의 개념을 기반으로 한 스택과 큐, 데크를 알아봅니다

 

 

스택

한쪽이 막힌 파이프관 FILO

제일 먼저 들어간 데이터가 가장 늦게 나온다. 왜? 제일 밑에 깔려있으니까

파이프 구조라서 끝에서 부터 순차적으로 탐색하는 과정없이 중간에서 데이터를 바로 빼낼 수 없음

카페에서 마우스 패드로 급하게 그림판을 통해 그린 스택의 모습이다

스택 구조에서 많이 헷가리는 부분이 '데이터가 쌓이면 주소값이 커져야하는거 아닌가?' 하는 부분이다.

이는 돈으로 생각하면 쉽게 해결할 수 있는 부분이다

 

메모리 총 공간 : 초기자본

데이터 : 내가 산 물건

메모리 주소 : 잔액

 

내가 초기 자본이 500원 있다고 가정을 하자 = 메모리 총 공간 500 (그림에서는 바닥의 크기 100도 포함시켜야 하기 때문에 500)

100원짜리 물건 3개를 구입한다 = 메모리 크기 100의 공간을 3개 할당한다

그러면 내 잔액은 500 - 100*3 으로 200만큼 남는다 = 마지막 할당된 데이터는 200의 주소를 가진다

이때 주의할 점은 100원짜리 물건의 가격 (할당되는 데이터 크기 단위) 은 100으로 고정되어 있다는 것이다. 

이 크기를 결정하는 요인은 각 컴퓨터마다 다르다. 자세한 내용은 알고리즘과 큰 관련이 없기 때문에 상세내용은 생략한다.

 

 

큐

FIFO

양쪽이 다 뚫린 파이프. 먼저 넣은 데이터가 먼저 나옴

스택을 이해하셨다면 큐는 크게 어려울 것 없을 것이라 생각합니다

말그대로 앞뒤 뚫려있는 구조라서 먼저 들어간놈이 먼저 나옵니다

 

 

덱

스택 + 큐

원하는 방향에서 데이터를 추출할 수 있는 구조

생각보다 쓰는 모습을 본적이 없음