자료구조 큐와 스택 알아보기

1. 큐의 정의

First-In-First-Out) 원칙에 따라 데이터를 관리한다. 즉, 먼저 넣은 데이터가 먼저 빠져나가는 구조를 갖는다. 큐는 현실 세계에서 병렬로 줄을 서서 기다리는 상황을 모방한 구조로, 은행 창구에서의 대기줄, 콘서트 티켓 구매 줄 등 다양한 일상생활 사례와 밀접한 관련이 있다. 컴퓨터 과학에서는 운영체제의 작업 스케줄링, 네트워크 메시지 전달, 프린터 작업 목록 등에서 큐가 핵심적인 역할을 담당하며, 이러한 응용 사례는 현대 IT 산업에서 필수적이다. 통계에 따르면, 글로벌 클라우드 서비스에서는 초당 수십 만 건의 요청을 처리하는데 이때 큐 자료구조는 우선순위와 순서를 보장하는 역할로 쓰여지고 있다. 큐의 기본 연산은 Enqueue(삽입)와 Dequeue(삭제)로, Enqueue는 큐의 뒤쪽에 데이터를 넣으며, Dequeue는 앞쪽의 데이터를 제거하는 작업을 의미한다. 이 두 연산은 모두 일정한 시간 복잡도 O(1)을 갖기 때문에 빠른 처리속도를 기대할 수 있다. 큐는 배열이나 연결리스트로 쉽게 구현 가능하며, 각각의 특성에 따라 성능 차이가 발생한다. 배열을 이용한 큐는 인덱스를 이용하여 구현하나, 원형 큐(Circular Queue)를 사용하면 연속된…