여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고 활용하기 위해 선배 개발자들이 연구해둔 방법이 자료구조라고 할 수 있겠다!
자료구조의 종류는 당장 구글에 자료구조 분류라고 쳐보면 알 수 있듯이 굉장히 많은데,
이번 유닛에서는 그 중에서 가장 많이 사용되고, 알고리즘 테스트에 자주 등장하는 Stack, Queue, Tree, Graph를 학습한다고 한다.
오늘 배운 건 Stack과 Queue 두가지이다.
데이터를 순서대로 쌓는 자료구조
대표적으로 앞으로 가기, 뒤로 가기 기능을 구현할 때 stack을 사용할 수 있다.
//앞으로 가기, 뒤로 가기 구현
function browserStack(actions, start) {
//출력되는 값은 배열 : [prev 스택, 현재 위치, next 스택]
//브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않는다.
//**비활성화 되었을 때 === 해당 버튼의 stack이 비었을때**
//prev에 아무것도 없거나 next에 아무것도 없을 때
const prev = [];
let now = start;
const next= [];
//예외 조건 제외(start의 인자로 string 자료형이 아닌 다른 자료형이 들어온다면 false를 리턴)
if(typeof start !== 'string'){
return false;
}
for(let i=0;i<actions.length;i++){
if(actions[i] === 1 && next.length !== 0 ){
//앞으로 가기 버튼을 누를 경우 (+1) && next가 비어있지 않은 경우
//원래 있던 페이지를 prev 스택에 넣는다
//next 스택의 top에 있는 페이지로 이동한다
//next 스택의 값을 pop한다 (현재 페이지가 되었으니 prev 스택에서 제거하는 것)
prev.push(now);
now = next[next.length-1];
next.pop();
}else if(actions[i] === -1 && prev.length !== 0){
//뒤로 가기 버튼을 누를 경우 (-1) && prev가 빈 배열이 아닐 경우
//원래 있던 페이지를 next 스택에 넣는다
//prev 스택의 top(포인터)에 있는 페이지로 현재 페이지를 이동한다
//prev스택의 값을 pop 한다 (현재 페이지가 되었으니까 prev 스택에서 제거하는 것)
next.push(now);
now = prev[prev.length-1];
prev.pop();
}else if(typeof actions[i] === 'string'){
//새로운 페이지로 접속할 경우
//prev 스택에 원래 있던 페이지를 넣는다
//next 스택을 비운다
prev.push(now);
next.splice(0);
now = actions[i];
}//마지막 조건이 else가 아니고 else if인 이유는
//뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우에는 아무것도 해주지 않기 위해서
//else를 하게 되면 actions[i]가 새로운 페이지인 경우와
//뒤로 가기, 앞으로 가기 버튼을 눌렀지만 next나 prev가 비어있는 경우가 합쳐져서 잘못된 결과가 나오기 때문
}
return [prev,now,next];
}
stack과 반대되는 개념.
먼저 들어간 데이터가 먼저 나오는 선입선출 방식으로 Queue에 데이터를 넣는 것을 enqueue, 데이터를 꺼내는 것을 dequeue라고 함.
데이터가 입력된 순서대로 처리할 때 Queue를 사용.
문서 순서대로 인쇄하기 (컴퓨터 출력 버튼 ⇒ Queue에 하나씩 들어옴 ⇒ Queue에 들어온 문서를 순서대로 인쇄)
//인쇄 구현하기
function queuePrinter(bufferSize, capacities, documents) {
//아직 채워지지 않은 빈 작업 목록 칸은 0으로 채운다
let printerQueue = new Array(bufferSize).fill(0);
//첫번째 문서를 documents에서 제거하면서 해당 값을 printerQueue의 맨 뒤에 넣는다
printerQueue[printerQueue.length-1] = documents.shift();
//시간은 1초 지남
let time = 1
//sum은 printerQueue의 모든 용량의 합이다 (sum을 통해서 새로운 문서를 queue에 추가할 수 있는지 없는지 판별한다)
let sum = printerQueue[printerQueue.length-1]
//queue 속의 용량 값이 0이 되면 반복문을 종료하도록 한다 (더 이상 프린트 할 문서가 없을 때)
while(sum>0){
//아래의 sum 변경은 queue의 맨 앞에 있던 문서가 프린트되어 진 뒤에 queue에 남은 용량을 계산한다
//처음에는 sum - 0이겠지만, 점점 문서가 이동해서 queue의 맨 첫번째 자리에 오고, 프린트가 되면 sum에서 해당 용량이 제거됨
sum = sum - printerQueue.shift()
//프린트 된 문서의 용량이 제거되고 난 뒤에 sum과 새롭게 queue에 들어오고 싶어하는 documents[0]의 합이 capacities보다 큰지 확인한다
//만약 용량제한보다 크면 queue에 추가할 수 없고, 새로운 문서가 들어오지 않은 자리에는 0을 넣어준다.
//만약 용량제한보다 작거나 같아서 queue에 추가할 수 있게 되면 documents에서 첫번째 요소를 제거하면서 printerQueue에 넣어준다
//두 경우 다 시간을 증가시켜주어야 한다.
if(documents.length>0 && sum + documents[0] <= capacities){
sum = sum + documents[0];
printerQueue.push(documents.shift());
time += 1;
}else{
printerQueue.push(0);
time+= 1;
}
}
return time;
}
자료구조라는 건 데이터를 다루는 구조 그 자체를 뜻하는 거라 구현하는 방식에는 제약이 없다.
과제에서는 우선 클래스로 stack과 queue를 구현했지만, 배열로도 stack 자료구조를 구현하거나, queue 자료구조를 구현할 수 있음.
//Stack 구현
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 포인터 변수를 초기화
}
//스택의 크기를 반환하는 매서드
size() {
return Object.keys(this.storage).length;
}
// 데이터를 추가하는 매서드
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// 데이터 추출하는 매서드
pop() {
// 빈 스택에 pop 연산을 적용하는 경우 제외하기
if (Object.keys(this.storage).length === 0) {
return;
}
const result = this.storage[this.top-1];
delete this.storage[this.top-1];
this.top -= 1;
return result;
}
}
//Queue 구현
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return Object.keys(this.storage).length
}
// 큐에 데이터를 추가 하는 매서드
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 데이터를 추출하는 매서드
dequeue() {
// 빈 큐에 dequeue 매서드 사용하는 경우 제외하기
if (Object.keys(this.storage).length === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}