[TIL] 스택과 큐

1. 스택

1) 정의

스택은 자료구조의 일종으로, 마지막에 삽입된 항목만을 제거하고 접근할 수 있다. 이러한 원리를 후입선출(LIFO)이라고 한다. 스택은 속도가 빠르다는 장점이 있다. 스택은 알고리즘이 마지막에 추가된 항목만을 접근해야 하는 후입선출 형태로 자료를 처리해야 하는 경우에만 배열에 대해 사용한다. 스택의 한계는 배열과 딜리 마지막에 추가된 항목 외에는 직접 접근할 수 없다는 것이다. 게다가 초반에 추가된 항모글 접근하기 위해서는 이후에 추가된 항목들을 자료구조로부터 제거해야 한다. 

 

자바스크립트에는 스택 클래스를 정의한 pop과 push라는 메소드가 있다

 

2) 들여다보기

스택의 마지막에 추가된 항목을 들여다보는 것(peeking)은 마지막에 추가된 항목을 스택 자료구조에서 제거하지 않고 반환하는 것을 의미한다. 들여다보기는 마지막에 추가된 항목을 다른 변수와 비교해 마지막에 추가된 항목을 자료구조에서 제거해야 할지 결정하기 위해 주로 사용된다.

 

3) 삽입

스택에 항목을 삽입하는 것은 자바스크립트 배열이 기본 지원하는 push 함수를 통해 수행된다.

 

4) 삭제

삭제 역시 자바스크립트가 기본 지원하는 배열 메소드인 pop를 통해 수행된다.

 

 

2. 큐

1) 정의

큐는 스택과 달리 첫 번째로 추가된 항목만을 제거할 수 있는 자료구조다. 이러한 원리를 선입선출(FIFO)라고 한다. 연산이 상수시간이라는 점이 큐의 장점이다. 큐는 스택과 비슷하게 한 번에 한 개의 항목만 접근할 수 있기 때문에 한계를 갖는다. 큐는 알고리즘이 첫 번째로 추가된 항목만을 접근해야 하는 선입선출 방식으로 자료를 처리해야 하는 경우에만 배열에 대해 사용한다.

 

자바스크립트에서 배열에는 큐 클래스를 정의한 shift와 push 라는 메소드가 있다.

 

2) 들여다보기

peek 함수는 큐에서 첫 번째 항목을 제거하지 않고도 첫 번째 항목을 반환한다. 스택 구현의 경우 배열의 마지막 항목이 반환됐지만, 큐의 경우 선입선출이기 때문에 배열의 첫 번째 항목이 반환된다. 

 

3) 삽입

큐에서 삽입을 인큐(enqueue)라 부른다. 배열이 스택 자료를 담는 데 사용되기 때문에 push 메소드를 사용해 enqueue를 구현할 수 있다.

 

4) 삭제

큐에서의 삭제를 디큐(dequeue)라 부른다. 배열이 스택 자료를 담는 데 사용되기 때문에 shift 메소드를 사용해 큐의 첫 번째 항목을 제거하고 반환할 수 있다.

 

5) 접근

배열과 달리 인덱스를 통해 큐의 항목들에 대해 접근할 수 없다. n번째 마지막으로 추가된 노드에 접근하려면 dequeue를 n번 호출해야 한다. 원래 큐에 변경이 생기지 않도록 버퍼가 필요하다. 큐에 어떤 항목이 존재하는지 확인하기 위해서는 큐를 검색해야 한다. 검색 역시 원래 큐에 변경이 생기지 않도록 버퍼 큐를 우선 생성해야 한다.