큐와 스택은 프로그래밍에서 중요한 역할을 하는 자료 구조입니다. 큐는 먼저 들어온 데이터가 먼저 나가는 ‘선입선출’ 방식으로 동작하며, 대기열 관리나 네트워크 통신에서 활용됩니다. 스택은 가장 최근에 추가된 데이터가 가장 먼저 제거되는 ‘후입선출’ 방식으로 작동하며, 함수 호출과 문자열 역순 만들기 등에 활용됩니다. 이러한 데이터 구조들은 프로그래밍에서 빈번하게 활용되어 효율적인 데이터 처리를 가능케 합니다.



  1. 큐
  2. 스택




큐

큐는 데이터가 들어오는 순서대로 처리되는 선입선출(First-In, First-Out) 방식을 가집니다. 대기열을 처리하는 동작과 비슷합니다. BFS 알고리즘, 캐시 구현, 멀티 스레딩 환경에서의 동기화 등에서 사용됩니다.


구현방식

큐는 배열 또는 연결 리스트를 활용해서 구현할 수 있습니다. 큐는 추상 데이터 타입으로 기본 연산인 ‘디큐’, ‘인큐’, ‘피크’ 기능을 구현하면 됩니다.

연결 리스트를 활용할 경우, 리스트의 처음을 참조하는 head와 마지막을 참조하는 tail을 이용하면 쉽게 구현할 수 있습니다. head로만 데이터를 ‘다큐’하고 tail로만 ‘인큐’하면 됩니다. ‘피크’의 경우 head를 조회하면 됩니다. 그래서 java.utils.LinkedList 클래스는 List인터페이스와 Deque 인터페이스(Queue 추상 클래스를 상속받고 있음)를 동시에 구현하고 있습니다.

배열을 활용할 경우, 데이터를 삭제하고 나서 배열의 값들을 이동시켜야 하기에 일반적인 큐를 구현할 때는 사용하지 않습니다. 하지만 원형 큐를 구현할 때, 배열을 사용합니다. rear 인덱스와 front 인덱스가 이동할 때마다 인덱스%size를 사용합니다. 이때, 더미 인덱스를 사용하면 더 쉽게 원형 큐 기능을 구현할 수 있습니다.

우선순위 큐

우선순위 큐는 높은 우선순위를 가지는 데이터가 먼저 처리되는 큐를 말합니다. 최단 경로 알고리즘(다익스트라)에 사용되거나 MST를 만들기 위한 방법 중 크루스칼 알고리즘에 사용됩니다. 우선순위 큐(PriorityQueue)는 힙 트리를 사용하여 구현합니다. 힙 트리는 완전 이진 트리 중 하나로 부모와 자식 노드 값에 대해 규칙을 가집니다.(비선형 자료구조에 대해 정리할 때, 자세하게 정리하고자 합니다.)




스택

스택은 데이터가 저장될 때, 가장 최근에 들어온 데이터가 먼저 처리되는 후입선출(Last-In, First-Out) 방식을 가집니다. 흔히 함수를 호출하고 반환할 때 확인할 수 있습니다.


구현방식

배열과 연결 리스트를 사용하여 구현할 수 있습니다. 큐와 마찬가지로 기본 연산인 ‘푸쉬’, ‘팝’, ‘피크’ 기능을 구현하면 됩니다.

배열로 구현할 경우, 한 부분(Top)으로만 데이터가 추가되거나 삭제되기 때문에 큐와 달리 배열의 이동을 할 필요가 없습니다. 하지만 크기가 고정되어 있어, 배열의 크기가 초과할 경우 배열의 크기를 재지정 해줘야 한다는 단점이 있습니다.

연결 리스트로 구현할 경우, 크기의 제한은 없지만, 구현에 있어서는 배열이 더 편리하고 더 빠릅니다.