🌱 What I learned today
✨ Data Structure
✨ Queue
✨ Stack
🌱 Data Structure (자료 구조)
여러 데이터들의 묶음을 어떻게 '저장' 하고 '사용'할지 정의한 것.
🌱 Queue
그림에서 보여지듯이
Queue는 편의점 맥주 진열대와 비슷하다.
편의점 알바생이 갓 들어온 맥주를 진열하기 위해선
맥주 진열대 뒤에서 맥주를 추가하고
손님은 순서대로 진열된 맥주를 냉장실 문을 열어
제일 앞에 있는 맥주를 꺼내는 그림이 연상이 된다.
다른 비유는 Queue는
놀이공원에서 놀이기구를 타기 위해 서있는 대기줄이라 비유하기도 한다.
아래 사진은 실제로 Queue가 실제로 작동되는 모습을 그림으로 나타낸 것이다.
위의 그림처럼
Queue는 자료를 맨 마지막(tail)에 집어넣고(Enqueue), 빼낼 때는 제일 첫번째(head)에 위치한 먼저 들어간 값부터 빼낸다(Dequeue).
즉, Queue는 선입선출 (FIFO: First in, First out)의 자료구조 형태로 돌아간다.
"먼저 줄 선 사람, 먼저 놀이기구 타세요!"
🌱 Queue에 사용되는 메소드 등
-
.storagethis.storage = {}; / / Queue 전용 그릇 —→ obj
-
.front제일 먼저 들어온 원소
-
.rear제일 최근에 들어온 원소
-
size()-
큐의 현재 요소 개수를 반환합니다.
-
Object.keys(obj) ⇒ Object.keys(this.storage)를 사용하면 좋다.
a. 키가 담긴 배열을 반환
b. Object.keys(storage).length 로 활용
-
-
enqueue(element)데이터를 담기 위한 메소드로 → 요소를 큐의
뒤에추가``합니다. -
dequeue()데이터를 빼내기 위한 메소드로 → 큐의 제일 첫번째에 있는 요소를
제거하고반환합니다.위의 메소드 등을 활용하면 아래와 같은 기본적인 코드가 구현된다.
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() { //Object.keys(obj) – 키가 담긴 배열을 반환합니다.
if (Object.keys(this.storage).length === 0) {
return 0;
}
return Object.keys(this.storage).length;
}
enqueue(element) {
this.storage[this.rear++] = element;
}
dequeue() {
if (this.rear > this.front) {
let res = this.storage[this.front];
delete this.storage[this.front++];
return res;
}
}
}
module.exports = Queue;🌱 언제 쓰일까?
어떠한 작업 & 데이터를 순서대로 실행하기 위해 대기시킬 때 사용한다고 한다.
네트워크에서의 버퍼 등 밀려드는 수많은 요청을 순차적으로 처리할 필요가 있는 프로그램에서 사용된다.
* 버퍼(buffer)란?
데이터를 한 곳에서 다른 한 곳으로 전송하는 동안,
일시적으로 그 데이터를 보관하는 메모리 영역.
즉 버퍼링은 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미한다.
다른 말로 'Queue'라고도 표현한다.
(출처:https://images.app.goo.gl/uhxwcKhXd1M4cRot5)
🌱 Stack
간단한 비유를 프링글스로 들어보겠다.
프링글스는 길다란 통에 꼭대기에만 넣고 뺄 수 있는 입구 1개만 존재한다.
따라서 맨 하단에 깔려있는 과자를 빼낼 수가 없다.
이렇듯 Queue와는 달리 Stack은 프링글스와 동일한 원리로 작동이 된다.
다른 말로 하면,
후입선출(LIFO - Last In First Out) 형태의 자료구조라고도 할 수 있다.
"늦게 들어 온 놈이 먼저 나간다."
좀 더 수월한 이해를 돕자면 아래 그림을 참고하자.
[Stack = 하노이의 탑과 유사]
🌱 Stack의 필요한 메소드 등
-
.storagethis.storage = {}; / / Stack의 전용 그릇 —→ obj
-
top최상단 값만 리턴하고, 데이터에는 아무런 영향을 주지 않는다. pop과 다름에 주의!
그리고 가장 먼저 입력되에 바닥에 깔린 데이터를 bottom이라고 하며 다중 스택 같은 특별한 구조가 아니라면 이 값은 0으로 고정되어 있다
-
size()-
Stack의 현재 요소 개수를 반환합니다.
-
Object.keys(obj) ⇒ Object.keys(this.storage)를 사용하면 좋다.
a. 키가 담긴 배열을 반환
b. Object.keys(storage).length 로 활용
c. 혹은 this.top을 그대로 리턴도 가능
-
-
push(element)데이터를 담기 위한 메소드로 → 요소를 Stack의 최상단에
추가합니다. -
pop()데이터를 빼내기 위한 메소드로 → Stack의 최상단에 있는 요소를
제거하고반환합니다. -
peek(element)-
Stack 에서 top이 가리키는 데이터를 읽는 작업.
-
top의 값의 변화는 X
이 코드를 따라 작성하기보다는 어떻게 구현이 되었는지 참고하길 바랍니다.
저는 코드의 다양성을 존중합니다.
위의 메소드 등을 활용하면 아래와 같은 기본적인 코드가 구현된다. -
const { object } = require("underscore");
class Stack {
constructor() {
this.storage = {};
this.top = 0;
}
//push (a), pop(), push(b), pop()
size() {
if (Object.keys(this.storage).length === 0) {
return 0;
} // 이거말고 return this.top; 으로도 해결 가능
return Object.keys(this.storage).length;
}
push(element) {
this.storage[++this.top] = element; //{1: 'a'} this.top = 1
}
pop() {
if (this.top > 0) {
let res = this.storage[this.top]; //{1: 'a'}
delete this.storage[this.top--]; //{1: 'a'} this.top 1 pop 끝나고 top은 0
return res;
}
}
}
module.exports = Stack;끝!
Q) 다음과 같은 코드의 실행 결과는?
function calc(expression) {
// 1. 문자를 하나씩 검사한다.
// 2. 숫자를 만나면 숫자를 스택에 푸시한다.
// 3. 연산자를 만나면 스택에서 팝을 두 번 하고, 두 개의 숫자를 가지고 연산한다. //제거하고 반환하는 것이니 반환된것 끼리 아까 만난 연산자로 연산하기 ->(3 * 9))
// 4. 3의 연산 결과를 다시 스택에 푸시한다. // (27)
// 5. 문자열이 끝날 때 까지 반복한다. (27 15 5) -> pop으로 반환된 값 === (15, 5)-> 15/5 === 3 -> 다시 푸시 (3 27) -> 3 + 27 === 30 -> (2, 30)--> 2개 pop--> (30, 2)-> 30-2===28)
// 6. 문자열이 끝나면 연산 결과 값을 리턴한다.
}
const result = calc("9 3 * 15 5 / + 2 -")
console.log(result); // 28Q) 큐에 대한 설명 중 틀린 것을 모두 고르면?
**A**
먼저 들어간게 먼저 나오는 First In First Out 구조이다.
**B** 📌
먼저 들어간게 나중에 나오는 First In Last Out 구조이다.
**C**
dequeue는 큐의 가장 앞에 있는 값을 꺼내서 반환한다.
**D**
rear는 큐의 마지막 값의 인덱스를 가리킨다.
**E**📌
하노이의 탑의 구조는 큐와 유사하다.