스택과 큐는 기본적으로 데이터를 순차적으로 나열시킨 선형 구조다! 이를 알고 선형을 쓰는 자료구조를 배워보자
후입선출, 스택은 말 그대로 데이터를 쌓아 올린다. 데이터(data)를 순서대로 쌓는 자료구조
LIFO(Last In First Out) 정책을 가지고 있음(나중에 들어간 데이터가 먼저 나옴), 반대인 FILO로 부르는 사람도 있음
예1) 1, 2, 3, 4를 스택에 차례대로 넣는다.
stack.push(데이터)
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.
예2) 스택이 빌 때까지 데이터를 전부 빼낸다.
stack.pop()
---------------------------
---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 된다.
직접 스택을 구현해보자.
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
}
size() {
return this.top;
}
// 스택에 데이터를 추가 가능
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생 X
if (this.size() === 0) {
return;
}
// 마지막 top은 마지막 요소가 8이고 추가한 뒤 +1해줬기 때문에 마지막 요소 없앨라면 -1
const result = this.storage[this.top - 1];
delete this.storage[this.top - 1];
this.top -= 1;
return result;
}
}
// 결과
const stack = new Stack();
stack.size(); // 0
for(let i = 1; i < 10; i++) {
stack.push(i);
}
stack.pop(); // 9
프로토타입으로 만들기 위해 클래스 함수에다가 ⭐️top
이라는 포인터 변수를 만들어 가장 최근에 어떤 걸 넣었는지 알 수 있게 선언했다. 걍 인덱스를 객체형식으로 만들어 준거임
선입선출, 데이터를 줄 세워 순서에 맞게 데이터를 관리
데이터를 넣는 것을enqueue
, 데이터를 꺼내는 것을dequeue
FIFO(First-In-First-Out) 정책을 가짐(먼저 들어간 데이터가 먼저 나옴)
먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조
예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.
queue.enqueue(데이터)
출력 방향 <---------------------------< 입력 방향
1 <- 2 <- 3 <- 4
<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.
queue.dequeue(데이터)
출력 방향 <---------------------------< 입력 방향
<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.
Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없음
Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없음
직접 큐를 구현해보자.
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return this.rear - this.front;
}
// 큐에 데이터를 추가하게
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생 X
if (this.rear - this.front === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}
// 출력값
const queue = new Queue();
queue.size(); // 0
for(let i = 1; i < 10; i++) {
queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
front
는 앞 인덱스, rear
는 뒤 인덱스로 설정한 포인터 변수
아까 전까지 새로운 클래스를 만들어 구현해봤다. 익숙한 이름도 봤지만 배열으로 스택/큐의 메소드를 구현할 수 있다. 바로 Array.prototype.shift()
, Array.prototype.pop()
들로 구현하는 것! 자료구조는 구현 방식에 제한이 없으니까~
꼭 알아둘 것이 shift
같은 경우는 인덱스 값 자체가 바뀌어버리니 주의하기~
코스 코플릿과 프로그래머스의 문제를 가져왔다.
이런식으로
false
출력. 방문한 페이지의 개수는 100개 이하const actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
const start = "A";
const output = browserStack(actions, start);
console.log(output); // [["A"], "B", ["A", "D"]]
const actions2 = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1];
const start2 = "A";
const output2 = browserStack(actions2, start2);
console.log(output2); // [["A", "B"], "D", ["E"]]
function browserStack(actions, start) {
// 제한요건 제외
if (typeof start !== "string") {
return false;
}
// prev 스택, next 스택, 현재 페이지 만들기
let prev = [];
let next = [];
let current = start;
/* 조건
* 1. 새알파벳: prev에 현재페이지 넣고 알파벳 현재페이지에 넣기
* 2. 뒤로가기: prev가 0이 아닐 때와 -1
* 3. 앞으로가기: next가 0이 아닐때와 1
*
*/
for (let i = 0; i < actions.length; i++) {
// 1: 주의- 새 페이지로 넘어가면 앞에거 다 없어지고 현재페이지만 남게되니 초기화 必
if (typeof actions[i] === "string") {
prev.push(current);
current = actions[i];
next = [];
}
// 2: 현재 페이지 next에 넣고 prev에서 최상위 값 가져오기(순서 잘맞추기)
else if (prev.length !== 0 && actions[i] === -1) {
next.push(current);
current = prev.pop();
}
// 3: 현재-prev, next에서 최상위 값
else if (next.length !== 0 && actions[i] === 1) {
prev.push(current);
current = next.pop();
}
}
return [prev, current, next];
}
function queuePrinter(bufferSize, capacities, documents) {
//buffersize : 인쇄 작업 목록 크기
//capacities : 최대로 담을 수 있는 문서의 용량
//time: 인쇄대기목록에 documents 문서들 모두 넣는데 걸리는 시간
let time = 0;
//printList : buffersize 의 길이를 가지는 배열 만들어놓기 , 0으로 다채우기
let printList = Array(bufferSize).fill(0); //[0,0]
while (documents.length !== 0) {
//가장 먼저 대기중인 인쇄 대기열 첫번째 문서 출력
printList.shift();
//현재 인쇄 대기 목록에 있는 총 용량의 크기
let currentCap = printList.reduce((acc, cur) => acc + cur, 0); //[0,7] [7, 4]
if (currentCap + documents[0] <= capacities) {
// [0,0] 7 => 7 / 10
//인쇄할 documents[0] 을 현재 인쇄 대기목록에 추가해도 capacities 를 넘지 않는다면
//인쇄 대기 목록에 해당 문서를 push 하고
//기존의 documents 에서는 해당 문서는 이제 대기 목록으로 갔으니 shift로 제거 4,5,6
printList.push(documents.shift());
} else {
//capacities 를 초과한다면
//인쇄 대기 목록에 들어갈 수 없고
//더미 데이터인 0을 맨 뒤에 추가(어차피 매 순환마다 shift 를 통해 인쇄 대기열 맨 앞 원소 하나씩 빠짐)
printList.push(0);
//[0,0]
//[0,7] 4 >10 x
//[0,7,0]
//[7, 0]
}
//documents 원소가 들어가거나 공간 확보시마다 1초씩 time 증가 계산
time++;
}
//인쇄완료하는데 걸리는 시간 = 문서들 모두 대기 목록에 넣는 시간 + 해당 대기목록 크기(=프린트할 문서 갯수)
return time + bufferSize;
}