자료구조란? 🧐

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것으로 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다. 즉 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다. 특히 문제 해결력을 필요로 하는 알고리즘 테스트(코딩 테스트)와 굉장히 밀접한 연관성이 있는데, 특정 문제를 해결하는 데에 적합한 자료구조를 찾아 데이터를 정리하고 활용할 줄 알면, 상황에 가장 적합하고 정확한 코드를 작성할 수 있다!

자주 등장하는 자료구조 : Stack, Queue, Tree, Graph

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있는데 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조를 말한다.

Stack의 특징

1. LIFO(Last In First Out / 후입선출)

• 가장 먼저 들어간 데이터는 가장 나중에 나오는 구조
• 하지만 이런 특성으로 인해 스택 구조 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있음
• 데이터를 저장할 때나 검색할 때 항상 스택의 최상단에서만 행위가 이루어지며 이에 따라 데이터를 저장하고 검색하는 프로세스가 매우 빠르다

2. 하나의 입출력 방향을 가지고 있다.

• 데이터를 넣을 때 스택의 가장 최상단으로 넣고(입력) 뺄 때 또한 스택의 가장 최상단으로 데이터를 뺄 수(출력) 있다.

3. 데이터는 하나씩 넣고 뺄 수 있다.

• 스택에 한개 씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만을 뺄 수 있다.

배열로 자료구조 Stack 구현하기

//const stack = new Array(); 미리 정의된 Array 객체를 사용할 수 있습니다.
const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]

console.log(stack); // [1, 2, 3, 4, 5]

//제일 마지막에 들어간 요소부터 빼내기 위해 pop() 메소드를 사용합니다.
stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]

console.log(stack); // [1, 2, 3]

Queue

자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터가 먼저 나오는 특징으로 가지고 있습니다. 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 이 자료구조는 입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 입력할 시에는 큐의 끝에서(tail), 데이터를 출력할 때는 큐의 맨 앞에서(head) 진행된다. 여기에서 Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.

Queue의 특징

1. FIFO (First In First Out / 선입선출)

• 먼저 들어간 데이터가 제일 처음에 나오는 구조

2. 두 개의 입출력 방향을 가지고 있다.

• 큐는 데이터를 입력하는 곳과 출력하는 곳이 각각 정해져 있으며 이렇게 총 2개의 입출력 방향을 가지고 있다.
• 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없음!

3. 데이터는 하나씩 넣고 뺄 수 있다.

• 큐에 한 개 씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있다.

배열로 자료구조 Queue 구현하기

//const queue = new Array(); 미리 정의된 Array 객체를 사용할 수 있습니다.
const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]

console.log(queue); // [1, 2, 3, 4, 5]

//제일 먼저 들어간 것부터 빼내기 위해 shift() 메소드를 사용합니다.
queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]

console.log(queue); // [3, 4, 5]