본문 바로가기

갬발자의 프로그래밍/알고리즘 & 자료구조5

[자료구조] Queue 구현하기 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 출처 - 위키백과 구현하기 class Queue { private size = 0; private currSize = 0; private queue: Array = []; private first = 0; private rear = 0; constructor(size: number) { this.size = size; } enqueue(value: T): Queue { if (this.currSize >= this.size) { throw new Error('queue is overflow'); } this.queue[this.rear.. 2021. 3. 31.
[자료구조] Linked List 직접 구현하기. Linked list - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. (위키백과) [구현하기] class MyNode { public next: null | undefined | MyNode; public value: T; constructor(value: T) { this.value = value; this.next = null; } } class LinkedList { private head: MyNode; private tail: MyNode; private length = 0; constructor(value: T) { this.head = new MyNode(value); this.tail = this.head; this.length = .. 2021. 3. 30.
[자료구조] Stack 직접 구현하기 stack은 후입선출(LIFO)의 자료 구조이다. 즉, 마지막에 넣은 데이터가 가장 먼저 꺼내진다. [구현하기] class Stack { private stack: Array = []; private max = 0; private len = 0; constructor(max: number) { this.max = max; } top(): T { return this.stack[this.len - 1]; } pop(): Stack { if (this.len === 0) throw new Error('stack is empty'); this.stack.splice(this.len - 1, 1); this.len--; return this; } push(value: T): Stack { if (this.len.. 2021. 3. 28.
큐 와 스택 스택은 FILO(First In Last Out)의 구조이다. 1, 2, 3, 4 라는 것을 순서대로 스택에 쌓이고 꺼낼 때는 4, 3, 2, 1의 순서로 꺼낼 수 있다. push 자료를 넣는다. pop 자료를 빼낸다. empty 스택이 비어있는지 확인한다. 이밖에도 몇가지 더 있지만 중요하다고 생각되는 부분이다. 큐는 FIFO (First In First Out)의 구조이다. 1, 2, 3, 4를 순서대로 스택에 집어넣고 꺼낼때도 1, 2, 3, 4순서대로 꺼내올 수 있다. push 자료를넣는다 pop 자료를 빼낸다. empty 큐가 비어있는지 확인한다. 큐를 자주 사용하는 알고리즘은 BFS 가 있다. 두개 모두 복잡도는 O(1) 이 된다. 2020. 2. 18.

티스토리툴바