스택과 큐란?
- 임시 데이터를 처리할 수 있는 간결한 도구 (데이터 처리 순서에 초점)
- 운영체제 아키텍쳐부터 출력 잡과 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 사용해 뛰어난 알고리즘 생성이 가능
스택
- 데이터는 스택의 끝(위)에만 삽입할 수 있다.
- 데이터는 스택의 끝에서만 삭제할 수 있다.
- 스택의 마지막 원소만 읽을 수 있다.
스택에 새 값을 삽입 === 스택에 푸시
스택의 위에서 원소를 제거하는 것 === 스택으로부터 팝
“Last In First Out” === LIFO
추상데이터 타입
- 다른 내장데이터 구조(배열, 해시테이블,,)를 기반으로 작성된 코드
스택은 내장데이터 타입이나 클래스로 딸려있지 x (구현은 사용자의 몫)
대부분의 언어가 배열을 지원하는 것과 극명하게 대조 (배열이 내장되어 있어, 컴퓨터 메모리와 직접 상호작용)
스택 생성 ⇒ 실제로 데이터를 저장할 내장 데이터 구조 중 하나 선정
class Stack{
constructor() {
// item들을 받을 배열 생성
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
read(){
if (this.items.length === 0) {
return null;
}
// items 배열의 마지막 item만 가져와준다. pop()과 다르게 배열에서 아이템이 빠지는 것이 아닌 유지된 채로 마지막 값만 받아와줌
return this.items[this.items.length - 1];
}
}원래 배열은 어떤 인덱스든 정상적으로 읽을 수 있는데, 스택 인터페이스로 배열을 사용하면 마지막 항목만 읽을 수 있다.
스택 예시
- 자바스크립트 린터 (코드를 검사하며 각 줄이 문법적으로 올바른지 확인) - (실제로 내장되어 있는 서비스이지만, 이게 잘 스택으로 구성되어 있다.!)
- 스택의 실제 적용 예시
- 여는 괄호와 닫는 괄호에만 초점
- 괄호가 아닌 모든 문자는 무시하고 넘어간다.
- 여는 괄호가 나오면 스택에 푸시한다. (스택에 넣는다는 것은 이 괄호가 닫히기를 기다린다는 뜻)
- 닫는 괄호가 나오면 스택 위에 원소를 팝해서 확인한다.
- 팝한 항목(여는 괄호)이 현재 닫는 괄호와 종류가 다른지
- 스택이 비어 팝할 수 없다면 현재 닫는 괄호에 대응하는 여는 괄호가 앞에 나오지 않은 것
- 팝한 항목이 현재 닫는 괄호와 종류가 같으면 여는 괄호를 성공적으로 닫았다는 뜻
- 줄 끝에 도달했는데, 스택에 여전히 남아있는 괄호가 있다면 여는 괄호에 대응하는 닫는 괄호가 없다는 뜻
class Linter {
constructor() {
this.stack = [];
}
lint(text) {
for (const char of text) {
if (this.is_opening_brace(char)) {
this.stack.push(char); // Use char instead of item
} else if (this.is_closing_brace(char)) {
const popped_opening_brace = this.stack.pop();
if (!popped_opening_brace) return `${char} doesn't have an opening brace`;
if (this.is_not_match(popped_opening_brace, char)) return `${char} has a mismatched opening brace`;
}
}
if (this.stack.length !== 0) {
const remainingOpeningBrace = this.stack.pop(); // get the remaining unclosed brace
return `${remainingOpeningBrace} does not have a closing brace`;
}
return true;
}
is_opening_brace(char) {
return ["(", "[", "{"].includes(char);
}
is_closing_brace(char) {
return [")", "]", "}"].includes(char);
}
is_not_match(opening_brace, closing_brace) {
// Define matching pairs
const matchingBraces = {
"(": ")",
"[": "]",
"{": "}",
};
// Return true if there's a mismatch
return matchingBraces[opening_brace] !== closing_brace;
}
}📌 스택은 내부적으로 배열을 사용하는데 꼭 스택을 써야할까?
스택 (제약을 갖는 배열) === 스택이 하는 일은 배열도 할 수 있다.
1. 제약을 갖는 데이터구조를 사용하면 잠재적버그를 막을 수 있다.
- 스택 위 항목을 제외하고는 삭제할 수 없으므로 스택을 사용하면 위에서만 항목을 제거한다.
2. 스택같은 데이터 구조는 문제를 해결하는 새로운 사고모델을 제공한다.
- LIFO 프로세스에 대한 전반적인 아이디어 제공
스택 예시 - 워드 ‘되돌리기’
큐
- 데이터는 큐의 끝(위)에만 삽입할 수 있다.
- 데이터는 큐의 앞에서만 삭제할 수 있다.
- 큐의 앞에 있는 원소만 읽을 수 있다.
큐에 새 값을 삽입 === 인큐
큐에서 **원소를 제거하는 것 === 디큐**
First In First Out” === FIFO
class Queue{
constructor() {
// item들을 받을 배열 생성
this.items = [];
}
enqueue(item) {
this.items.push(item);
}
dequeue() {
return this.items.shift();
}
read(){
return this.items[0];
}
}enqueue 메소드는 배열 끝에 데이터를 삽입
dequeue 메소드는 배열에서 첫번째 항목을 제거
read 메소드는 배열의 첫 번째 원소만 본다.
큐 예시
- 프린터 출력 class
class Printer{
constructor() {
// item들을 받을 배열 생성
this.items = [];
}
queue_print_job(document) {
this.items.push(document);
}
// 프린트 작업을 실행하는 메서드
run() {
while (this.items.length > 0) {
this.print(this.items.shift()); // 첫 번째 프린트 작업을 실행하고 제거
}
print(docment){
console.log(document);
}
}프로그램은 요청받은 순서대로 문서를 출력한다.
큐는 요청받은 순서대로 요청을 처리하므로 비동기식 요청을 처리하는 완벽한 도구
