스택(Stack)과 큐(Queue)
Last updated
Last updated
A. 스택은 간단하게 접시를 쌓아 올리는 것처럼 데이터를 쌓아서 가장 위에 있는 접시를 먼저 꺼내는 것 처럼 나중에 들어간 데이터가 먼저 나오는 구조입니다. 이러한 구조를 후입선출 LIFO 구조라고 합니다. 주요 연산으로는 데이터를 쌓는 push과 꺼내는 pop이 있습니다.
반면에 큐는 줄을 서서 차례대로 나가는 것처럼 같이 먼저 들어온 데이터가 먼저 나가게 되는 구조로, 먼저 들어온 데이터가 먼저 나가게 되는 구조입니다. 이러한 구조를 선입선출 FIFO 구조라고 합니다. 주요 연산으로는 데이터를 넣는 offer과 꺼내는 poll이 있습니다.
A. 사용자가 스택을 가장 쉽게 확인할 수 있는 예로는 실행 취소와 웹 브라우저의 뒤로 가기 기능이 있습니다. 두 기능 모두 가장 최근에 추가된 데이터를 다시 보여주는 방식으로, 이는 스택의 LIFO(Last In, First Out) 구조를 잘 나타냅니다. 스택은 주로 함수 호출 관리에 사용되는데, 예를 들어 재귀 함수 호출 시, 호출된 함수들이 스택에 차례로 쌓이고, 함수가 종료되면 마지막에 호출된 함수부터 반환됩니다. 또한 백트래킹 알고리즘에서 스택을 사용하면, 이전 상태로 쉽게 되돌아갈 수 있습니다. 한편, 큐는 작업을 순차적으로 처리하는 데 주로 사용됩니다. 예를 들어, 운영체제에서 프로세스나 작업들을 들어온 순서대로 처리할 때 큐가 활용됩니다. 너비 우선 탐색(BFS) 같은 알고리즘에서도 현재 노드의 이웃을 먼저 모두 처리하고 나서 다음 노드를 탐색할 때 큐가 필요합니다. 또한, 메시지 큐에서는 비동기적인 요청을 처리할 때, 먼저 들어온 요청을 먼저 처리하는 구조를 유지하는 데 큐를 사용합니다.
A. 스택은 ArrayList를 이용하여 구현할 수 있습니다. 데이터 추가와 제거 연산이 리스트의 끝에서 이루어지기 때문에, ArrayList는 인덱스를 통해 마지막 데이터에 빠르게 접근할 수 있어 스택에 적합합니다.
반면에, 큐는 LinkedList를 이용하여 구현할 수 있습니다. 큐는 앞에서 데이터를 제거하고, 뒤에서 데이터를 추가하는 구조이므로, 삽입과 삭제가 효율적인 LinkedList가 적합합니다.