[자료구조] Queue & Stack 1

Q. Queue는 무슨 자료구조 인가요?

queue는 선입선출 FIFO(First In First Out)의 자료구조입니다. 시간복잡도는 enqueue $O(1)$ , dequeue $O(1)$ 입니다. 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이있습니다.

✨ Circular Queue 자료구조와 예시들 기억

FIFO

queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다.

enqueue & dequeue

queue에서 데이터를 추가하는 것을 enqueue라고 합니다.
queue에서 데이터를 추출 하는 것은 dequeue라고 합니다.
enqueue의 경우 queue의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1) 입니다. 이와 비슷하게 dequeue의 경우 맨 앞의 데이터를 삭제하면 완료 되기 때문에 동일하게 O(1)의 시간복잡도를 갖습니다.

구현 방식

• Array-Based queue: enqueue와 dequeue 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현을 합니다.

• List-Based: 재할당이나 메모리 낭비의 걱정을 할 필요가 없어집니다.

• Array-Base 와 List-Base의 차이점 :
  두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖습니다. Array-Base의 경우 전반적으로 performance가 더 좋지만, worst case의 경우에는 훨씬 더 느릴 수 있습니다(resize). List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있습니다.

원형큐(circular queue)

확장 & 활용

queue의 개념에서 조금 확장한 자료구조들로는 양쪽에서 enqueue와 dequeue가 가능한 deque(double-ended queue)와 시간순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 priority queue가 있습니다.

활용 예시로는 하나의 자원을 공유하는 프린터나, CPU task scheduling, Cache구현, 너비우선탐색 (BFS) 등이있습니다.

---

---

Q. Stack은 어떤 자료구조 인가요?

stack은 후입선출 LIFO(Last In First Out)의 자료구조입니다. 시간복잡도는 push $O(1)$ , pop $O(1)$ 입니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

LIFO

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조입니다.

push & pop

stack에서 데이터를 추가하는 것을 push라고 하고 데이터를 추출 하는 것은 pop이라고 합니다. push의 경우 stack의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)입니다. 이와 동일하게 pop의 경우도 맨 뒤의 데이터를 삭제하면 완료 되기 때문에 O(1)의 시간복잡도를 갖습니다. push와 pop은 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 구현됩니다.

활용

stack은 재귀적인 특징이 있어서 프로그램을 개발할 때 자주 쓰이는 자료구조입니다. 활용 예시로는 call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

---

---

Q. Queue vs priority queue를 비교하여 설명해 주세요

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식입니다. 이와ㅈ 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

Queue의 operation 시간복잡도는 enqueue $O(1)$, dequeue $O(1)$이고,
Priority queue는 push $O(logn)$ , pop $O(logn)$ 입니다.