[CS study] 3. 스택과 큐

오늘은 스택과 큐 자료 구조를 복습한다.

스택

스택은 LIFO(후입선출) 구조의 자료를 말한다.

사용 예시로 이전에 재귀에서 살펴본 시스템 스택이나 DFS을 생각할 수 있다.

 

구현은 3가지 정도의 방법으로 해볼수 있다.

- 리스트를 이용해 전역변수로 구현하는 방법

- 구조체리스트를 통해서 마지막 인덱스와 리스트를 함께

- allocation(malloc, realloc...) 을 활용한 동적 스택 생성

 

스택문제의 대표 예시는 다음과 같다.

- 괄호 검사 알고리즘

- 전위, 중위, 후위 표기식

큐

큐는 FIFO(선입선출) 구조의 자료를 말한다.

사용 예시로 BFS, CPU 스케줄링을 생각할 수 있다

 

구현은 선형 큐 혹은 원형 큐의 형태로 만들게 된다.

선형

퀴즈

스택과 큐의 차이점을 설명하고, 각 자료구조가 실제 문제 해결에 어떻게 적용되는지 설명하세요. 또한, 스택과 큐를 동시에 사용하는 문제 해결 사례를 제시하고, 이 경우 두 자료구조를 함께 사용하는 이유를 설명하세요.

스택은 LIFO(Last In, First Out) 방식으로 작동하며, 큐는 FIFO(First In, First Out) 방식으로 작동합니다. 스택은 재귀적인 문제나 DFS(깊이 우선 탐색)에서 주로 사용되고, 큐는 BFS(너비 우선 탐색)나 작업 스케줄링에 적합합니다.
동시 사용 예시: 두 자료구조를 동시에 사용하는 경우로는 비동기 처리나 멀티태스킹 환경에서 작업 큐가 있습니다. 여기서 스택은 중단된 작업을 기록하고, 큐는 작업을 스케줄링합니다.

 

 

다음 후위표기법(postfix notation) 식을 스택을 사용하여 계산하는 과정을 설명하고, 각 단계에서 스택의 상태 변화를 설명하세요.

예: 15 25 + 10 2 * -

스택에 15와 25를 push
연산자를 만나면 15 + 25 = 40, 스택에 40을 push
스택에 10과 2를 push
연산자를 만나면 10 * 2 = 20, 스택에 20을 push
연산자를 만나면 40 - 20 = 20, 최종 결과는 20

 

 

우선순위 큐와 일반 큐의 차이점을 설명하고, 우선순위 큐가 더 적합한 상황을 예시로 설명하세요.

일반 큐는 FIFO 방식으로 작동하지만, 우선순위 큐는 각 요소에 우선순위가 부여되어 높은 우선순위를 가진 요소가 먼저 처리된다. 또한 큐의 경우 연결리스트, 구조체 등을 이용해 구현하게 되지만, 우선순위 큐의 경우 힙을 이용한다.

예시: 작업 스케줄링에서 중요도가 높은 작업을 먼저 처리해야 하는 경우 우선순위 큐가 적합하다.

 

 

스택과 큐를 동적 배열로 구현했을 때, pop 및 front 연산의 시간 복잡도를 설명하세요.

스택의 pop 연산은 배열의 끝에서 이루어지므로 O(1)
큐의 front 연산은 배열의 앞에서 이루어지며, 이를 위해 나머지 요소들을 이동해야 하기 때문에 O(n) 시간이 걸린다.