Queue & Stack

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

queue는 선입선출 FIFO(First In First Out)의 자료구조입니다.

시간 복잡도는 enqueue O(1), dequeue O(1) 입니다.

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

 

 

2. Array-Base 와 List-Base의 경우 어떤 차이가 있나요?

Array-Base의 경우 queue는 circular queue로 구현하는 것이 일반적입니다. 이는 메모리를 효율적으로 사용하기 위함입니다. 또한, enqueue가 계속 발생하면 fixed size를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 합니다. 그럼에도 enqueue의 시간복잡도는 (amortized)O(1)를 유지할 수 있습니다.

 

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

 

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

 

 

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

stack은 후입선출 LIFO(Last In First Out)의 자료구조입니다.

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

활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

 

 

4. Stack 두 개를 이용하여 Queue를 구현해 보세요.

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

편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다.

1. enqueue() :: instack에 push()를 하여 데이터를 저장합니다.
2. dequeue() ::
   1. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
   2. outstack.pop()을 하면 가장먼저 왔던 데이터가 가정 먼저 추출된다.(FIFO)

 

 

5. (Q4 꼬리질문) enqueue와 dequeue의 시간복잡도는 어떻게 되는지 설명해 주세요.

• enqueue() : instack.push()를 한번만 하면 되기 때문에 시간복잡도 O(1)입니다.
• dequeue() : 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 합니다. 따라서 총 2*n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다.
• 하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.

 

 

 

6. Queue 두 개를 이용하여 Stack을 구현해 보세요

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠습니다. 두 개의 queue로 stack을 구현하는 방법은 다음과 같습니다.

1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다.
2. pop() :: 
    1. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
    2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
    3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

 

 

7. (Q6 꼬리질문) 시간복잡도는 어떻게 되는지 설명해 주세요.

• push() : q1.enqueue()를 한번만 하면 되기 때문에 O(1)의 시간복잡도를 갖습니다.
• pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 O(n)이 됩니다.

 

 

8. ⭐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)입니다.