컴퓨팅 또는 "실제"수명에서 스택에 대해 이야기 할 때 우리는 일반적으로 기능의 "처음 사용 후 마지막"유형을 가정합니다.스택 데이터 저장 순서
스택의 아이디어는 실제 세계의 무언가를 기반으로하기 때문에 스택의 데이터가 저장되는 방식이 중요합니까?
많은 예제에서 스택 데이터의 저장은 배열을 사용하여 매우 자주 수행되며 스택에 추가 된 최신 항목은 배열의 맨 아래에 배치됩니다. (기존 플레이트 더미에 새로운 플레이트를 추가하는 것 (상단 플레이트가 아닌 다른 플레이트 아래에 배치하는 것 제외).
패러다임으로서 스택 작업이 예상대로 작동하는 한 데이터가 스택 내에 저장된 순서는 중요합니까?
기능이 이고 성능이 인 경우 데이터를 메모리에 저장하는 방법은 중요하지 않습니다.
종종 스택은 크기와 용량이있는 배열로 구현됩니다. 여기서 크기는 현재 스택에있는 요소의 수이고 용량은 상대적으로 비싼 메모리 재 할당 없이도 저장할 수있는 최대 수입니다.
용량은 일반적으로 삽입을 위해 상환 된 O (1) 성능을 제공해야 할 때 두 배가됩니다. 일반적으로 배열의 높은 인덱스 끝 부분에 빈 공간이있는 스택을 구현하는 것이 더 쉽습니다. 따라서 일반적으로이 작업이 수행됩니다.
특정 예제를 제공하기 위해 스택의 현재 상단을 인덱스로 맨 위 요소의 배열에 저장할 수 있습니다. 항목이 배열의 가장 높은 색인에 아래쪽으로 추가 된 경우 더 많은 요소를위한 공간을 만들기 위해 배열을 늘리면 배열의 맨 위 색인도 변경됩니다. 맨 아래에서 칠할 때 배열의 크기를 조정해야 할 때 맨 위 요소의 인덱스가 변경되지 않습니다.
스택을 다르게 구현하려면 구현의 기능과 성능이 문서화되었는지 확인해야합니다.
아니요. 그러나 푸시 된 항목을 다른 위치로 이동하는 데 계산 상 이점이 없으므로 선형 구조 (스택의 현재 "상단"에 빠르게 액세스 할 수 있음)가 무엇이든 작동합니다. 배열은 성능 및 소형화 측면에서 스택 구조의 요구를 충족하므로 대개 가장/명백한 선택입니다.
패러다임으로서, 아니, 실제로는 아닙니다. 저수준 구현 세부 사항으로, 아래쪽으로 커지는 스택은 이미 스택에있는 항목을 양수 오프셋을 사용하여 현재 스택 포인터에서 처리 할 수 있다는 약간의 이점이 있습니다 (예 : 일부 CPU 아키텍처에 유용 할 수 있음).