Queue & Stack

Queue

queue는 선립선출(FIFO) 자료구조

시간복잡도는 데이터 추가 enqueue O(1), 데이터 추출 dequeue O(1) 이다.

활용 예시로는 Cache구현, 프로세스 관리, 너비우선탐색(BFS)가 있다.

구현 방식

• Array-Based queue

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

• List-Based queue

  재할당이나 메모리 낭비의 걱정을 할 필요가 없다.

Stack

stack은 후입선출(LIFO) 자료구조

시간복잡도는 push O(1), pop O(1)이다.

활용예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록, DFS등이 있다.

Stack 2개로 Queue 구현

enqueue에 사용할 stack instack 과 dequeue에 사용할 outstack을 구현한다.

1. enqueue() : instack에 push()하여 데이터를 저장한다.

2. dequeue() :

   a. 만약 outstack이 비어 있다면 instack.pop()을 하고 outstack.push()를 하여 instack에서

   ​ outstack으로 데이터를 옮긴다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.

   b. outstack.pop()을 하면 가장 먼저 왔던 데이터가 가장 먼저 추출된다.(FIFO)

Queue 2개로 Stack 구현

push()에 사용할 queue를 q1, pop()에 사용할 queue를 q2라고 한다.

1. push() : q1으로 enqueue()히여 데이터를 저장한다.

2. pop():

   a. q1에 저장된 데이터의 갯수가 1이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터 를 q2에 enqueue()한다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이 터는 q2로 옮겨진다.

   b. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환

   c. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1, q2이름을 swap

Priority Queue(Heap)

• 우선 순위가 높은것이 먼저 나온다.

• push, pop 모두 O(logn)의 시간복잡도

• Heap -> Tree로 구현 -> Tree의 대부분 linked list로 구현 -> but, heap은 Array로 구현

  -> 새로운 인자가 언제나 마지막에 위치