Algorithm - [Stack & Queue]

Stack & Queue

Stack, Queue, Deque Image from Velog

---

Stack

'접시 쌓기' (Last In First Out)

- push : 스택에 자료를 한개 집어 넣는 동작 <-> pop : 스택 안에 있는 자료를 한 개 꺼내는 동작

​- Stack이 비어있을 때 stack.pop -> stack underflow  |  Stack이 가득 찼을 때 stack.push -> stack overflow

 

시간 복잡도

가장 위에 있는 원소에 접근하기 때문에 접근, 삽입, 삭제의 시간복잡도는 O(1)

 

예

- 재귀 알고리즘

- 괄호검사, 후위 연산법, 문자열 역순

- DFS(Depth First Search)

 

Queue

'줄 서기' (First In First Out)

- enqueue : 큐에 자료를 한 개 집어 넣는 동작 <-> dequeue : 큐 안에 있는 자료를 한 개 꺼내는 동작

- 선형 큐, 원형 큐가 존재

 

시간 복잡도

First, Last의 위치로 데이터 접근 및 삽입 삭제가 가능하여 O(1)

 

예

- BFS(Binary First Search)

- 대기 순서 관리

 

Deque

'Double - ended queue' (LIFO + FIFO)

 

- 데이터 삽입 삭제가 빠르고 앞 뒤에서 접근, 삽입, 삭제가 가능

- 배열의 크기가 가변적일 때 사용

- 새로운 원소를 삽입할 때, 새로운 단위의 메모리 블록을 할당하여 삽입한다.

 

시간복잡도

접근, 삽입, 삭제의 시간복잡도는 O(1)이며 index를 활용해서 원소들에 접근이 가능하기 때문에 이 또한 O(1)