2022.08.12(Fri)
[TIL] Day76
[SEB FE] Day77
☑️ 자료구조
여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
👉 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없음
☑️ Stack
데이터를 순서대로 쌓는 자료구조
- 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
LIFO(Last In First Out) /FILO(First In Last Out)- Stack에 데이터를 넣는 것:
PUSH- Stack에서 데이터를 꺼내는 것:
POP
🔹 Stack 특징
-
LIFO(Last In First Out)
: 먼저 들어간 데이터를 제일 나중에 나오는 후입선출 구조
⇒ Stack 구조는 조회 필요 ❌ → 데이터 저장&검색 프로세스 매우 fast
👍 최상위 블록에서 데이터를 저장하고 검색하면 됨 -
데이터는 하나씩 넣고 뺄 수 있음
: 한꺼번에 여러 개를 넣거나 뺄 수 없음 -
하나의 입출력 방향을 가지고 있음
: 데이터 입출력 방향이 같음 -
저장되는 데이터는 유한하고 정적이어야 함
-
스택 크기는 제한되어 있음
⇒Stack Overflow와 같은 에러가 자주 발생
☑️ Queue
줄을 서서 기다리다, 대기행렬 뜻 의미
FIFO(First In FIrst Out) /LILO(Last In Last Out)- 입력과 출력 방향이 고정되어 있으며, 두 곳으로 접근 가능
- Queue에 데이터를 넣는 것:
enqueue- Queue에서 데이터를 꺼내는 것:
dequeue- data가 입력된 순서대로 처리할 때 주로 사용
🔹 Queue 특징
-
FIFO(First In First Out)
: 먼저 들어간 데이터가 제일 처음에 나오는 선입선출 구조
-
데이터는 하나씩 넣고 뺄 수 있음
: 한꺼번에 여러 개를 넣거나 뺄 수 없음 -
2개의 입출력 방향을 가지고 있음
: 데이터 입력, 출력 방향이 다름
✋ 컴퓨터 장치 사이의 속도/시간 차이 극복을 위해 임시 기억 장치 자료구조로 Queue 사용 ⇒ Buffer
👉 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 Buffer 사용
☑️ Stack & Queue 코드로 구현해보기
🔸 class 키워드로 사용자 정의 데이터 타입 생성 → Stack & Queue의 데이터 타입 정의
// class로 Stack 구현
class Stack {
// stack constructor 생성
constructor() {
this.storage = {};
this.top = 0;
}
// [stack 사이즈 구하기]
// this.top: 스택에 새롭게 추가될 요소의 인덱스를 나타냄 => 전체 요소 개수 나타낼 수 있음
// this.top => 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로 size를 구할 수 있음
size() {
return this.top;
}
// [stack에 element 추가]
push(element) {
// key: this.top, value: element(요소) => storage에 할당
this.storage[this.top] = element;
// this.top => 다음 인덱스를 가리키게 하여 새로운 요소에 대비
this.top += 1;
}
// [stack에서 element를 제거한 뒤 해당 element 반환]
pop() {
// size = 0 즉, 빈 스택이라면 아무것도 수행 x
if (this.size() === 0) {
return;
}
// top-1로 최상단 설정 후, result 변수에 저장하고,
const result = this.storage[this.top - 1];
// stack에서 삭제
delete this.storage[this.top - 1];
// 하나 제거했으므로 top도 -1 감소
this.top -= 1;
return result;
}
}// class로 Queue 구현
class Queue {
//queue constructor 생성
constructor() {
this.storage = {};
//가장 앞에 있는 요소 = front,
this.front = 0;
//가장 뒤에 있는 요소 = rear
this.rear = 0;
}
// [queue 사이즈 구하기]
// 추가될 땐 rear값 증가, 삭제 될 땐 front 변경 => rear, front로 사이즈 구할 수 있음
size() {
return this.rear - this.front;
}
// [queue에 element 추가]
enqueue(element) {
// key: [this.rear], value: element(요소) => storage에 할당
this.storage[this.rear] = element;
// this.rear => 다음 인덱스를 가리키게 하여 새로운 요소에 대비
this.rear += 1;
}
// [queue에서 element를 제거 한 뒤 해당 element 반환]
// 가장 먼저 추가된 데이터가 가장 먼저 추출!
dequeue() {
// size = 0 즉, 빈 스택이라면 아무것도 수행 X
if (this.size() === 0) {
return;
}
// front로 최상단 설정 후, result 변수에 저장 후
const result = this.storage[this.front];
// queue에서 삭제
delete this.storage[this.front];
this.front += 1;
return result;
}
}🔸 생성한 사용자 정의 데이터 타입은 Stack & Queue을 Array & Object처럼 사용 가능
// 배열로 Stack 구현
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]
stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]
console.log(stack); // [1, 2, 3]
// 배열로 Queue 구현
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]
queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]
console.log(queue); // [3, 4, 5]
✋ Stack을 사용자 정의 데이터 타입으로 정의하면, new 키워드를 통해 새로운 인스턴스 생성 가능
⇒ 생성한 인스턴스를 통해 다양한 메서드 사용 가능
✅ Coplit 문제는 github에 코드 정리해놓기 ~@!
