위키득계정 ↗
기술

스택과 큐의 선택

스택과 큐의 선택기술
스택
후입선출
큐
선입선출
덱
양쪽 끝의 추가와 제거
선택 기준
처리 순서와 필요한 연산
스택은 나중에 넣은 항목을 먼저 꺼내고 큐는 먼저 넣은 항목을 먼저 꺼내는 규칙을 제공한다. 저장 형태보다 처리 순서와 실제 구현의 연산 비용, 동시 접근 요구를 기준으로 선택해야 한다.

순서를 정하는 자료구조

A, B, C를 차례로 넣었을 때 스택에서는 C부터, 큐에서는 A부터 꺼내는 것이 기본 규칙이다. 이 차이는 탐색 순서나 작업 처리 방식에 영향을 준다. 같은 컨테이너라도 어느 쪽에서 추가하고 제거하는지에 따라 다른 동작을 구현할 수 있다. 이름만 붙이는 대신 연산의 위치와 순서를 명시한다.

탐색과 작업 처리

깊이 우선 탐색에서는 가장 최근에 남긴 후보를 먼저 처리하는 스택의 구조를 활용할 수 있다. 너비 우선 탐색에서는 먼저 발견한 후보를 먼저 처리하는 큐의 구조를 이용한다. 다만 실제 처리 시간이 서로 다르거나 작업이 병렬로 실행되면 꺼낸 순서와 완료 순서가 같지 않을 수 있다. 시작과 완료의 순서를 구분해야 한다.

배열의 맨 앞을 제거하기

배열 기반 자료에서 맨 앞 원소를 지울 때 뒤 원소를 이동하는 구현이라면 반복 제거 비용이 커질 수 있다. 큐가 필요할 때 사용하는 라이브러리의 앞쪽 제거 비용을 확인한다. 양 끝 연산에 적합한 덱 같은 선택지도 있다. 논리적인 선입선출 규칙과 그 규칙을 구현하는 실제 비용은 서로 다른 설명이다.

길이 제한과 넘침

처리할 수 있는 속도보다 항목이 더 빨리 들어오면 대기 자료가 계속 쌓일 수 있다. 길이를 제한했을 때 대기할지, 거절할지, 오래된 항목을 버릴지 정해야 한다. 어떤 자료구조는 용량 제한 시 자동으로 항목을 제거할 수 있으므로 그 동작이 요구에 맞는지 확인한다. 저장 공간을 제한하는 설정이 작업의 손실 정책과 연결된다.

동시 접근의 범위

여러 실행 흐름이 함께 접근한다면 개별 추가와 제거 연산의 안전성뿐 아니라 여러 연산을 묶은 판단도 검토한다. 비어 있지 않은지 확인한 뒤 꺼내는 사이에 다른 작업이 제거할 수 있다. 필요한 경우 동기화와 대기 기능을 갖춘 작업 큐를 사용한다. 컨테이너가 빠르다는 사실이 전체 작업 조정까지 보장하지는 않는다.

관련 문서

스택 / 너비 우선 탐색 / 깊이 우선 탐색 / 배열