close
본문으로 이동

스택

위키백과, 우리 모두의 백과사전.
BERJAYA 다른 뜻에 대해서는 스택 (동음이의) 문서를 참고하십시오.
BERJAYA
접시 더미와 마찬가지로, 추가하거나 제거하는 것은 맨 위에서만 실용적이다.
BERJAYA
푸시 및 팝 연산을 사용한 스택 런타임의 간단한 표현.

컴퓨터 과학에서 스택(stack)은 다음 두 가지 주요 연산이 있는 추상 자료형으로, 요소들의 컬렉션 역할을 한다.

  • 푸시(Push): 컬렉션에 요소를 추가한다.
  • 팝(Pop): 가장 최근에 추가된 요소를 제거한다.

추가적으로, 피크 연산은 스택을 수정하지 않고 가장 최근에 추가된 요소(스택 맨 위에 있는 항목)의 값을 반환할 수 있다. 스택이라는 이름은 접시 더미처럼 물리적인 물건들이 서로 위에 쌓여 있는 것에 대한 유추이다.

스택에 추가되거나 제거되는 요소의 순서는 후입선출이라고 하며, 약어로 LIFO라고 한다.[1] 물리적인 물건 더미와 마찬가지로, 이 구조는 스택의 맨 위에서 항목을 쉽게 꺼낼 수 있게 하지만, 스택 깊숙이 있는 자료에 접근하려면 먼저 여러 다른 항목을 제거해야 할 수 있다.[2]

순차적인 컬렉션으로 간주되는 스택은 푸시 및 팝 연산이 발생할 수 있는 유일한 위치인 스택의 맨 위가 한쪽 끝에 있고, 다른 쪽 끝인 바닥은 고정되어 있다. 스택은 예를 들어 맨 위 요소를 가리키는 포인터가 있는 단일 연결 리스트로 구현될 수 있다.

스택은 제한된 용량을 갖도록 구현될 수 있다. 스택이 가득 차서 다른 요소를 수용할 공간이 충분하지 않으면 스택은 스택 오버플로 상태가 된다.

역사

[편집]

스택은 앨런 튜링이 서브루틴을 호출하고 반환하는 수단으로 "bury"와 "unbury"라는 용어를 사용하면서 1946년 컴퓨터 과학 문헌에 등장했다.[3][4] 서브루틴과 2단계 스택은 이미 1945년에 콘라트 추제의 Z4에 구현되어 있었다.[5][6]

뮌헨 공과대학교의 클라우스 자멜슨과 프리드리히 L. 바우어는 1955년에 Operationskeller("작동 지하실")라는 스택 개념을 제안했고[7][8] 1957년에 특허를 출원했다.[9][10][11][12] 1988년 3월, 자멜슨이 사망했을 때 바우어는 스택 원리 발명으로 IEEE 컴퓨터 개척자상을 수상했다.[13][8] 유사한 개념은 1954년 상반기에 찰스 레너드 햄블린에 의해 독립적으로 개발되었으며[14][8] 1958년에는 빌헬름 케머러에 의해 그의 automatisches Gedächtnis("자동 메모리")로 개발되었다.[15][16][8]

스택은 종종 카페테리아의 스프링식 접시 더미에 비유하여 설명된다.[17][2][18] 깨끗한 접시가 스택의 맨 위에 놓이면 이미 그곳에 있던 접시들을 아래로 밀어낸다. 스택에서 맨 위 접시가 제거되면 그 아래 접시가 위로 올라와 새로운 맨 위 접시가 된다.

필수적이지 않은 연산

[편집]

많은 구현에서 스택은 필수적인 "푸시" 및 "팝" 연산 외에 더 많은 연산을 가진다. 필수적이지 않은 연산의 한 예는 스택에서 제거하지 않고 맨 위 요소를 관찰하는 "스택 맨 위" 또는 "피크"이다.[19] 이는 동일한 데이터를 스택에 반환하기 위해 "팝" 다음에 "푸시"로 분해될 수 있으므로 필수적인 연산으로 간주되지 않는다. 스택이 비어 있으면 "스택 맨 위" 또는 "팝" 연산 중 하나를 실행할 때 언더플로 조건이 발생한다. 또한, 많은 구현에는 스택이 비어 있는지 확인하거나 크기를 반환하는 등 일반적인 작업을 처리하는 편의 연산이 포함된다.

소프트웨어 스택

[편집]

구현

[편집]

스택은 단순히 리스트의 특수한 경우이므로 배열이나 연결 리스트를 통해 쉽게 구현할 수 있다.[20] 어느 경우든 자료 구조를 스택으로 식별하는 것은 구현이 아니라 인터페이스이다. 사용자는 배열이나 연결 리스트에 항목을 팝하거나 푸시하는 것만 허용되며, 다른 도우미 연산은 거의 없다. 다음은 의사코드를 사용하여 두 가지 구현을 모두 보여준다.

배열

[편집]

배열은 다음과 같이 (유한한) 스택을 구현하는 데 사용될 수 있다. 첫 번째 요소는 일반적으로 0번 오프셋에 있으며 바닥이 된다. 따라서 array[0]은 스택에 처음 푸시되고 마지막으로 팝되는 요소이다. 프로그램은 스택의 크기(길이)를 추적해야 하며, 지금까지 푸시된 항목 수를 기록하는 top 변수를 사용하여 다음 요소를 삽입할 배열의 위치를 가리킨다(0 기반 인덱스 규칙을 가정). 따라서 스택 자체는 세 요소 구조로 효과적으로 구현될 수 있다.

structure stack:
    maxsize : integer
    top : integer
    items : array of item
procedure initialize(stk : stack, size : integer):
    stk.items ← new array of size items, initially empty
    stk.maxsize ← size
    stk.top ← 0

푸시 연산은 오버플로를 확인한 후 요소를 추가하고 top 인덱스를 증가시킨다.

procedure push(stk : stack, x : item):
    if stk.top = stk.maxsize:
        report overflow error
    else:
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

마찬가지로, 팝은 언더플로를 확인한 후 top 인덱스를 감소시키고 이전에 맨 위였던 항목을 반환한다.

procedure pop(stk : stack):
    if stk.top = 0:
        report underflow error
    else:
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        return r

동적 배열을 사용하면 필요에 따라 커지거나 줄어들 수 있는 스택을 구현할 수 있다. 스택의 크기는 동적 배열의 크기와 같으며, 동적 배열의 끝에서 항목을 추가하거나 제거하는 데 상각 O(1) 시간이 필요하므로 스택의 매우 효율적인 구현이다.

연결 리스트

[편집]

스택을 구현하는 또 다른 옵션은 단일 연결 리스트를 사용하는 것이다. 스택은 리스트의 "헤드"를 가리키는 포인터이며, 리스트의 크기를 추적하는 카운터가 있을 수 있다.

structure frame:
    data : item
    next : frame or nil
structure stack:
    head : frame or nil
    size : integer
procedure initialize(stk : stack):
    stk.head ← nil
    stk.size ← 0

항목을 푸시하고 팝하는 것은 리스트의 헤드에서 발생한다. 이 구현에서는 오버플로가 불가능하다(메모리가 소진되지 않는 한).

procedure push(stk : stack, x : item):
    newhead ← new frame
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← newhead
    stk.size ← stk.size + 1
procedure pop(stk : stack):
    if stk.head = nil:
        report underflow error
    r ← stk.head.data
    stk.head ← stk.head.next
    stk.size ← stk.size - 1
    return r

스택과 프로그래밍 언어

[편집]

펄, 리스프, 자바스크립트, 파이썬과 같은 일부 언어는 표준 리스트/배열 유형에서 푸시 및 팝 스택 연산을 제공한다. 포스 계열(포스트스크립트 포함)의 언어는 언어 정의 스택을 중심으로 설계되었으며, 이 스택은 프로그래머에게 직접 표시되고 조작된다.

다음은 커먼 리스프에서 스택을 조작하는 예시이다. (">"는 Lisp 인터프리터의 프롬프트이며, ">"로 시작하지 않는 줄은 표현식에 대한 인터프리터의 응답이다.)

> (setf stack (list 'a 'b 'c))  ;; "stack" 변수 설정
(A B C)
> (pop stack)  ;; 맨 위(가장 왼쪽) 요소 가져오기, 스택을 수정해야 함
A
> stack        ;; 스택 값 확인
(B C)
> (push 'new stack)  ;; 스택에 새 맨 위 요소 푸시
(NEW B C)

C++ 표준 라이브러리 컨테이너 유형 중 일부는 LIFO 의미론을 가진 push_back() 및 pop_back() 연산을 가진다. 또한 std::stack 템플릿 클래스는 기존 컨테이너를 조정하여 푸시/팝 연산만 포함하는 제한된 API를 제공한다. PHP에는 SplStack 클래스가 있다. 자바 라이브러리에는 Vector의 특수화인 Stack 클래스가 포함되어 있다. 다음은 해당 클래스를 사용하는 자바 언어의 예제 프로그램이다.

package org.wikipedia.examples;

import java.util.Stack;

public class Example {
    public static void main(String[] args) {
        Stack<Character> stack = new Stack<>();
        stack.push('a'); // 스택에 'a' 삽입
        stack.push('b'); // 스택에 'b' 삽입
        stack.push('c'); // 스택에 'c' 삽입
        stack.push('d'); // 스택에 'd' 삽입
        System.out.println(stack.peek()); // 스택의 맨 위 ('d')를 출력
        stack.pop(); // 맨 위 ('d') 제거
        stack.pop(); // 다음 맨 위 ('c') 제거
    }
}

PDP-11, VAX, 모토로라 68000 시리즈와 같은 일부 프로세서는 스택 조작에 유용한 주소 지정 모드를 가진다. 다음 PDP-11 어셈블리어 소스 코드는 스택에 두 개의 숫자를 푸시하고 더한 다음 결과를 스택에 남긴다.

; R0은 스택 영역을 가리키는 것으로 가정
; -(R0)는 스택에 항목을 할당하여 스택 포인터를 미리 감소시킴
; (R0)+는 스택에서 항목을 제거하여 스택 포인터를 사후 증가시킴
;
       MOV    #12,-(R0)         ; 스택에 12 푸시
	   MOV    #34,-(R0)         ; 스택에 34 푸시
	   ADD 	  (R0)+,(R0)        ; 스택에서 34 팝하여 12에 더함
                                ; 결과를 스택에 남김

하드웨어 스택

[편집]

아키텍처 수준에서 스택의 일반적인 사용은 메모리를 할당하고 접근하는 수단으로 사용된다.

스택의 기본 아키텍처

[편집]

일반적인 스택은 고정된 원점과 가변적인 크기를 가진 컴퓨터 메모리 영역이다. 처음에는 스택의 크기가 0이다. 스택 포인터(일반적으로 프로세서 레지스터 형태)는 스택에서 가장 최근에 참조된 위치를 가리킨다. 스택의 크기가 0일 때 스택 포인터는 스택의 원점을 가리킨다.

모든 스택에 적용되는 두 가지 연산은 다음과 같다.

  • 푸시 연산: 스택 포인터의 주소는 데이터 항목의 크기만큼 조정되고, 데이터 항목은 스택 포인터가 가리키는 위치에 기록된다.
  • 팝 또는 풀 연산: 스택 포인터가 가리키는 현재 위치의 데이터 항목이 읽히고, 스택 포인터는 해당 데이터 항목의 크기에 해당하는 거리만큼 이동한다.

스택 연산의 기본 원리에는 많은 변형이 있다. 모든 스택은 메모리에서 시작하는 고정된 위치를 가진다. 데이터 항목이 스택에 추가됨에 따라 스택 포인터는 스택의 현재 범위를 나타내도록 이동하며, 이는 원점에서 멀어진다.

스택 포인터는 스택의 원점을 가리킬 수도 있고, 원점 위 또는 아래의 제한된 주소 범위를 가리킬 수도 있다(스택이 성장하는 방향에 따라 다름). 그러나 스택 포인터는 스택의 원점을 넘어설 수 없다. 다시 말해, 스택의 원점이 주소 1000에 있고 스택이 아래쪽으로(999, 998 등의 주소로) 성장한다면, 스택 포인터는 1000을 넘어(1001 이상으로) 증가해서는 안 된다. 스택에서 팝 연산이 스택 포인터를 스택의 원점을 넘어서 이동하게 하면 스택 언더플로가 발생한다. 푸시 연산이 스택 포인터를 스택의 최대 범위를 넘어 증가시키거나 감소시키면 스택 오버플로가 발생한다.

스택에 크게 의존하는 일부 환경에서는 추가적인 연산을 제공할 수 있다. 예를 들어:

  • 복제 (Duplicate): 맨 위 항목이 팝된 다음 두 번 푸시되어, 이전 맨 위 항목의 두 복사본이 이제 맨 위에 놓인다.
  • 피크 (Peek): 맨 위 항목을 검사(또는 반환)하지만, 스택 포인터와 스택 크기는 변경되지 않는다(항목이 스택에 남아 있음을 의미). 이것은 top 연산이라고도 불릴 수 있다.
  • 교환 (Swap or exchange): 스택의 맨 위 두 항목이 서로 위치를 바꾼다.
  • 회전 (Rotate or Roll): 스택의 맨 위 n개 항목이 회전하는 방식으로 스택에서 이동한다. 예를 들어, n = 3이면 스택의 항목 1, 2, 3이 각각 스택의 위치 2, 3, 1로 이동한다. 이 연산에는 많은 변형이 가능하며, 가장 일반적인 것은 왼쪽 회전과 오른쪽 회전이다.

스택은 종종 아래에서 위로(실제 세계의 스택처럼) 성장하는 것으로 시각화된다. 또한 왼쪽에서 오른쪽으로 성장하는 것으로 시각화될 수도 있는데, 이 경우 맨 위는 가장 오른쪽에 있거나, 심지어 위에서 아래로 성장하는 것으로 시각화될 수도 있다. 중요한 특징은 스택의 바닥이 고정된 위치에 있다는 것이다. 이 섹션의 그림은 위에서 아래로 성장하는 시각화의 예이다. 맨 위(28)는 스택 "바닥"인데, 스택 "맨 위"(9)는 항목이 푸시되거나 팝되는 곳이기 때문이다.

오른쪽 회전은 첫 번째 요소를 세 번째 위치로, 두 번째 요소를 첫 번째 위치로, 세 번째 요소를 두 번째 위치로 이동시킨다. 이 과정을 시각화한 두 가지 동등한 예시는 다음과 같다.

apple                         banana
banana    ===right rotate==>  cucumber
cucumber                      apple
cucumber                      apple
banana    ===left rotate==>   cucumber
apple                         banana

스택은 일반적으로 컴퓨터에서 메모리 셀 블록으로 표현되며, "바닥"은 고정된 위치에 있고 스택 포인터는 스택의 현재 "맨 위" 셀 주소를 가지고 있다. "맨 위"와 "바닥"이라는 명칭은 스택이 실제로 더 높은 메모리 주소 방향으로 성장하는지 여부와 관계없이 사용된다.

스택에 항목을 푸시하는 것은 스택 포인터를 항목 크기만큼 조정(스택이 메모리에서 성장하는 방향에 따라 감소 또는 증가)하여 다음 셀을 가리키게 하고, 새로운 맨 위 항목을 스택 영역으로 복사한다. 다시 정확한 구현에 따라, 푸시 연산이 끝날 때 스택 포인터는 스택에서 다음 사용 가능한 위치를 가리킬 수도 있고, 스택의 맨 위 항목을 가리킬 수도 있다. 스택이 현재 맨 위 항목을 가리키는 경우, 새 항목이 스택에 푸시되기 전에 스택 포인터가 업데이트된다. 스택의 다음 사용 가능한 위치를 가리키는 경우, 새 항목이 스택에 푸시된 후에 업데이트된다.

스택을 팝하는 것은 푸시하는 것의 역방향이다. 스택의 맨 위 항목이 제거되고 스택 포인터는 푸시 연산에서 사용된 것과 반대 순서로 업데이트된다.

주 기억장치의 스택

[편집]

x86, Z80, 6502를 포함한 많은 CISC 유형 CPU 설계는 콜 스택 스택 포인터로 사용하기 위한 전용 레지스터와 전용 레지스터를 암시적으로 업데이트하는 전용 호출, 반환, 푸시 및 팝 명령어를 가지고 있어 코드 밀도를 높인다. PDP-11 및 68000과 같은 일부 CISC 프로세서는 스택 구현을 위한 특수 주소 지정 모드도 가지고 있으며, 일반적으로 반전용 스택 포인터도 있다(예: 68000의 A7). 이와 대조적으로 대부분의 RISC CPU 설계는 전용 스택 명령어를 가지고 있지 않으므로 필요에 따라 거의 모든 레지스터를 스택 포인터로 사용할 수 있다.

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

[편집]
BERJAYA
1988년의 프로그래밍 가능 포켓 계산기 HP-42S는 당시 회사의 거의 모든 계산기와 마찬가지로 4단계 스택을 가지고 있었으며, X와 Y 두 줄 디스플레이 덕분에 스택 레지스터 X, Y, Z, T의 네 값 중 두 값을 동시에 표시할 수 있었다. HP-48과 같은 후속 모델에서는 레벨 수가 메모리 크기에 의해서만 제한되도록 증가되었다.

일부 기계는 스택을 산술 및 논리 연산에 사용한다. 피연산자는 스택에 푸시되고, 산술 및 논리 연산은 스택의 맨 위 하나 이상의 항목에 작용하여 스택에서 팝하고 결과를 스택에 푸시한다. 이런 방식으로 작동하는 기계를 스택 머신이라고 한다.

많은 메인프레임 및 미니컴퓨터가 스택 머신이었으며, 가장 유명한 것은 버로우즈 대형 시스템이었다. 다른 예로는 CISC HP 3000 기계와 탠덤 컴퓨터의 CISC 기계가 있다.

x87 부동소수점 아키텍처는 스택으로 구성된 레지스터 세트의 예시로, 개별 레지스터에 직접 접근(현재 맨 위에 상대적으로)하는 것도 가능하다.

스택의 맨 위를 암묵적 인수로 사용하면 버스 대역폭 및 코드 캐시를 잘 활용하는 작은 기계어 풋프린트를 가질 수 있지만, 이는 모든 (두세 개의) 피연산자에 대해 레지스터 파일에 임의 접근을 허용하는 프로세서에서 가능한 일부 유형의 최적화를 방지한다. 스택 구조는 레지스터 이름 변경(투기적 실행을 위해)을 통한 슈퍼스칼라 구현을 다소 복잡하게 만들기도 하지만, 현대 x87 구현에서 입증된 바와 같이 여전히 실현 가능하다.

선 SPARC, AMD Am29000, 인텔 i960은 모두 레지스터 윈도를 레지스터 스택 내에서 사용하여 함수 인수 및 반환 값에 느린 주 기억장치 사용을 피하는 또 다른 전략을 사용하는 아키텍처의 예이다.

또한 스택을 하드웨어에 직접 구현하는 작은 마이크로프로세서들이 많이 있으며, 일부 마이크로컨트롤러는 직접 접근할 수 없는 고정 깊이 스택을 가지고 있다. 예를 들어 PIC 마이크로컨트롤러, 컴퓨터 카우보이즈 뮤P21, 해리스 RTX 라인, 노빅스 NC4016 등이 있다. 적어도 하나의 마이크로컨트롤러 계열인 COP400은 장치에 따라 스택을 하드웨어에 직접 구현하거나 스택 포인터를 통해 RAM에 구현한다. 많은 스택 기반 마이크로프로세서는 마이크로코드 수준에서 포스 프로그래밍 언어를 구현하는 데 사용되었다.

스택의 응용

[편집]

표현식 평가 및 구문 분석

[편집]

역폴란드 표기법을 사용하는 계산기는 스택 구조를 사용하여 값을 저장한다. 표현식은 전위, 후위 또는 중위 표기법으로 나타낼 수 있으며, 한 형식에서 다른 형식으로의 변환은 스택을 사용하여 수행할 수 있다. 많은 컴파일러는 저수준 코드로 변환하기 전에 구문을 분석하기 위해 스택을 사용한다. 대부분의 프로그래밍 언어는 문맥 자유 언어이므로 스택 기반 기계로 구문 분석할 수 있다.

백트래킹

[편집]

스택의 또 다른 중요한 응용 분야는 퇴각검색이다. 이에 대한 예시는 일련의 지점, 시작 지점, 여러 경로 및 목적지를 포함하는 미로에서 올바른 경로를 찾는 간단한 예시이다. 무작위 경로를 선택해야 하는 경우, 잘못된 경로를 따른 후에는 해당 경로의 시작으로 돌아갈 수 있는 방법이 있어야 한다. 이는 스택을 사용하여 달성할 수 있는데, 마지막 올바른 지점을 스택에 푸시하고, 잘못된 경로의 경우 스택에서 팝할 수 있다.

퇴각검색 알고리즘의 전형적인 예는 깊이 우선 탐색으로, 지정된 시작 정점에서 도달할 수 있는 그래프의 모든 정점을 찾는다. 퇴각검색의 다른 응용 분야에는 최적화 문제의 잠재적 솔루션을 나타내는 공간을 탐색하는 것이 포함된다. 분기 한정법은 이러한 공간에서 모든 잠재적 솔루션을 철저히 탐색하지 않고도 퇴각검색을 수행하는 기술이다.

컴파일 시간 메모리 관리

[편집]
BERJAYA
여러 수준의 프로시저 호출에 대한 로컬 데이터 및 호출 정보를 저장하는 일반적인 호출 스택. 이 스택은 원점에서 아래쪽으로 성장한다. 스택 포인터는 스택의 현재 맨 위 자료를 가리킨다. 푸시 연산은 포인터를 감소시키고 데이터를 스택에 복사한다. 팝 연산은 스택에서 데이터를 복사한 다음 포인터를 증가시킨다. 프로그램에서 호출된 각 프로시저는 프로시저 반환 정보(노란색) 및 로컬 데이터(다른 색상)를 스택에 푸시하여 저장한다. 이 유형의 스택 구현은 매우 일반적이지만 버퍼 오버플로 공격에 취약하다(텍스트 참조).

많은 스택 지향 프로그래밍 언어는 대부분의 기본 연산(두 숫자 더하기, 문자 인쇄)을 스택에서 인수를 가져오고 반환 값을 스택에 다시 배치하는 것으로 정의한다. 예를 들어, 포스트스크립트는 반환 스택과 피연산자 스택을 가지며, 그래픽 상태 스택과 사전 스택도 가진다. 많은 가상 머신도 스택 지향적이며, p-코드 머신 및 자바 가상 머신이 포함된다.

거의 모든 호출 규약 —서브루틴이 매개변수를 받고 결과를 반환하는 방식—은 호출된 함수의 컨텍스트로 전환하고 호출이 완료될 때 호출자 함수로 복원하기 위해 프로시저/함수 호출 및 중첩에 대한 정보를 저장하기 위해 특수 스택(콜 스택)을 사용한다. 함수는 스택에 인수 및 반환 값을 저장하기 위해 호출자와 호출자 간의 런타임 프로토콜을 따른다. 스택은 중첩되거나 재귀적 함수 호출을 지원하는 중요한 방법이다. 이 유형의 스택은 컴파일러에 의해 CALL 및 RETURN 문(또는 그에 상응하는 것)을 지원하기 위해 암시적으로 사용되며 프로그래머가 직접 조작하지 않는다.

일부 프로그래밍 언어는 스택을 사용하여 프로시저에 로컬인 데이터를 저장한다. 로컬 데이터 항목을 위한 공간은 프로시저가 시작될 때 스택에서 할당되고, 프로시저가 종료될 때 할당 해제된다. C 프로그래밍 언어는 일반적으로 이런 방식으로 구현된다. 데이터와 프로시저 호출에 동일한 스택을 사용하면 중요한 보안 문제가 발생할 수 있으며(아래 참조), 프로그래머는 프로그램에 심각한 보안 버그를 도입하지 않으려면 이러한 함정을 피하기 위해 특별한 주의를 기울여야 한다.

효율적인 알고리즘

[편집]

여러 알고리즘은 스택(대부분의 프로그래밍 언어의 일반적인 함수 호출 스택과는 별개)을 정보 구성의 주요 자료 구조로 사용한다. 여기에는 다음이 포함된다.

  • 그레이엄 스캔, 2차원 점 시스템의 볼록 폐포를 찾는 알고리즘. 입력의 부분 집합의 볼록 폐포는 스택에 유지되며, 새 점이 폐포에 추가될 때 경계에서 오목한 부분을 찾고 제거하는 데 사용된다.[21]
  • 단조 행렬의 행 최소값을 찾는 SMAWK 알고리즘의 일부는 그레이엄 스캔과 유사한 방식으로 스택을 사용한다.[22]
  • 모든 가장 가까운 더 작은 값, 배열의 각 숫자에 대해 자신보다 작은 가장 가까운 이전 숫자를 찾는 문제. 이 문제에 대한 한 알고리즘은 스택을 사용하여 가장 가까운 더 작은 값에 대한 후보 컬렉션을 유지한다. 배열의 각 위치에 대해, 스택의 맨 위에서 더 작은 값이 발견될 때까지 스택이 팝되고, 그런 다음 새 위치의 값이 스택에 푸시된다.[23]
  • 최근접 이웃 체인 알고리즘, 클러스터 스택을 유지하는 것을 기반으로 하는 응집형 계층적 클러스터링 방법으로, 각 클러스터는 스택에서 이전 클러스터의 최근접 이웃이다. 이 방법이 상호 최근접 이웃인 클러스터 쌍을 찾으면 팝되어 병합된다.[24]

보안

[편집]

일부 컴퓨팅 환경은 스택을 보안 침해 및 공격에 취약하게 만들 수 있는 방식으로 사용한다. 이러한 환경에서 작업하는 프로그래머는 이러한 구현의 함정을 피하기 위해 특별한 주의를 기울여야 한다.

예를 들어, 일부 프로그래밍 언어는 호출된 프로시저에 로컬인 데이터와 프로시저가 호출자에게 반환할 수 있도록 하는 연결 정보를 모두 저장하기 위해 공통 스택을 사용한다. 이는 프로그램이 프로시저 호출에 대한 중요한 반환 주소를 포함하는 동일한 스택으로 데이터를 이동하고 이동시킨다는 것을 의미한다. 데이터가 스택의 잘못된 위치로 이동되거나, 너무 큰 데이터 항목이 이를 포함할 만큼 충분히 크지 않은 스택 위치로 이동되면 프로시저 호출에 대한 반환 정보가 손상되어 프로그램이 실패할 수 있다.

악의적인 측은 입력 길이를 확인하지 않는 프로그램에 과도한 데이터 입력을 제공하여 이러한 유형의 구현을 악용하는 스택 스매싱 공격을 시도할 수 있다. 이러한 프로그램은 데이터를 스택의 특정 위치로 전체적으로 복사할 수 있으며, 이 과정에서 호출한 프로시저의 반환 주소를 변경할 수 있다. 공격자는 이러한 프로그램에 제공할 수 있는 특정 유형의 데이터를 찾기 위해 실험하여 현재 프로시저의 반환 주소가 스택 자체(및 공격자가 제공한 데이터 내)의 영역을 가리키도록 재설정되어, 결국 무단 작업을 수행하는 명령어를 포함하도록 할 수 있다.

이러한 유형의 공격은 버퍼 오버플로 공격의 변형이며 소프트웨어 보안 침해의 매우 빈번한 원인인데, 주로 가장 인기 있는 컴파일러 중 일부가 데이터와 프로시저 호출에 모두 공유 스택을 사용하고 데이터 항목의 길이를 확인하지 않기 때문이다. 종종 프로그래머도 데이터 항목의 크기를 확인하는 코드를 작성하지 않으며, 과도하거나 부족한 데이터 항목이 스택에 복사될 때 보안 침해가 발생할 수 있다.

같이 보기

[편집]

각주

[편집]
  1. ↑ By contrast, a queue operates first in, first out, referred to by the acronym FIFO.
  2. 1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. 《Introduction to Algorithms》 3판. MIT Press and McGraw-Hill. 232–233쪽. ISBN 0-262-03384-4.
  3. ↑ Turing, Alan Mathison (1946년 3월 19일). 《Proposals for Development in the Mathematics Division of an Automatic Computing Engine (ACE)》. (NB. Presented on 1946-03-19 before the Executive Committee of the National Physical Laboratory (Great Britain).)
  4. ↑ Carpenter, Brian Edward; Doran, Robert William (1977년 1월 1일). “The other Turing machine”. 《The Computer Journal》 20 (3): 269–279. doi:10.1093/comjnl/20.3.269. (11 pages)
  5. ↑ Blaauw, Gerrit Anne; Brooks, Jr., Frederick Phillips (1997). 《Computer architecture: Concepts and evolution》. Boston, Massachusetts, USA: Addison-Wesley Longman Publishing Co., Inc.
  6. ↑ LaForest, Charles Eric (April 2007). 〈2.1 Lukasiewicz and the First Generation: 2.1.2 Germany: Konrad Zuse (1910–1995); 2.2 The First Generation of Stack Computers: 2.2.1 Zuse Z4〉 (thesis). 《Second-Generation Stack Computer Architecture》 (PDF). Waterloo, Canada: University of Waterloo. 8, 11쪽. 2022년 1월 20일에 원본 문서 (PDF)에서 보존된 문서. 2022년 7월 2일에 확인함. (178 pages)
  7. ↑ Samelson, Klaus (1957). Internationales Kolloquium über Probleme der Rechentechnik, Dresden, Germany에서 작성. 《Probleme der Programmierungstechnik》 (독일어). Berlin, Germany: VEB Deutscher Verlag der Wissenschaften. 61–68쪽. (NB. This paper was first presented in 1955. It describes a number stack (Zahlenkeller), but names it linear auxiliary memory (linearer Hilfsspeicher).)
  8. 1 2 3 4 Fothe, Michael; Wilke, Thomas 편집 (2015). Jena, Germany에서 작성. 《Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial》 [Cellar, stack and automatic memory - a structure with potential] (PDF) (독일어) (Tagungsband zum Kolloquium 14. November 2014 in Jena). GI Series: Lecture Notes in Informatics (LNI) – Thematics T–7. Bonn, Germany: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. ISSN 1614-3213. 2020년 4월 12일에 원본 문서 (PDF)에서 보존된 문서. 2020년 4월 12일에 확인함. (77 pages)
  9. ↑ Bauer, Friedrich Ludwig; Samelson, Klaus (1957년 3월 30일). “Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens” (독일어). Munich, Germany: Deutsches Patentamt. DE-PS 1094019. 2010년 10월 1일에 확인함.
  10. ↑ Bauer, Friedrich Ludwig; Goos, Gerhard (1982). 《Informatik – Eine einführende Übersicht》 3판 (독일어). Part 1. Berlin: Springer-Verlag. 222쪽. ISBN 3-540-11722-9. Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.
  11. ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1959). “Sequentielle Formelübersetzung” [Sequential Formula Translation] (독일어). 《Elektronische Rechenanlagen》 1 (4): 176–182.
  12. ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1960). “Sequential Formula Translation”. 《Communications of the ACM》 3 (2): 76–83. doi:10.1145/366959.366968. S2CID 16646147.
  13. ↑ “IEEE-Computer-Pioneer-Preis – Bauer, Friedrich L.”. Technical University of Munich, Faculty of Computer Science. 1989년 1월 1일. 2017년 11월 7일에 원본 문서에서 보존된 문서.
  14. ↑ Hamblin, Charles Leonard (May 1957). 《An Addressless Coding Scheme based on Mathematical Notation》 (PDF) (typescript). N.S.W. University of Technology. 121–1 – 121–12쪽. 2020년 4월 12일에 원본 문서 (PDF)에서 보존된 문서. 2020년 4월 12일에 확인함. (12 pages)
  15. ↑ Kämmerer, Wilhelm (1958년 12월 11일). 《Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild》 (독일어) (Habilitation thesis). Jena, Germany: Mathematisch-naturwissenschaftliche Fakultät, Friedrich-Schiller-Universität. urn:nbn:de:gbv:27-20130731-133019-7. PPN:756275237. 2023년 10월 14일에 원본 문서에서 보존된 문서. 2023년 10월 14일에 확인함. (2+69 pages)
  16. ↑ Kämmerer, Wilhelm (1960). 《Ziffernrechenautomaten》 (독일어). Elektronisches Rechnen und Regeln 1. Berlin, Germany: Akademie-Verlag.
  17. ↑ Ball, John A. (1978). 《Algorithms for RPN calculators》 1판. Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 978-0-471-03070-6. LCCN 77-14977.
  18. ↑ Godse, Atul P.; Godse, Deepali A. (2010년 1월 1일). 《Computer Architecture》. Technical Publications. 1–56쪽. ISBN 978-8-18431534-9. 2015년 1월 30일에 확인함.
  19. ↑ Horowitz, Ellis (1984). 《Fundamentals of Data Structures in Pascal》. Computer Science Press. 67쪽.
  20. ↑ Pandey, Shreesham (2020). 《Data Structures in a Nutshell》. 《Dev Genius》 2020. SSRN 4145204.
  21. ↑ Graham, Ronald "Ron" Lewis (1972). 《An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set》 (PDF). Information Processing Letters 1 1. 132–133쪽. 2022년 10월 22일에 원본 문서 (PDF)에서 보존된 문서.
  22. ↑ Aggarwal, Alok; Klawe, Maria M.; Moran, Shlomo; Shor, Peter; Wilber, Robert (1987). “Geometric applications of a matrix-searching algorithm”. 《Algorithmica》 2 (1–4): 195–208. doi:10.1007/BF01840359. MR 895444. S2CID 7932878..
  23. ↑ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993). “Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values”. 《Journal of Algorithms》 14 (3): 344–370. CiteSeerX 10.1.1.55.5669. doi:10.1006/jagm.1993.1018..
  24. ↑ Murtagh, Fionn (1983). “A survey of recent advances in hierarchical clustering algorithms” (PDF). 《The Computer Journal》 26 (4): 354–359. doi:10.1093/comjnl/26.4.354..

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=스택&oldid=41719180"