자료구조 ?

자료구조란 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것이다.
데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.
데이터를 사용하려는 목적에 따라 형태를 구분하고 분류하여 사용해야한다.
데이터를 체계적으로 정리하여 저장해두는 게, 데이터를 활용하는 데 있어 훨씬 유리하다.

자료구조의 종류와 구분

자주 등장하는 네 가지의 자료구조
Stack, Queue, Tree, Graph 에 대해 학습해 보자

이전에 학습했던 배열(Array)도 대표적인 자료구조중 하나이다.

자료구조를 학습하기 위한 방법

• 각 자료구조가 가진 특징을 학습한다.
• 각 자료구조를 사용하기 적합한 상황을 이해한다.
• 다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현한다.
• 자료구조를 구현하며 자료구조의 동작원리를 이해한다.

Stack

Stack은 데이터를 순서대로 쌓는 자료구조이다.

동전쌓기에 예를 들 수 있다. 동전하나하나가 데이터이고 우리는 새로운 동전을 제일 위에 쌓을 수 있고 제일 위에 있는 동전만 가져갈 수 있다.

특징

입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.
LIFO (Last In First Out) 혹은 FILO (First in Last Out)이라 부른다.

실사용 예제

대표적으로 자주 사용하는 브라우저의 뒤로가기, 앞으로 가기 기능을 구현할 때 Stack이 활용된다.
1. 새로운 페이지로 접속시 현재 페이지를 Prev Stack에 보관
2. '뒤로 가기'시 현재 페이지를 Next Stack에 보관 Prev Stack에서 현재 페이지를 가져온다.
3. '앞으로 가기'시 Next Stack에서 현재 페이지를 가져오며 이전 페이지를 Prev Stack에 보관한다.

배열로 Stack 구현

const stack = [];
stack.push(1);
console.log(stack); // [1]
stack.push(2);
console.log(stack); // [1, 2]
stack.push(3); 
console.log(stack); // [1, 2, 3]
stack.pop(); // [3]
console.log(stack); // [1, 2]
stack.pop(); // [2]
console.log(stack); // [1]

Queue

Queue는 Stack과 반대되는 구조로 먼저 넣은 데이터가 먼저 나오는 구조이다.

톨게이트에 예를 들 수 있다. 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과한다.

특징

먼저 들어간 데이터가 먼저 나오는 구조로,
FIFO (First In First Out) 혹은 LILO (Last In Last Out)이라 부른다.

실사용 예제

컴퓨터에서도 광범위하게 활용된다.
컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 경우가 예시다.
1. 출력 버튼을 누르면 해당 문서는 임시 기억장치의 인쇄작업 Queue에 들어간다.
2. 프린터는 인쇄작업 Queue에 들어온 문서를 순서대로 인쇄한다.

Buffer

예제 처럼 장치들 사이에서 데이터를 주고받을 때 각 장치 사이에 존재하는 속도차나 시간차를 극복하기 위해 Queue를 사용한다 이것을 통틀어 Buffer라고 한다.

CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다.
대부분의 장치에서 발생하는 이벤트는 불규칙적으로 발생한다.

배열로 Queue 구현

const queue = [];
queue.push(1);
console.log(queue); // [1]
queue.push(2);
console.log(queue); // [1, 2]
queue.push(3); 
console.log(queue); // [1, 2, 3]
queue.shift(); // [1]
console.log(queue); // [2, 3]
queue.shift(); // [2]
console.log(queue); // [3]