스택(추상 데이터 유형)

플레이트 스택과 마찬가지로 추가 또는 제거는 상단에서만 가능합니다.

푸시 및 팝 조작을 사용한 스택 런타임의 간단한 표현.

컴퓨터 과학에서 스택은 두 가지 주요 연산이 있는 요소의 집합 역할을 하는 추상 데이터 유형입니다.

• Push - 컬렉션에 요소를 추가합니다.
• Pop - 아직 제거되지 않은 가장 최근에 추가된 요소를 제거합니다.

요소가 스택에서 분리되는 순서에 따라 대체 이름인 LIFO(last in, first out)가 생성됩니다.또한 엿보기 작업을 통해 ^[1]스택을 수정하지 않고도 상단에 액세스할 수 있습니다.이러한 유형의 구조에 대해 "스택"이라는 이름은 겹쳐진 물리적 항목 집합과 유사하기 때문에 붙여진 이름입니다.이 구조를 사용하면 스택의 맨 위에서 항목을 쉽게 제거할 수 있지만 스택의 더 깊은 곳에 있는 항목으로 이동하려면 먼저 ^[2]다른 여러 항목을 제거해야 할 수도 있습니다.

선형 데이터 구조, 또는 추상적으로 순차 집합으로 간주되는 푸시 및 팝 작업은 구조의 한쪽 끝(스택의 맨 위)에서만 발생합니다.이 데이터 구조를 통해 스택을 단일 링크 목록 및 상위 요소에 대한 포인터로 구현할 수 있습니다.스택은 한정된 용량을 가지도록 구현될 수 있다.스택이 가득 차서 푸시되는 엔티티를 받아들이기에 충분한 공간이 없는 경우 스택은 오버플로우 상태로 간주됩니다.pop 조작은 스택의 맨 위에서 항목을 삭제합니다.

깊이 우선 검색을 구현하려면 스택이 필요합니다.

역사

스택스는 Alan M이 1946년에 컴퓨터 과학 문헌에 실렸다. 튜링은 서브루틴에서 ^[3][4]호출하고 돌아오는 수단으로 "베리와 언베리"라는 용어를 사용했다.서브루틴은 이미 1945년에 Konrad Zuse의 Z4에 구현되었다.

뮌헨 공과대학의 클라우스 사멜슨과 프리드리히 L. 바우어는 1955년에^[5][6] 스택의 아이디어를 제안했고 ^{[7][8][9][10]}1957년에 특허를 출원했다.1988년 3월 Samelson이 사망했을 때 Bauer는 스택 원리의 ^[11][6]발명으로 IEEE Computer Pioneer Award를 받았습니다.1954년 상반기^[12] 찰스 레오나드 햄블린과 1958년 ^[13][14]빌헬름 케머러[de]에 의해 유사한 개념이 독립적으로 개발되었다.

스택은 종종 ^[15][2][16]구내식당의 스프링식 플레이트 스택과 유사합니다.깨끗한 플레이트가 스택 위에 놓여져 있고, 이미 있는 플레이트를 아래로 밀어냅니다.플레이트를 스택에서 분리하면 그 아래에 있는 플레이트가 튀어나와 새로운 탑 플레이트가 됩니다.

비필수 조작

많은 구현에서 스택은 필수 "푸시" 및 "팝" 작업보다 더 많은 작업을 수행합니다.중요하지 않은 작업의 예로는 스택에서 삭제하지 않고 상위 요소를 관찰하는 "top of stack"^[17] 또는 "peeek"가 있습니다.이는 "팝"에 이어 "푸시"를 사용하여 동일한 데이터를 스택에 반환할 수 있으므로 필수 작업으로 간주되지 않습니다.스택이 비어 있는 경우 "stack top" 또는 "pop" 작업 실행 시 언더플로 상태가 발생합니다.또한 많은 구현에서는 스택이 비어 있는지, 크기가 반환되었는지 여부를 확인합니다.

소프트웨어 스택

실행

스택은 ^[18]리스트의 특수한 경우에 불과하기 때문에 어레이 또는 링크드 리스트를 통해 쉽게 구현할 수 있습니다.어느 경우든 데이터 구조를 스택으로 식별하는 것은 구현이 아니라 인터페이스입니다.사용자는 다른 도우미 조작을 거의 하지 않고 항목을 배열 또는 링크 목록에 팝업 또는 푸시할 수 있습니다.다음으로 의사코드를 사용한 양쪽의 실장을 나타냅니다.

어레이

다음과 같이 어레이를 사용하여 (바운딩된) 스택을 구현할 수 있습니다.첫 번째 요소는 보통 제로 오프셋에 있으며, 그 결과 다음과 같이 됩니다.array[0]스택에 푸시된 첫 번째 요소가 되고 마지막 요소가 튀어 나옵니다.프로그램은 지금까지 푸시된 항목의 수를 기록하는 변수 상단을 사용하여 스택의 크기(길이)를 추적해야 합니다.따라서 다음 요소가 삽입되는 배열 위치를 가리킵니다(제로 기반 인덱스 규칙을 가정).따라서 스택 자체는 3요소 구조로 효과적으로 구현될 수 있습니다.

구조 스택: maxsize : integer top : integer items : array of item

procedure initialize(stk : stack, size : integer): stk.tems ← 크기 항목의 새 배열(처음에는 빈 stk.maxsize ← size stk.top ← 0)

푸시 작업은 오버플로우를 확인한 후 요소를 추가하고 상위 인덱스를 증가시킵니다.

프로시저 푸시(stk : stack, x : item): stk.top = stk.maxsize: 보고서 오버플로 오류 기타: stk.disc[stk.top] ← x stk.top ← stk.top + 1

마찬가지로 pop은 언더플로우를 체크한 후 상위 인덱스를 줄이고 이전에 상위 인덱스를 반환했습니다.

procedure pop(stk : stack): stk.top = 0: underflow 오류를 보고합니다.그렇지 않으면 stk.top ← stk.top - 1 r ← stk.back[stk.top]을 반환합니다.

동적 어레이를 사용하면 필요에 따라 확장 또는 축소할 수 있는 스택을 구현할 수 있습니다.스택의 크기는 단순히 다이내믹 어레이의 크기입니다.다이나믹 어레이의 끝에 아이템을 추가하거나 삭제하려면 O(1)시간을 상각해야 하기 때문에 스택의 매우 효율적인 구현입니다.

링크 리스트

스택을 구현하기 위한 또 다른 옵션은 단일 링크 목록을 사용하는 것입니다.스택은 목록의 "머리"에 대한 포인터이며 목록 크기를 추적하기 위한 카운터가 있을 수 있습니다.

구조 프레임: data: item next: frame

구조체 스택: head: frame 또는 null 크기: 정수

프로시저 initialize(stk : stack): stk.head ← nil stk.size ← 0

항목 푸시 및 팝업은 목록의 선두에서 발생합니다.이 구현에서는 오버플로우가 발생하지 않습니다(메모리가 소진되지 않는 한).

프로시저 푸시(stk : stack, x : item): newhead ← newframe newhead.data ← x newhead.next ← stk.머리가 아프다.헤드 ← newhead stk.size ← stk.size + 1

프로시저 pop(stk : stack): stk의 경우.헤드 = 0: 언더플로 오류 r ← stk.head.data stk를 보고합니다.헤드 ← stk.head.next stk.size ← stk.size - 1 return r

스택 언어 및 프로그래밍 언어

Perl, LISP, JavaScript 및 Python과 같은 일부 언어에서는 스택 작업이 표준 목록/배열 유형에서 push 및 pop을 사용할 수 있도록 합니다.일부 언어(특히 PostScript 포함)는 프로그래머가 직접 보고 조작할 수 있는 언어 정의 스택을 중심으로 설계되어 있습니다.

다음으로 Common Lisp ( )에서의 스택 조작 예를 나타냅니다.>"는 Lisp 인터프리터의 프롬프트이며, ">"로 시작하지 않는 행은 표현에 대한 인터프리터의 응답입니다.

> (설정 스택 (목록. 'a' b. 'c'))  ;; 변수 "stack"을 설정합니다. (A B C) > (팝 스택)  ;; 맨 위(왼쪽 끝) 요소를 가져옵니다.스택을 변경해야 합니다. A > 스택        ;; 스택의 값을 확인합니다. (B C) > (밀다 '신규' 스택)  ;; 새 탑을 스택에 푸시합니다. (신규 B C) 

일부 C++ 표준 라이브러리 컨테이너 유형에는 LIFO 시멘틱스를 사용한 push_back 및 pop_back 조작이 있습니다.또한 스택템플릿 클래스는 기존 컨테이너를 조정하여 푸시/팝 조작만으로 제한된 API를 제공합니다.PHP에는 SplStack 클래스가 있습니다.Java 라이브러리에는Stack전문화된 클래스Vector다음은 해당 클래스를 사용하는 Java 언어의 예제 프로그램입니다.

수입품 java.displaces를 클릭합니다.스택;  학급 스택 데모 {     일반의 정적인 무효 주된(스트링[]args) {         스택< >스트링> 스택 = 신규 스택< >스트링>();         스택.밀다("A");    // 스택에 "A" 삽입         스택.밀다('B');    // 스택에 "B" 삽입         스택.밀다('C');    // 스택에 "C" 삽입         스택.밀다('D');    // 스택에 "D" 삽입         시스템..나가..인쇄(스택.훔쳐보다());    // 스택의 맨 위("D")를 인쇄합니다.         스택.팝();    // 상단("D") 제거         스택.팝();    // 다음 상단("C") 제거     } } 

하드웨어 스택

아키텍처 수준에서 일반적으로 사용되는 스택은 메모리 할당 및 액세스 수단입니다.

스택의 기본 아키텍처

일반적인 스택은 컴퓨터 메모리의 영역으로, 원점이 고정되어 있고 크기가 가변적입니다.처음에 스택의 크기는 0입니다.스택 포인터는 보통 하드웨어 레지스터의 형태로 스택에서 가장 최근에 참조된 위치를 가리킵니다.스택의 크기가 0일 경우 스택 포인터는 스택의 원점을 가리킵니다.

모든 스택에 적용할 수 있는 두 가지 작업은 다음과 같습니다.

• 푸시 조작: 스택 포인터가 가리키는 위치에 데이터 항목을 배치하고 스택 포인터의 주소를 데이터 항목의 크기에 따라 조정합니다.
• 팝 또는 풀 조작: 스택 포인터가 가리키는 현재 위치의 데이터 항목이 제거되고 스택 포인터가 데이터 항목의 크기에 따라 조정됩니다.

스택 동작의 기본원칙에는 많은 종류가 있습니다.모든 스택은 메모리 내에서 시작점이 고정된 위치를 가집니다.데이터 항목이 스택에 추가되면 스택 포인터가 스택의 현재 범위를 나타내도록 이동하며, 스택 포인터는 원점에서 멀리 확장됩니다.

스택 포인터는 스택의 원점을 가리킬 수도 있고 (스택이 커지는 방향에 따라) 원점 위 또는 아래 주소의 제한된 범위를 가리킬 수도 있습니다.다만, 스택 포인터는 스택의 원점을 통과할 수 없습니다.즉, 스택의 원점이 주소 1000이고 스택이 하향(주소 999, 998 등)인 경우 스택포인터를 1000 이상으로 증가시키지 마십시오(1001, 1002 등).스택상의 팝 조작에 의해 스택포인터가 스택의 원점을 지나 이동하면 스택 언더플로우가 발생합니다.푸시 조작에 의해 스택포인터가 스택의 최대 익스텐트를 초과하여 증가 또는 감소하면 스택오버플로가 발생합니다.

스택에 크게 의존하는 일부 환경에서는 다음과 같은 추가 작업이 제공될 수 있습니다.

• Duplicate(복제) : 상단 아이템을 팝업하여 다시 눌러서 (2회) 이전 상단 아이템의 추가 복사본이 상단 위에 있고 그 아래에 원본이 있습니다.
• Peek: 맨 위 항목은 검사(또는 반환)되지만 스택 포인터와 스택 크기는 변경되지 않습니다(즉, 항목이 스택에 남아 있음).이것은 많은 기사에서 톱 오퍼레이션이라고도 불립니다.
• 스왑 또는 교환: 스택에서 가장 상위2개의 아이템이 교환됩니다.
• 회전(또는 롤): 맨 위 항목 n개가 스택에서 회전 방식으로 이동합니다.예를 들어, n = 3이면 스택의 항목 1, 2, 3이 각각 스택의 위치 2, 3, 1로 이동됩니다.이 조작에는 다양한 종류가 있으며, 가장 일반적인 것은 왼쪽 회전 및 오른쪽 회전이라고 불립니다.

스택은 (실제 스택과 같이) 아래에서 위로 확장되는 경우가 많습니다.또한 왼쪽에서 오른쪽으로 확대되어 "가장 위"가 "가장 오른쪽"이 되거나 심지어 위에서 아래로 확대되도록 시각화할 수 있습니다.중요한 기능은 스택의 하단이 고정 위치에 있다는 것입니다.이 섹션의 그림은 위에서 아래로 확장 시각화의 예입니다.스택의 「상단」(9)은 아이템을 푸시 또는 팝하는 장소이기 때문에, 상단(28)은 스택 「하단」입니다.

우회전하면 첫 번째 요소가 세 번째 위치로, 두 번째 요소가 첫 번째 위치로, 세 번째 요소가 두 번째 위치로 이동합니다.이 프로세스의 두 가지 동등한 시각화를 다음에 나타냅니다.

사과 바나나 바나나 === 우회전 == > 오이 사과

오이 사과 바나나===좌회전==> 오이 사과 바나나

스택은 보통 메모리 셀 블록에 의해 표현되며, "하단"은 고정된 위치에 있고 스택 포인터는 스택 내의 현재 "상단" 셀의 주소를 보유하고 있습니다.상위 및 하위 용어는 스택이 실제로 낮은 메모리주소로 증가하는지 또는 더 높은 메모리주소로 증가하는지 여부에 관계없이 사용됩니다.

항목을 스택에 푸시하면 스택 포인터가 항목 크기(메모리 내에서 스택이 커지는 방향에 따라 감소 또는 증가)에 따라 조정되고 다음 셀을 가리키며 새로운 상위 항목이 스택 영역에 복사됩니다.정확한 구현에 따라서는 푸시 조작의 마지막에 스택포인터가 스택 내에서 사용되지 않는 다음 위치를 가리킬 수도 있고 스택의 맨 위 항목을 가리킬 수도 있습니다.스택이 현재 최상위 항목을 가리키고 있는 경우 스택 포인터는 새 항목이 스택에 푸시되기 전에 업데이트됩니다.새 항목이 스택에서 사용 가능한 다음 위치를 가리키고 있는 경우 새 항목이 스택에 푸시된 후에 업데이트됩니다.

스택을 터트리는 것은 단순히 밀어내는 것의 반대입니다.스택의 맨 위 항목이 삭제되고 푸시 조작에 사용되는 순서와 반대 순서로 스택포인터가 갱신됩니다.

메인 메모리에 스택

x86, Z80 및 6502를 포함한 많은 CISC 타입 CPU 설계에는 전용 레지스터가 있어 전용 레지스터를 암묵적으로 갱신하는 전용 콜, 리턴, 푸시 및 팝 명령을 사용하여 콜스택 포인터로 사용합니다.PDP-11이나 68000 등의 일부 CISC 프로세서에는 스택 구현을 위한 특별한 어드레싱 모드도 있습니다.일반적으로 세미 전용 스택포인터(68000의 A7 등)도 있습니다.이와는 대조적으로 대부분의 RISC CPU 설계에는 전용 스택명령어가 없기 때문에 전부는 아니더라도 대부분의 레지스터를 필요에 따라 스택포인터로 사용할 수 있습니다

레지스터 또는 전용 메모리에 스택

일부 머신에서는 산술 연산과 논리 연산에 스택을 사용합니다.연산자는 스택에 푸시되고 산술 연산과 논리 연산은 스택 상의 1개 또는 여러 항목에 작용하여 스택에서 삭제되고 결과가 스택에 푸시됩니다.이와 같이 기능하는 머신을 스택 머신이라고 합니다.

많은 메인프레임과 미니컴퓨터는 스택머신이었으며, 가장 유명한 것은 Burroughs 대형 시스템입니다.기타 예로는 CISC HP 3000 머신이나 Tandem Computers의 CISC 머신 등이 있습니다.

x87 부동소수점 아키텍처는 (현재 상단을 기준으로) 개별 레지스터에 직접 액세스할 수 있는 스택으로 구성된 레지스터 세트의 예입니다.

top-of-stack을 암묵적인 인수로 지정하면 버스 대역폭과 코드 캐시를 적절하게 사용하는 작은 머신코드 풋프린트가 가능하지만 프로세서에서 가능한 일부 유형의 최적화를 방지하여 모든 (2개 또는 3개) 오퍼랜드에 대해 레지스터 파일에 대한 랜덤액세스를 허용합니다.스택 구조는 (추측 실행을 위해) 레지스터 이름을 바꾼 슈퍼스케일러 구현을 좀 더 복잡하게 만들기도 하지만, 현대의 x87 구현에서 볼 수 있듯이 여전히 실현 가능합니다.

Sun SPARC, AMD Am29000 및 Intel i960은 모두 함수 인수 및 반환 값에 느린 메인 메모리를 사용하지 않기 위한 또 다른 전략으로 레지스터 스택 내의 레지스터 창을 사용하는 아키텍처의 예입니다.

또, 하드웨어에 직접 스택을 실장하는 소규모 마이크로프로세서도 다수 있습니다.또, 일부 마이크로 컨트롤러에는, 직접 액세스 할 수 없는 고정 깊이 스택이 있습니다.예를 들어 PIC 마이크로컨트롤러, Computer Cowboys MuP21, Harris RTX 라인, Novix NC4016 등이 있습니다.많은 스택 기반 마이크로프로세서가 마이크로코드 수준에서 프로그래밍 언어 Forth를 구현하기 위해 사용되었습니다.

스택의 응용 프로그램

표현식 평가 및 구문 분석

폴란드어 역 표기법을 사용하는 계산기는 스택 구조를 사용하여 값을 유지합니다.표현은 프리픽스, 포스트픽스 또는 인픽스 표기로 나타낼 수 있으며 스택을 사용하여 한 형식에서 다른 형식으로 변환할 수 있습니다.많은 컴파일러는 낮은 수준의 코드로 변환하기 전에 식, 프로그램 블록 등의 구문을 해석하기 위해 스택을 사용합니다.대부분의 프로그래밍 언어는 컨텍스트가 필요 없는 언어이므로 스택 기반 기계로 구문 분석할 수 있습니다.

역추적

스택의 또 다른 중요한 적용 분야는 백트랙입니다.미로에서 올바른 경로를 찾는 간단한 예를 생각해 보십시오.출발지부터 목적지까지 일련의 포인트가 있습니다.우리는 한 지점부터 시작한다.최종 수신처에 도달하려면 , 몇개의 패스가 있습니다.랜덤 경로를 선택한다고 가정합니다.어떤 길을 따라가다 보면 우리가 선택한 길이 잘못되었다는 것을 깨닫게 된다.그래서 우리는 그 경로의 시작으로 돌아갈 수 있는 방법을 찾아야 합니다.이는 스택을 사용하여 수행할 수 있습니다.스택의 도움으로 우리는 도달한 지점을 기억할 수 있습니다.이것은, 그 점을 스택에 밀어 넣는 것으로 행해집니다.잘못된 경로로 넘어갔을 경우 스택에서 마지막 지점을 팝업하여 마지막 지점으로 돌아가 올바른 경로를 찾기 위한 탐색을 계속할 수 있습니다.이를 역추적이라고 합니다.

역추적 알고리즘의 원형 예는 깊이 우선 검색으로, 지정된 시작 정점에서 도달할 수 있는 그래프의 모든 정점을 찾습니다.백트랙킹의 다른 응용 프로그램에는 최적화 문제에 대한 잠재적인 해결책을 나타내는 공간을 검색하는 작업이 포함됩니다.분기 및 바운드는 이러한 공간에서 가능한 모든 솔루션을 철저히 검색하지 않고 이러한 역추적 검색을 수행하는 기술입니다.

컴파일 시 메모리 관리

여러 수준의 프로시저 콜을 위한 로컬 데이터 및 콜 정보를 저장하는 일반적인 콜스택.이 스택은 원점에서 아래로 자란다.스택 포인터는 스택의 현재 맨 위 데이텀을 가리킵니다.푸시 조작은 포인터를 줄이고 데이터를 스택에 복사합니다.팝 조작은 스택에서 데이터를 복사한 후 포인터를 증가시킵니다.프로그램에서 호출되는 각 프로시저는 프로시저 리턴 정보(노란색)와 로컬 데이터(기타 색상)를 스택에 푸시하여 저장합니다.이런 유형의 스택 실장은 매우 일반적이지만 버퍼 오버플로 공격에 취약합니다(텍스트 참조).

많은 프로그래밍 언어는 스택 지향입니다.즉, 대부분의 기본 조작(2개의 숫자 추가, 문자 인쇄)을 스택에서 인수를 가져와 반환 값을 스택에 다시 배치하는 것으로 정의합니다.예를 들어 PostScript에는 리턴 스택과 오퍼랜드스택이 있으며 그래픽스테이트 스택과 딕셔너리 스택도 있습니다.p-code 머신과 Java Virtual Machine을 포함한 많은 가상 머신도 스택 지향입니다.

서브루틴이 파라미터를 수신하여 결과를 반환하는 방법인 거의 모든 콜규칙에서는 특수한 스택('콜스택')을 사용하여 프로시저/함수의 호출 및 네스트에 관한 정보를 보관 유지하고 콜이 종료되었을 때 호출된 함수의 컨텍스트로 전환하여 발신자 함수로 복원합니다.함수는 호출자와 착신자 사이의 런타임 프로토콜을 따라 인수를 저장하고 스택에 값을 반환합니다.스택은 중첩 또는 재귀 함수 호출을 지원하는 중요한 방법입니다.이 유형의 스택은 CALL 및 RETURN 문(또는 동등한 문)을 지원하기 위해 컴파일러에 의해 암묵적으로 사용되며 프로그래머에 의해 직접 조작되지는 않습니다.

일부 프로그래밍 언어에서는 스택을 사용하여 프로시저의 로컬 데이터를 저장합니다.로컬 데이터 항목의 공간은 절차 입력 시 스택에서 할당되며 절차 종료 시 할당 해제됩니다.C 프로그래밍 언어는 일반적으로 다음과 같이 구현됩니다.데이터 콜과 프로시저 콜 모두에 같은 스택을 사용하면 프로그램에 심각한 보안 버그가 발생하지 않도록 프로그래머가 알아야 하는 중요한 보안상의 영향이 있습니다(아래 참조).

효율적인 알고리즘

여러 알고리즘은 정보를 정리하는 주요 데이터 구조로서 스택(대부분의 프로그래밍 언어의 일반적인 함수 콜 스택과는 별개)을 사용합니다.여기에는 다음이 포함됩니다.

• 그래함 스캔은 2차원 점 시스템의 볼록 선체에 대한 알고리즘입니다.입력 부분 집합의 볼록한 선체를 스택 내에 유지하여 새로운 ^[19]점이 선체에 추가되었을 때 경계 내의 오목한 부분을 찾아 제거하는 데 사용한다.
• 단조 행렬의 행 최소값을 구하기 위한 SMAWK 알고리즘의 일부는 그래함 ^[20]스캔과 유사한 방식으로 스택을 사용합니다.
• 가장 가까운 모든 작은 값 배열의 각 숫자에 대해 그보다 작은 가장 가까운 이전 숫자를 찾는 문제입니다.이 문제의 알고리즘 중 하나는 스택을 사용하여 가장 작은 값의 후보 컬렉션을 유지합니다.배열 내의 각 위치에 대해 스택은 그 상단에 더 작은 값이 표시될 때까지 팝된 후 새 위치의 값이 ^[21]스택에 푸시됩니다.
• 근접 네이버 체인알고리즘.클러스터 스택의 유지보수에 기초한 집적 계층 클러스터링 방식입니다.각 클러스터는 스택상의 이전 네이버에 가장 근접합니다.이 메서드는 서로 가장 가까운 인접 라우터인 클러스터 쌍을 찾으면 팝되고 ^[22]병합됩니다.

보안.

일부 컴퓨팅 환경에서는 스택을 보안 침해 및 공격에 취약하게 만드는 방식으로 사용합니다.이러한 환경에서 작업하는 프로그래머는 이러한 구현의 위험을 피하기 위해 각별히 주의해야 합니다.

예를 들어, 일부 프로그래밍 언어에서는 공통 스택을 사용하여 착신 프로시저의 로컬 데이터와 프로시저를 발신자에게 반환할 수 있는 링크 정보를 모두 저장합니다.즉, 프로그램은 프로시저 콜의 중요한 리턴 주소를 포함한 같은 스택으로 데이터를 이동시킵니다.데이터가 스택 상의 잘못된 위치로 이동되거나 크기가 너무 큰 데이터 항목이 저장하기에 충분한 크기가 아닌 스택 위치로 이동되면 프로시저 호출에 대한 반환 정보가 손상되어 프로그램이 실패할 수 있습니다.

악의적인 당사자는 입력 길이를 확인하지 않는 프로그램에 초과 크기의 데이터 입력을 제공함으로써 이러한 유형의 구현을 이용하는 스택스매싱 공격을 시도할 수 있습니다.이러한 프로그램은 데이터 전체를 스택 상의 위치에 복사하여 호출한 절차의 반환 주소를 변경할 수 있습니다.공격자는 현재 프로시저의 반환 주소가 스택 자체(및 공격자가 제공한 데이터) 내의 영역을 가리키도록 리셋되도록 프로그램에 제공할 수 있는 특정 유형의 데이터를 실험할 수 있습니다.이 영역에는 부정 조작을 실행하는 명령이 포함됩니다.

이러한 유형의 공격은 버퍼 오버플로 공격의 변형으로 소프트웨어에서 보안 침해를 일으키는 매우 빈번한 원인이 됩니다.이는 가장 일반적인 컴파일러 중 일부가 데이터 콜과 프로시저 콜 모두에 공유 스택을 사용하고 데이터 항목의 길이를 확인하지 않기 때문입니다.프로그래머는 데이터 항목의 크기를 확인하기 위해 코드를 작성하지 않는 경우가 많습니다.또한 크기가 크거나 작은 데이터 항목이 스택에 복사되면 보안 위반이 발생할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

• 이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.

추가 정보

• 도널드 크누트.The Art of Computer Programming, Volume 1: Fundamental Algorithms, 제3판.애디슨 웨슬리, 1997년ISBN 0-201-89683-4.섹션 2.2.1: 스택, 큐, 디크, 페이지 238–243.

외부 링크

Wikimedia Commons에는 스택 데이터 구조와 관련된 미디어가 있습니다.

Wikibooks는 데이터 구조/스택 및 큐에 관한 책을 가지고 있습니다.

• 스택 머신 - 새로운 웨이브
• 경계 스택 깊이
• 인터럽트 구동 프로그램의 스택사이즈 분석(322KB)