CS

Queue & Stack

농담농담 2022. 11. 2. 00:34

🐷Queue의 자료구조 

  • FIFO(First In First Out)의 자료구조.
  • 시간복잡도는 enqueue(데이터 추가) O(1) , dequeue(데이터 추출) O(1)
  • 활용 예) Cache 구현, 프로세스 관리, 너비우선탐색(BFS) 등

Array-Based queue:

  • enqueue와 dequeue 과정에서 남는 메모리 발생 - Circular queue형식으로 구현(메모리 낭비 방지)
  • List-Based: 재할당이나 메모리 낭비 X

확장 & 활용

deque(double-ended queue) : 양쪽에서 enqueue와 dequeue가 가능하다.

priority queue : 시간순서가 아닌 우선순위가 높은 순서로 dequeue 할 수 있다.

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

🔥circular queue: Array-base로 일반적으로 구현하는 Queue이다. 메모리를 효율적으로 사용할 수 있다.fixed size보다 더  enqueue가 발생하면 dynamic array와 같은 방법으로 Size를 확장시켜야 한다. 이 경우에도 enqueue의 시간복잡도는 (amortized)O(1)을 유지한다.

 

List-Bases의 경우 보통 singly-lilnked list로 구현한다. enqueue는 단순히 singly-lilnked list에서 append를 하는 것으로 구현되고, 이 때 시간복잡도는 O(1)입니다. dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에 이 연산도 O(1)이다.

Array-Base가 전반적으로 performance가 더 좋다. 하지만, worst case(resize)의 경우에는 훨씬 더 느릴 수 있다.

List-Base의 경우, enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있다.

🐷Stack의 자료구조

  • LIFO(Last In First Out)의 자료구조.
  • 시간복잡도는 push(데이터 추가) O(1) , pop(데이터 추출) O(1)
  • 활용 예) call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등
  • 재귀적 특징

 

Stack 두 개로 Queue 구현

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있다.

enqueue - stack1에 push하여 데이터 추가

dequeue - stack1에서 stack2로 pop하고 stack2에 push 쌓인 데이터를 pop

stack의 경우 LIFO이므로 dequeue할 때, stack1에 마지막에 push된 데이터가 stack2에 가장 처음으로 push 된다. stack2에서 데이터를 추출할 때는 그 데이터가 가장 마지막에 pop되므로 결국 이 모든 과정을 보면 FIFO가 된다.

시간복잡도 worst의 경우 stack2가 비어있는 경우, stack1 에서 데이터를 전부 pop, stack2에 push 해야하므로 O(n)이 소요된다.

하지만 stack2가 비어있지 않은 경우 pop하면 O(1) 이므로 결론적으로 amorized O(1)의 시간 복잡도를 갖는다.