목차
스택은 왜 Array인가?
C#에서 스택 구현이 Array를 사용하는이유는 효율성과 접근성 때문입니다.
1. 메모리 연속성
배열은 메모리 상에서 연속적인 공간에 데이터를 저장합니다. 이로 인해 CPU 캐시 효율이 높아지며, 데이터를 빠르게 읽고 쓸 수 있는 이점이 있습니다. 스택의 경우, 빈번하게 요소를 추가하거나 제거하는 작업이 이루어지기 때문에, 배열을 사용함으로써 이러한 연산들이 더욱 빨리 처리될 수 있습니다.
조금 더 자세히 설명하기 위해, CPU의 캐시 정책인 공간 지역성에 대해 간단히 설명해보겠습니다.
공간 지역성은 메모리 상에서 서로 근접해 있는 데이터가 연속적으로 접근될 가능성이 높다는 원리입니다. 예를 들어, 배열을 순차적으로 처리하거나 구조체의 필드를 읽는 경우가 있습니다. CPU 캐시는 이러한 패턴을 이용해 한 번의 메모리 접근으로 여러 근접 데이터를 불러와 캐시에 저장하고, 이후 접근에서 빠른 응답을 가능하게 합니다.
2. 접근 속도
배열을 사용하면 스택의 가장 중요한 연산인 추가와 제거를 매우 빠르게 수행할 수 있습니다.
배열에서는 인덱스를 통해 요소에 빠르게 접근할 수 있으며, 스택의 경우에는 배열의 끝 부분을 가리키는 인덱스만을 조작하여 데이터를 추가하거나 제거할 수 있습니다.
접근 속도 측면에서 배열의 주변 공간까지 캐싱되기 때문에, 추가나 제거를 할 때 그 메모리 주소까지 CPU가 캐싱 히트할 확률이 높습니다.
스택과 리스트의 추가 제거
스택과 리스트의 주요 차이점은 추가와 제거의 방식에 있습니다.
배열 기반 스택에서의 연산 복잡도
•
Push 연산 : 최상단에 요소를 추가합니다. 배열에서는 스택의 top을 나타내는 인덱스가 있으며, 이 인덱스에 해당하는 배열 위치에 요소를 추가하고 top 인덱스를 증가시킵니다. 이 과정은 O(1)의 시간 복잡도를 가집니다.
•
Pop 연산 : 이 연산은 스택의 최상단에서 요소를 제거합니다. 배열에서 top 인덱스를 감소시키기만 하면 되므로, 이 역시 O(1)의 시간 복잡도를 가집니다.
배열에서 요소 제거의 복잡도
일반적인 배열에서 임의의 위치에 있는 요소를 제거할 경우, 그 위치 이후의 모든 요소를 한 칸씩 앞으로 당겨야 하므로 O(N)의 시간이 소요됩니다.
그러나 스택에서는 항상 배열의 끝에서만 요소를 추가하거나 제거하기 때문에, O(1)으로 수행될 수 있습니다.
스택과 리스트의 값 복사
스택도 리스트와 마찬가지로 할당된 배열의 크기가 충분하지 않아 배열의 크기를 동적으로 확장해야 할 경우, 배열을 더 큰 배열로 복사하는 과정이 발생합니다.
var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
stack.Push(4);
stack.Push(5); // 이 push에서 배열의 크기를 확장
// 크기를 확장하는 방식은 List와 동일합니다. 기존 Capacity의 배수
C#
복사
