stack, queue

Stack

LIFO(Last-In-First-Out)의 개념을 가진 자료구조로서 가장 마지막의 들어간 데이터가 가장 처음 나오게 되는 자료구조이다. 데이터 추가 및 삭제는 오직 한방향으로만 가능하다.

Queue

FIFO(First-In-First-Out)의 개념을 가진 자료구조로서 가장 처음의 들어간 데이터가 처음으로 나오게 되는 자료구조이다. 큐의 가장 첫 원소를 front로, 가장 끝 원소를 rear로 정하며, front에서는 데이터의 삭제를, rear에서는 데이터의 추가를 담당한다. 또한, 데이터를 추가하는 것을 enqueue라 부르고, 데이터를 삭제하는 것을 dequeue라 부른다.

흔히들 Javascript에서 shift()를 사용하여 queue처럼 사용하려하지만, shift를 사용할 경우 데이터를 다시 정렬하기 위해 O(n)의 시간복잡도를 가져야 하기 때문에 원래 Queue의 특성에는 벗어나게 된다.