⚡ 자료구조 - 스택, 큐, 덱, 우선순위 큐

🔹 스택(Stack)

• 후입선출 구조
• 삽입과 삭제가 한쪽 끝에서만 발생
• 대표 연산은 push, pop, peek
• 재귀 호출 처리, 괄호 검사, 백트래킹 등에 사용
• 배열이나 연결 리스트로 구현 가능
• 구현이 간단하고 직관적이나, 특정 요소 접근이 어렵고 순차 처리에 불리함

🔹 큐(Queue)

• 선입선출 구조
• 한쪽에서 삽입, 반대쪽에서 삭제
• 대표 연산은 enqueue, dequeue
• 프로세스 스케줄링, BFS 등에서 사용
• 배열이나 연결 리스트로 구현 가능
• 순차 처리에 유리하나, 특정 요소 접근이 불가능하고 삽입 삭제가 한정됨

🔹 덱(Deque)

• 양쪽에서 삽입과 삭제가 모두 가능한 큐
• front, rear 양쪽에서 enqueue와 dequeue 가능
• 캐시 알고리즘이나 슬라이딩 윈도우 문제에 사용됨
• 유연한 큐 구조지만 구현이 상대적으로 복잡하고 메모리 관리 필요
• 자바에서는 ArrayDeque, C++에서는 deque STL 사용

🔹 우선순위 큐(Priority Queue)

• 요소마다 우선순위를 부여하고, 가장 높은 우선순위 요소를 먼저 꺼냄
• 일반적으로 힙으로 구현
• 삽입은 O(log n), 삭제도 O(log n)
• 작업 스케줄링, 다익스트라 알고리즘 등에서 사용됨
• 일반 큐보다 복잡하지만 정렬된 요소 처리에 적합

🔹 차이점 요약

구조	삽입 방식	삭제 방식	사용 예시	특이 사항
스택	한쪽 끝에 삽입	같은 쪽에서 삭제	괄호 검사, 재귀, DFS	후입선출 구조
큐	한쪽 끝에 삽입	반대쪽 끝에서 삭제	BFS, 요청 처리	선입선출 구조
덱	양쪽에서 삽입 가능	양쪽에서 삭제 가능	캐시, 슬라이딩 윈도우	이중 단방향 큐 구조
우선순위 큐	우선순위에 따라 삽입	가장 높은 우선순위 삭제	다익스트라, 작업 우선순위 처리	내부적으로 힙으로 구성되는 경우 많음

🔹 체크 포인트

• 스택과 큐는 구조와 사용 방식이 반대지만, 둘 다 제한된 접근 구조를 가진 선형 자료구조
• 덱은 큐의 확장판으로 더 유연하지만 메모리나 속도 측면에서 신중히 써야 함
• 우선순위 큐는 일반 큐와 다르게 우선순위를 기준으로 처리되며 힙 자료구조와의 연관성을 알아야 함
• 일반적인 큐는 연결 리스트나 원형 배열로 구현할 경우 삽입과 삭제가 O(1)이지만, 배열로 단순 구현하면 dequeue 시 O(n)이 될 수 있음
• 우선순위 큐는 힙을 사용해 삽입과 삭제가 O(log n)이며, 최댓값 또는 최솟값 조회는 O(1)이다.