[C/Python] 스택, 큐, 덱 1

[자료구조] 선형 자료구조의 삼총사: Stack, Queue, Deque 완벽 정리

데이터를 일렬로 나열하여 저장하는 '선형 자료구조'는 프로그래밍의 가장 기초이면서도 강력한 도구입니다. 각 자료구조의 특징과 실전 응용 사례를 정리합니다.

---

1. 스택 (Stack): 거꾸로 뒤집는 마법

• 원칙: LIFO (Last-In, First-Out / 후입선출)
• 특징: 한쪽 끝에서만 데이터의 삽입과 삭제가 일어납니다. 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.
• C언어 핵심: top 변수를 이용해 현재 데이터의 위치를 관리합니다.
• 실전 응용: 웹 브라우저 뒤로 가기, 수식의 괄호 검사, 재귀 함수 호출 등.

---

2. 큐 (Queue): 기다림의 미학

• 원칙: FIFO (First-In, First-Out / 선입선출)
• 특징: 한쪽(Rear)에서는 삽입이, 반대쪽(Front)에서는 삭제가 일어납니다.
• 원형 큐(Circular Queue): 배열의 끝과 처음을 연결하여 메모리 낭비를 줄이는 기법이 핵심입니다. (index + 1) % MAX_SIZE 연산이 필수!
• 실전 응용: 은행 번호표, 프린터 인쇄 대기열, 요세푸스 문제(2164, 1158번).

---

3. 덱 (Deque): 양방향의 만능 엔터테이너

• 명칭: Double-Ended Queue의 약자.
• 특징: 앞(Front)과 뒤(Rear) 양쪽 끝에서 삽입과 삭제가 모두 가능합니다. 스택과 큐의 장점을 합친 형태입니다.
• C언어 핵심: 양방향 이동을 위해 인덱스가 음수가 되지 않도록 (index - 1 + MAX_SIZE) % MAX_SIZE 처리를 하는 것이 포인트입니다.
• 실전 응용: 풍선 터뜨리기(2346번), 큐스택(24511번), 슬라이딩 윈도우 알고리즘.

---

💡 핵심 문제 해결 전략 (Troubleshooting)

학습 과정에서 우리가 해결했던 주요 기술적 이슈들입니다.

1. C언어 정적 배열 vs 동적 할당:
   • MAX_SIZE를 크게 잡을 때는 main 함수 밖(전역 변수)에 선언하여 스택 오버플로우를 방지했습니다.
   • malloc 사용 시에는 반드시 free를 통해 메모리 누수를 막았습니다.
2. 입출력 최적화:
   • 데이터가 10만 개 이상일 때는 printf 대신 **출력 버퍼링(fwrite)**을 사용하여 시간 초과를 해결했습니다.
3. 파이썬의 효율성:
   • collections.deque의 rotate() 메서드를 사용하여 원형 구조를 아주 쉽게 구현했습니다.

---

📝 정보처리기사 실기 대비 핵심 요약

• 선형 자료구조 종류: 리스트, 스택, 큐, 덱.
• 복잡도: 모든 삽입과 삭제 연산은 **O(1)**의 시간 복잡도를 가집니다. (가장 효율적)
• 데이터 필터링: queuestack 문제처럼 스택은 데이터 흐름에 영향을 주지 않고, 큐만 모으면 하나의 큰 큐가 된다는 논리를 이해하는 것이 중요합니다.