되돌리기 기능과 먼저 들어온 작업 처리는 왜 각각 스택과 큐에 어울리나요?

스택은 마지막에 넣은 항목을 먼저 꺼내는 후입선출이고, 큐는 먼저 넣은 항목을 먼저 꺼내는 선입선출입니다. 되돌리기는 가장 최근 상태 변경을 먼저 취소해야 앞선 상태를 복원하기 쉬우므로 스택이 자연스럽고, 접수 순서대로 처리해야 하는 작업은 큐가 적합합니다. 다만 큐에서 꺼낸 순서와 여러 워커가 작업을 끝내고 결과를 반영하는 순서는 별개의 계약입니다.

인출과 완료의 순서를 분리합니다

동작 A, B, C를 차례로 실행한 뒤 한 번 되돌리면 C의 역동작부터 수행해야 합니다. 각 동작의 이전 상태나 역연산을 스택에 쌓고 pop하면 최근 변경부터 복구할 수 있습니다. 새 동작을 실행한 뒤 redo 스택을 비우는 이유도 과거와 다른 분기 이력이 생겼기 때문입니다. 반면 작업 A가 먼저 접수됐다면 큐의 앞에서 A를 꺼내고 뒤에 새 작업을 넣어 공정한 도착 순서를 표현합니다. 이를 각각 후입선출(LIFO)과 선입선출(FIFO)이라고 부릅니다.

배열로 스택을 만들면 끝에서 넣고 빼는 작업은 인덱스 조정으로 간단합니다. 배열 큐에서 매번 첫 원소를 삭제하고 나머지를 당기면 O(n)이므로 head·tail 인덱스를 둔 원형 버퍼를 사용하겠습니다. 연결 리스트는 앞뒤 작업이 쉽지만 노드 할당과 포인터 추적 비용이 생깁니다. 큐가 가득 찼을 때 무한히 메모리를 늘릴지, 생산자를 막을지, 오래된 작업을 버릴지까지 정해야 합니다.

자료구조 순서와 실행 순서를 분리합니다

큐에서 A를 먼저 인출해 워커 1에 배정하고, B를 워커 2에 배정하면 B가 먼저 끝날 수 있습니다. 결과를 완료 순서대로 반영해도 되는지, 계정별로 입력 순서를 보장해야 하는지에 따라 순서 번호·재정렬 버퍼·키별 직렬화가 필요합니다. 큐가 FIFO라는 사실만으로 외부 효과와 완료가 FIFO가 되지는 않습니다. 작업 취소를 지원하려면 큐 중간 삭제를 위한 핸들·무효화 표식·우선순위 구조가 추가됩니다.

검증은 빈 스택·빈 큐, 포화 큐, wrap-around, 여러 번 넣고 빼기, redo 분기, 병렬 워커의 완료 역전, 취소된 작업을 포함하겠습니다. 성능은 인출 순서뿐 아니라 대기 시간·메모리·정리 비용과 작업 결과의 순서 보장까지 확인해야 합니다.

스택에는 동작 이름만이 아니라 이전 상태나 정확한 역연산을 넣어야 외부 효과를 되돌릴 수 있습니다. A, B, C를 실행한 뒤 undo는 C부터 처리해야 하며, 새 동작을 실행하면 기존 redo 경로를 버립니다. 큐는 A를 먼저 넣었다면 먼저 꺼내는 FIFO를 표현하지만, A를 워커 1에 주고 B를 워커 2에 주면 B가 먼저 끝날 수 있어 인출 순서가 완료·반영 순서를 보장하지 않습니다.

원형 버퍼는 앞 원소를 매번 당기는 비용을 피하지만 head·tail의 빈 상태와 가득 찬 상태를 구분해야 합니다. 재시도 작업을 큐 뒤에 넣을지 원래 순서에 복귀시킬지 정책을 정하고, 이미 워커에 전달된 취소는 큐에서 제거하는 것만으로 막히지 않으므로 실행 상태와 취소 표식을 함께 관리하겠습니다.

원형 버퍼에서 head와 tail이 같을 때 비어 있는지 가득 찼는지 구분하려면 원소 수를 따로 저장하거나 슬롯 하나를 비워 두는 규칙을 쓸 수 있습니다. 여러 스레드가 접근하면 인덱스 갱신뿐 아니라 데이터가 준비된 뒤 소비자에게 공개되는 순서도 보호해야 합니다. 단순한 배열 인덱스 순환만으로 동시성 큐가 되지는 않습니다.