당신의 Undo 버튼은 단지 팬케이크 스택일 뿐이다

Source: Dev.to

TL;DR: 나는 Undo 기능을 Stack 자료구조로 구현한다. Stack은 후입선출(LIFO) 원칙을 따르기 때문이다. 각 상태 변화는 스택에 푸시되고, Undo를 트리거하면 가장 최근의 동작을 팝하여 O(1) 시간에 전체 배열을 재인덱싱할 필요 없이 애플리케이션 상태를 되돌린다.

왜 Undo 기능은 항상 Stack인가?

나는 Stack을 사용한다. Stack은 오직 가장 최근 요소만 접근할 수 있는 엄격한 선형 히스토리를 강제하기 때문이다. 이는 모든 Undo 호출이 정확히 마지막에 수행된 동작을 되돌리게 하여 상태 손상을 방지하고 포인터 오버헤드를 최소화한다.

상태를 추적하는 앱을 만들 때, 거대한 배열을 스캔하거나 입력된 각 문자마다 인덱스를 이동시키는 것은 비효율적이다. Stack은 상태 스냅샷을 위에 놓고 바로 꺼낼 수 있게 해준다. Stack의 상단에서 푸시와 팝을 하는 것은 상수 시간 연산이며, 일련의 이벤트를 역추적하는 자연스러운 방식과 일치한다.

팬케이크 비유가 LIFO를 어떻게 설명하는가?

LIFO(Last‑In‑First‑Out)는 내가 접시 위에 마지막으로 올린 팬케이크가 가장 먼저 먹는다는 뜻이다. 소프트웨어에서는 히스토리 Stack에 마지막으로 푸시한 동작이 사용자가 undo를 눌렀을 때 가장 먼저 팝되는 것이다.

새 팬케이크를 더미의 바닥에 끼워 넣으려 하면 O(n) 연산이 필요하고 아침 식사가 망가진다—인덱스를 이동시키는 나쁜 아키텍처와 같다. 대신 새 동작을 위에 놓는다. Undo가 필요할 때는 위의 팬케이크를 가져가면 된다; 바닥에서 꺼내면 인덱스 이동 악몽과 상태 붕괴가 발생한다.

Stack vs. Array: 히스토리에서 효율성이 승리하는 이유

실제 상태 관리 루프에서 어떻게 구현할까?

// Simple undo stack implementation
const history = [];

const trackChange = (state) => {
  history.push(state);
};

const handleUndo = () => {
  if (history.length < 2) return; // Need at least one previous state
  history.pop(); // Remove current state
  const prevState = history[history.length - 1];
  applyToUI(prevState);
};

거대한 Stack의 메모리 사용량을 어떻게 관리할까?

Undo Stack이 무한히 커지는 것을 방지하기 위해 깊이에 하드 제한을 둔다(예: 100 개의 동작). 제한을 초과하면 가장 오래된 항목(바닥 요소)을 제거하거나 Stack을 원형 버퍼로 취급한다. 이 트레이드‑오프는 매우 오래된 히스토리를 버리지만, 애플리케이션이 메모리를 고갈하는 것을 방지한다.

FAQ

왜 Undo에 Queue를 사용하지 않나요?

Queue는 FIFO(First‑In‑First‑Out) 논리를 따른다. Undo에 Queue를 쓰면 앱이 처음 열렸을 때 수행된 첫 번째 동작을 되돌리게 되므로, 가장 최근의 실수를 되돌리지 못해 사용자 경험이 크게 저하된다.

Stack과 함께 ‘Redo’ 버튼은 어떻게 동작하나요?

나는 Redo를 위해 두 번째 Stack을 유지한다. Undo Stack에서 상태를 팝하면 그 상태를 Redo Stack에 푸시한다. 사용자가 새로운 변화를 만들면 Redo Stack은 비워진다. 이는 두 접시 사이에 팬케이크를 옮기는 것과 같다.

전체 상태 스냅샷 대신 diff를 저장할 수 있나요?

가능하다. 규모가 큰 애플리케이션에서는 전체 스냅샷 대신 diff(구체적인 명령이나 변경사항)만 저장하면 RAM 사용량을 크게 줄이면서도 O(1) Stack 연산을 유지할 수 있다. 이렇게 하면 “팬케이크”당 메모리 footprint가 작아진다.