스택과 큐는 데이터를 담는 배열 모양보다 “어떤 항목을 다음에 꺼내는가”를 표현하는 추상화입니다. 따라서 자료구조의 인출 순서, 작업의 실제 완료 순서, 외부 효과의 되돌림 가능성을 세 단계로 나누어야 undo·redo와 작업 처리의 차이를 놓치지 않습니다.
편집 변경과 접수 작업의 LIFO·FIFO 인출 순서
A·B·C 순서로 편집한 문서를 한 단계 되돌리려면 마지막 C의 변경부터 취소하는 것이 자연스럽습니다. 스택은 마지막에 넣은 것을 먼저 꺼내는 LIFO를 표현합니다. 반면 접수한 작업 A·B·C를 그 순서로 배정하려면 먼저 넣은 것을 먼저 꺼내는 FIFO 큐가 맞습니다.
이는 인출 규칙입니다. A를 워커 1에, B를 워커 2에 주면 B가 먼저 끝날 수 있습니다. FIFO 구조를 선택하는 것과 외부 상태를 순서대로 변경하는 것은 별도의 설계입니다.
상태를 추적할 때는 접수 시각, dequeue 시각, 시작 시각, 완료 시각을 별도로 기록합니다. A·B를 FIFO로 꺼내도 A가 느리면 B의 완료가 먼저일 수 있으며, 접수 순서가 반드시 외부 시스템의 commit 순서가 되려면 같은 owner에서 직렬화하거나 버전 조건을 추가해야 합니다.
undo 복구 정보
문자열에 A, B, C를 붙여 ABC를 만들었다고 합시다. 단순 동작 이름만 저장하지 않고 이전 상태·삽입 위치·삭제 내용 또는 정확한 역연산을 남겨야 복구할 수 있습니다.
| 동작 | 현재 문자열 | undo 스택 | redo 스택 |
|---|---|---|---|
| A,B,C 실행 | ABC | [A,B,C] | [] |
| undo | AB | [A,B] | [C] |
| undo | A | [A] | [C,B] |
| redo | AB | [A,B] | [C] |
| 새 X 실행 | ABX | [A,B,X] | [] |
마지막에 redo의 C를 지우는 것은 새 분기로 이동했기 때문입니다. 예전 C를 무조건 재실행하면 새 편집의 위치·내용에 맞지 않을 수 있습니다. 분기 이력을 보존하는 제품은 두 스택 대신 이력 트리 등 다른 모델이 필요합니다.
그림을 글로 읽기
- AB 상태
- 예전 ABC: redo 후보 C
- 새 ABX: 새 편집 X
- AB 상태 → 예전 ABC: 예전 분기
- AB 상태 → 새 ABX: 새 분기 선택
상태와 이력의 원자적 전환
execute(command):
nextState, undoData = prepareChange(currentState, command)
atomically_publish(currentState=nextState,
undo=undo+[undoData], redo=[])
undoOnce():
if undo.empty(): return no_change
previousState, redoData = prepareUndo(currentState, undo.last)
atomically_publish(currentState=previousState,
undo=undo.withoutLast, redo=redo+[redoData])
execute에서 currentState를 먼저 바꾸고 undo 항목을 나중에 저장하면, 두 번째 단계에서 실패할 때 화면은 새 상태인데 undo 스택은 예전 상태로 남을 수 있습니다. 반대로 스택부터 pop한 뒤 prepareUndo가 실패해도 같은 불일치가 생깁니다. 따라서 atomically_publish는 메모리 단일 소유자·잠금·DB 거래 등 실제 저장 경계 안에서 상태와 이력을 함께 바꾸고, 동시에 다른 편집이 들어오면 기준 버전도 확인해야 합니다.
메일 발송이나 결제처럼 이미 외부 효과가 난 작업은 문자열의 이전 상태로 되돌리는 역연산이 없습니다. 그런 경우 undo는 발송이나 결제를 없애는 것이 아니라 환불·정정이라는 새 보정 작업을 기록하는 의미가 되며, 스택 pop만으로 외부 효과가 사라지지 않습니다. 긴 이력은 snapshot·명령 병합·보관 범위를 함께 정해야 합니다.
배열 큐의 head·tail·count와 앞 삭제 비용
배열의 첫 칸을 지우고 나머지를 이동하면 dequeue가 O(n)입니다. 고정 크기 배열을 원처럼 쓰고 head·tail을 순환시키면 원소를 당기지 않습니다. 다음은 count를 따로 두어 빈 상태와 포화를 구분하는 단일 스레드 모형입니다.
push(value):
if count == capacity: return full
buffer[tail] = value
tail = (tail+1) mod capacity
count += 1
pop():
if count == 0: return empty
value = buffer[head]
clear_owned_reference(buffer[head])
head = (head+1) mod capacity
count -= 1
return value
capacity는 양수입니다. count 방식에서는 head=tail이 빈 상태와 가득 찬 상태 모두에서 가능하므로 count를 함께 봅니다. 슬롯 하나를 비워 두는 다른 방식은 유효 용량이 배열 길이보다 하나 작아집니다. 두 규칙을 섞지 않습니다.
용량 3에서 A,B,C를 넣으면 head=0,tail=0,count=3입니다. A를 꺼내면 head=1,count=2이고 D를 넣으면 buffer[0]=D,tail=1,count=3입니다. 논리 인출 순서는 여전히 B,C,D입니다. 물리 배열 순서 D,B,C와 다릅니다.
포화·취소·병렬 실행의 추가 계약
큐가 가득 찼다면 즉시 거절·생산자 대기·오래된 항목 폐기 중 무엇을 할지 정합니다. 서로 다른 의미의 작업을 몰래 버리면 안 됩니다. 대기 중 취소는 항목 제거·무효 표식으로 다룰 수 있지만 이미 실행 중인 작업을 멈추지는 못합니다.
여러 스레드가 접근하면 값 저장과 인덱스 공개의 순서도 보호해야 합니다. 단순 모듈러 연산만으로 lock-free 큐가 되는 것은 아닙니다. 접수 순서대로 효과를 적용해야 한다면 키별 직렬 실행이나 완료 재정렬·저장소 버전 조건이 필요합니다.
검사는 빈 pop·포화 push·여러 번 wrap·참조 제거·undo 실패·새 분기·병렬 완료 역전을 포함합니다. 원형 큐는 기준 목록과 인출 결과를, undo는 상태와 양쪽 스택을 함께 대조해야 합니다.
재현 연습은 용량 3 큐에 A·B·C를 넣고 A를 꺼낸 뒤 D를 넣는 경우와, ABC에서 두 번 undo한 뒤 X를 실행하는 경우를 함께 확인하는 것입니다. 예상 결과는 큐의 논리 순서 B·C·D, 물리 배열과 다른 head·tail 상태, X 실행 뒤 redo 비움입니다. 여기에 worker 완료를 의도적으로 역전시키면 FIFO 인출과 완료 순서가 다르다는 사실도 관찰할 수 있습니다.