알고리즘 & 문제풀이/자료구조

스택 (stack) 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)이다. 맨 위쪽 아이템을 top이라 한다. 자료를 넣는것을 push, 넣어둔 자료를 꺼내는 것을 pop이라 한다. pop시 꺼내지는 자료는 가장 최근에 push한 자료부터 나오게 된다. 보통 스택은 위가 뚫린 비커 이미지를 상상하면 편하다. 스택이 꽉차면 Stack Overflow , 비어있는 상태를 Underflow라 한다.

큐 (Queue) FIFO(First In First Out) 을 기준으로 만들어진 자료구조다. ( 먼저 들어온 데이터가 먼저 나간다 ) 데이터의 삽입하는 부분은 rear 삭제하는 부분을 fornt 라 부른다. 큐의 종류는 선형 큐(Linear Queue), 원형 큐(Circular Queue) 등이 있다. 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다. 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로 많이 사용한다. 자바스크립트에서 push, shift로 구현이 가능하나 shift의 시간 복잡도는 최대 O(n)이니 주의하자. const arr = []; //enqueue arr.push('test1'); arr.push('test2..