📝STACK이란??

스택은 LIFO(Last In First Out)의 자료구조로 먼저 넣은 데이터가 가장 나중에 나오는 특징을 가진다.

1. 시간복잡도는 push, pop 모두 O(1)이며 보통 브라우저의 뒤로가기 버튼에 자주 사용 된다. 그외 DFS, 수식 괄호 검사에 사용된다.

2. stack이 가득 찼을 때 push를 하면 stack overflow가 발생한다.

📝QUEUE란?

큐는 FIFO(First In First Out)의 자료구조로 먼저 넣은 데이터가 먼저 나오는 특징을 가진다.

1. 시간복잡도는 enqueue, dequeue 모두 O(1)이며 도중에 남는 메모리가 생기는것을 방지하기 위해 주로 circular queue를 사용한다. BFS, 프린터에 주로 사용된다.

2. 큐에는 Array Based와 List Based가 있는데 둘다 데이터를 넣고 뺄 때의 시간 복잡도는 같지만 다음과같은 특징을 가진다.

   A-B는circular queue를 사용하지만 메모리가 초과하는 입력이 자주 발생할 경우 전체를 새로운 Array에 옮기는 시간이 많아 오래걸릴 수 있다.

   L-B는 메모리 사용이 효율적이지만 메모리를 매번 할당해야하기 때문에 runtime 환경이 느릴 수 있다.

3. Priority Queue 는 enqueue, dequeue 모두 O(logn) 이며 heap의 자료구조와 일치한다. 부모가 항상 자식보다 높은 경우의 트리구조를 생각하면 된다.

📎Deque란?

Double ended queue의 약자로 입력을 시작한 쪽 마지막으로 입력한 쪽 양방향의 삽입 삭제가 가능하다.

💡결론

- STACK은 LIFO(후입선출)

- QUEUE는 FIFO(선입선출)