Queue vs Stack

Queue

Queue란 ?

Queue는 선입선출 FIFO(First In First Out)의 자료구조 이다. Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등에 활용된다.

enqueue와 dequeue

<—dequeue—

1

2

3

4

5

6

<—enqueue—

enqueue : queue에서 데이터를 추가하는 것. 맨 뒤에서 데이터를 추가하면 완료되기 때문에 O(1)의 시간복잡도.

dequeue : queue에서 데이터를 삭제하는 것. 맨 앞에서 데이터를 삭제하면 완료되기 때문에 O(1) 의 시간복잡도.

Array-based Queue

enqueue와 dequeue 과정에서 남는 메모리가 발생할 수 있다. 이 때 메모리의 낭비를 주리기 위해 주로 Circular queue 형식으로 구현한다.

Stack

Stack 이란?

Stack은 후입선출 LIFO(Last In First Out)의 자료구조 이다. 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선 탐색(DFS) 등에 활용된다.

push와 pop

push : stack에서 데이터를 추가하는 것. stack의 맨 뒤에서 데이터를 추가하면 완료되기 때문에 O(1)의 시간복잡도.

pop : stack에서 데이터를 추출하는 것. stack의 맨 뒤에서 데이터를 삭제하면 완료되기 때문에 O(1)의 시간복잡도.

-> push와 pop은 모두 stack의 top에서 원소를 추가하거나 삭제하는 형식으로 구현된다.