🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
스택(Stack)의 개념과 구현
📍 스택(Stack)
👉🏻 단순한 규칙을 가지고 있는 리스트
👉🏻 FILO(First In Last Out): 먼저 들어온 데이터가 나중에 쓰이는 리스트
👉🏻 ex) 쌓은 그릇을 위에서부터 씀
👉🏻 먼저 들어온 데이터를 나중에 쓰기만 한다면 어떤 자료 구조를 쓰더라도 상관없음
: 데이터 삽입/삭제를 무조건 첫 번째 인덱스로 한다면 연결 리스트로도 구현 가능
👉🏻 차례가 중요할 때는 쓸모없으나 Ctrl + z(되돌리기), 자바 스크립트 괄호 문법 검사와 같은 기능에서는 매우! 유용!
📍 스택(Stack)의 구현
👉🏻 추상 자료형 정의
1. push - 데이터 삽입2. pop - 데이터 제거3. peek - top에 있는 데이터 참조4. isEmpty - 스택이 비었는지 체크
[ Stack.mjs ]
import { LinkedList } from './LinkedList.mjs';
class Stack {
constructor() {
this.list = new LinkedList();
}
push(data) {
this.list.insertAt(0, data);
}
pop(data) {
try{
return this.list.deleteAt(0);
} catch(e) {
return null;
}
}
peek() {
return this.list.getNodeAt(0);
}
isEmpty() {
return (this.list.count == 0);
}
}
export { Stack };[ test_stack.mjs ]
import { Stack } from './Stack.mjs';
let stack = new Stack();
console.log("===== 첫 번째 출력 =====");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log("===== 두 번째 출력 =====");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.peek().data);
// peek 함수 호출해도 stack에서 데이터가 제거되지는 않음
stack.pop();
console.log(stack.peek().data);
console.log(`isEmpty: ${stack.isEmpty()}`); // false
stack.pop();
stack.pop();
stack.pop();
console.log(`isEmpty: ${stack.isEmpty()}`); // true
console.log(stack.pop()); // 빈 스택에서는 null 출력
🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
큐(Queue)의 개념과 구현
📍 큐(Queue)
👉🏻 FIFO(First In First Out): 먼저 들어간 데이터가 먼저 나오는 방식
👉🏻 ex: 운영체제가 프로세스 작업 요청을 순서대로 큐에 넣고 CPU가 순서대로 꺼내서 처리함(FIFO 스케쥴링)
👉🏻 연결 리스트로 구현하기 위해서는 삽입은 가장 앞에서, 삭제는 가장 뒤에서부터 진행(단방향 연결 리스트)
: 삽입은 유용하나 삭제의 경우 헤드를 타고 O(n)의 성능으로 접근하기 때문에 메모리 낭비됨
그래서, tail(가장 마지막 노드를 가리킴) 함수를 만들어 줌으로써 O(1)의 성능을 가지게끔 함
단, 삭제된 마지막 노드의 이전 노드를 가리킬 수 없음(단방향이기 때문에 결국 다시 head부터 참조해 와야 함) = O(n)의 성능
✔️ 결론: tail 함수 추가 후 이중 연결 리스트로 이전 노드도 참조할 수 있게 함
📍 큐(Queue)의 구현
👉🏻 추상 자료형 정의
1. enqueue - 데이터 삽입
2. dequeue - 데이터 제거
3. front - 가장 먼저 들어간(tail이 가리키고 있는) 데이터를 참조
4. isEmpty - 큐가 비었는지 확인
[ LinkedList.mjs를 DoublyLinkedList.mjs로 수정 ]
class Node{
// 클래스를 인스턴스화 했을 때 자동으로 호출되는 생성자 만들기
constructor(data, next = null, prev = null){
// 생성자로 초기화
// next 기본값: null
// data는 필수지만 next는 입력하지 않을 경우 null 들어옴
// 클래스 내의 변수: 프로퍼티
this.data = data;
this.next = next;
this.prev = prev; // 추가
}
}
class DoublyLinkedList {
constructor(){
// 매개변수 필요 없음
this.head = null;
this.tail = null; // 추가
this.count = 0; // 총 노드 개수
}
printAll() {
let currentNode = this.head;
let text = "[";
while(currentNode != null) {
text += currentNode.data;
currentNode = currentNode.next;
if(currentNode != null) {
text += ", ";
}
}
text += "]";
console.log(text);
}
// 리스트 모든 함수 제거
clear() {
this.head = null;
this.count = 0;
}
// 함수의 원형
insertAt(index, data) {
if(index > this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
// 삽입할 노드 생성
let newNode = new Node(data);
if(index == 0) { // 새로 삽입하는 노드가 head임
newNode.next = this.head;
if(this.head != null) { // (추가) head가 null일 때 오류 나지 않게 함
this.head.prev = newNode; // (추가) 기존 해드의 전 노드(새로 추가된 head)를 새로운 노드로 설정
}
this.head = newNode;
} else if(index == this.count) { // (추가) 마지막 인덱스에 추가하는 경우
newNode.next = null; // (추가) 새로 추가된 노드 뒤는 null
newNode.prev = this.tail; // (추가) 새로 추가된 노드 앞이 기존 tail
this.tail.next = newNode;// (추가) 새로 추가된 노드를 tail로 변경
} else { // 새로 삽입하는 노드가 head 아님 + (추가) tail도 아님
// 원하는 인덱스까지 노드 타고 들어가 새로 삽입
let currentNode = this.head;
// 목표 인덱스의 바로 전까지 접근
for(let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
// 새로운 노드가 currentNode의 next를 가리킴
newNode.next = currentNode.next;
newNode.prev = currentNode;// (추가) 새로운 노드의 이전 노드를 currentNode
// currentNode가 새로운 노드를 가리킴
currentNode.next = newNode;// (추가)
newNode.next.prev = newNode;// (추가)
}
if(newNode.next == null) {
this.tail = newNode;
}
this.count++;
}
// 마지막 데이터 뒤에 삽입
insertLast(data){
this.insertAt(this.count, data);
}
// deleteAt 함수 원형
deleteAt(index) {
if(index >= this.count || index < 0) {
throw new Error("제거할 수 없습니다.");
}
// 노드 순회 변수
let currentNode = this.head;
if(index == 0){ // 첫 번째 노드(head 노드) 제거
let deleteNode = this.head;
if(this.head.next == null) { // (추가) 데이터가 하나 남은 경우
this.head = null;
this.tail = null;
} else {// (추가) 데이터가 2개 이상일 때
this.head = this.head.next;
this.head.prev = null;
}
this.count--;
return deleteNode;
} else if(index == this.count - 1) { // (추가) 가장 마지막 노드 제거
let deleteNode = this.tail;
this.tail.prev.next = null;
this.tail = this.tail.prev;
this.count--;
return deleteNode;
} else { // 첫 번째 노드(head 노드 + (추가)tail 노드)가 아닌 나머지 노드 제거
for(let i = 0; i < index - 1; i++){
currentNode = currentNode.next;
}
// 현재 currentNode는 제거할 노드의 이전 노드를 가리킴
let deleteNode = currentNode.next;
// 제거할 노드의 next 노드를 가리키게 함
currentNode.next = currentNode.next.next; // (추가) 삭제될 다음 노드와 연결고리 지어 줌
currentNode.next.prev = currentNode; // (추가)
this.count--;
return deleteNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if(index >= this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
// 리스트 순회 변수 만들어 헤드와 같은 노드 가리킴
let currentNode = this.head;
for(let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, DoublyLinkedList };[ Queue.mjs ]
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class Queue {
constructor() {
this.list = new DoublyLinkedList();
}
enqueue(data) {
this.list.insertAt(0, data);
}
dequeue() {
try {
return this.list.deleteLast();
} catch(e) {
return null;
}
}
front() {
return this.list.tail;
}
isEmpty() {
return (this.list.count == 0);
}
}
export { Queue };[ test_queue.mjs ]
import { Queue } from "./Queue.mjs";
let queue = new Queue();
console.log("===== enqueue() 세 번 호출 =====");
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.front());
console.log("===== dequeue() 네 번 호출 =====");
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(`isEmpty: ${queue.isEmpty()}`);