[자료구조] 스택, 큐, 정렬 알고리즘

✔️ 링크드리스트 기반으로 스택 구현해보기

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

class Stack {
	constructor() {
		this.head = null;
	}
	
	peek() {
		if (this.head === null) return null;
		return this.head.value;
	}
	
	push(value) {
		let newHead = new Node(value);
		newHead.next = this.head;
		this.head = newHead;
	}
	
	pop() {
		if (this.head === null) return null;

		let popValue = this.head;
		this.head = popValue.next;
		return popValue.value;
	}
}

 

✔️ 링크드리스트 기반으로 큐 구현해보기

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
	}
	
	dequeue() {
		if (this.head === null) return null;
		
		let deleteQueue = this.head;
		this.head = deleteQueue.next;
		return deleteQueue.value;
	}

	enqueue(value) {
		let newQueue = new Node(value);
		
		if (this.head === null) {
			this.head = newQueue;
			this.tail = newQueue;
		} else {
			this.tail.next = newQueue;
			this.tail = newQueue;
		}
	}
}

 

✔️ 버블 정렬 구현해보기

function bubbleSort(arr) {
	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < arr.length - i - 1; j++){
			if (arr[j] > arr[j + 1]){
				let temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}

 

✔️ 선택 정렬 구현해보기

function selectSort(arr) {
	for (let i = 0; i < arr.length; i++) {
		let minValue = i;
		for (let j = i + 1; j < arr.length; j++) {
			if (arr[minValue] > arr[j]) minValue = j;
		}
		
		let temp = arr[i];
		arr[i] = arr[minValue];
		arr[minValue] = temp;
	}
	return arr;
}

 

✔️ 삽입 정렬 구현해보기

function insertSort(arr) {
	for (let i = 1; i < arr.length; i++) {
		for (let j = i; j > 0; j--) {
			if (arr[j-1] > arr[j]){
				let temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			} else {
				break;
			}
		}
	}

	return arr;
}

 

240429에 진행된 내일배움캠프 알고리즘 세션 특강을 정리한 내용입니다.