[면접대비]Stack과 Queue

Q. Stack과 Queue는 어떤 자료 구조인지 설명해주세요.

 

Stack과 Queue의 자료구조

모두 데이터를 연속적으로 연결한 자료 구조인 선형 구조에 해당합니다.

스택(Stack)은 한 방향으로만 자료를 넣고 꺼낼 수 있는 후입선출(LIFO) 형식입니다. PUSH와 POP 연산으로 데이터를 넣고 꺼내며 인터럽트 처리, 깊이 우선 선택(DFS) 등에 응용됩니다.

큐(Queue)는 한쪽 끝에서는 삽입이, 반대쪽 끝에서는 삭제가 이뤄지는 선입선출(FIFO) 형식입니다. ENQUEUE와 DEQUEUE 연산으로 데이터를 넣고 꺼냅니다. 이때 데이터를 꺼내는쪽에서 가장 가까운 데이터를 Header(Front), 데이터를 넣는 쪽에서 가장 가까운 데이터를 Tail(Rear)라고 합니다. 너비 우선 탐색(BFS)에 응용됩니다.

 

스택(Stack)

 

한 방향으로만 자료를 넣고 꺼낼 수 있는 후입선출(LIFO, Last-In First-Out) 형식입니다.

PUSH와 POP 연산으로 데이터를 넣고 꺼냅니다. Top은 스택에서 가장 위에 있는 데이터로 스택 포인터라고도 불립니다.

이러한 스택은 인터럽트 처리, 함수 호출, 후위 표현 연산, 깊이 우선 선택(Depth-First Search, DFS) 등에 응용됩니다.

 

큐(Queue)

한쪽 끝에서는 삽입이, 반대쪽 끝에서는 삭제가 이뤄지는 선입선출(FIFO, First-In First-Out) 형식입니다.

ENQUEUE와 DEQUEUE 연산으로 데이터를 넣고 꺼냅니다.

이때 데이터를 꺼내는쪽에서 가장 가까운 데이터를 Header(Front), 데이터를 넣는 쪽에서 가장 가까운 데이터를 Tail(Rear)라고 합니다.

작업 대기열, 멀티스레드 환경, 너비 우선 탐색(Breadth-First Search, BFS)에 응용됩니다.

 

깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

깊이 우선 탐색은 깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾습니다. 그래프 탐색, 미로 찾기 등에 사용됩니다.

반면에 너비 우선 탐색은 큐에서 노드를 하나씩 꺼내고, 해당 노드의 이웃 노드들을 큐에 추가합니다. 이미 방문한 노드는 다시 방문하지 않도록 방문 여부를 확인하고, 방문한 노드는 추가하지 않습니다. 큐가 비어있을 때까지 위의 과정을 반복합니다. 주로 최단 경로를 찾거나 그래프의 구조를 탐색하는 데 사용됩니다.

두 알고리즘은 각각의 특성에 따라 다른 상황에서 사용되며, 문제에 따라 적절한 알고리즘을 선택하여 사용해야 합니다.