01 Ago 2019

스택 알고리즘 예제

스택에는 요소의 삽입 및 삭제에 제한이 있습니다. 요소는 스택의 한쪽 끝(예: $$top$$)에서만 삽입하거나 삭제할 수 있습니다. 맨 위에 있는 요소를 $$top$$ 요소라고 합니다. 요소를 삽입하고 삭제하는 작업을 각각 $$push()$$와 $$pop()$$라고 합니다. 스택에 크게 의존하는 일부 환경은 추가 작업을 제공할 수 있습니다: 서브루틴이 매개 변수를 수신하고 결과를 반환하는 방법 – 특수 스택(«호출 스택»)을 사용하여 정보를 보유하는 거의 모든 호출 규칙 호출된 함수의 컨텍스트로 전환하고 호출이 완료되면 호출 함수에 복원하기 위해 프로시저/함수 호출 및 중첩에 대해 함수는 호출자와 호출 수신자 간의 런타임 프로토콜을 따라 인수를 저장하고 스택에서 값을 반환합니다. 스택은 중첩 또는 재귀 함수 호출을 지원하는 중요한 방법입니다. 이 유형의 스택은 CALL 및 RETURN 문(또는 해당 이에 상응하는 명령문)을 지원하기 위해 컴파일러에서 암시적으로 사용되며 프로그래머가 직접 조작하지 않습니다. 스택 포인터는 스택의 원점 또는 원점 위 또는 아래에 있는 제한된 범위의 주소를 가리킬 수 있습니다(스택이 증가하는 방향에 따라 다름). 그러나 스택 포인터는 스택의 원점을 교차할 수 없습니다. 즉, 스택의 원본이 주소 1000에 있고 스택이 아래쪽으로 증가하는 경우(주소 999, 998 등) 스택 포인터는 1000(1001, 1002 등)을 초과하여 증가해서는 안 됩니다.

스택의 팝 작업으로 인해 스택 포인터가 스택의 원점을 지나이동하면 스택 언더플로우가 발생합니다. 푸시 작업으로 인해 스택 포인터가 스택의 최대 범위를 초과하거나 감소하면 스택 오버플로가 발생합니다. 스택은 작업이 수행되는 특정 순서를 따르는 선형 데이터 구조입니다. 순서는 LIFO (마지막 첫 번째 아웃) 또는 FILO (마지막 아웃에서 첫 번째)일 수 있습니다. 스택의 또 다른 중요한 응용 프로그램은 역추적입니다. 미로에서 올바른 경로를 찾는 간단한 예를 생각해 보십시오. 시작 지점에서 목적지까지 일련의 포인트가 있습니다. 우리는 한 지점에서 시작합니다. 최종 목적지에 도달하기 위해 여러 경로가 있습니다. 임의의 경로를 선택한다고 가정해 보겠습니다.

어떤 길을 따라간 후, 우리는 우리가 선택한 길이 틀렸다는 것을 깨닫습니다. 그래서 우리는 그 길의 시작으로 돌아갈 수 있는 방법을 찾아야 합니다. 이 스택의 사용으로 수행할 수 있습니다. 스택의 도움으로, 우리는 우리가 도달 한 지점을 기억합니다. 이 작업은 해당 지점을 스택으로 푸시하여 수행됩니다. 우리가 잘못된 경로에 끝날 경우, 우리는 스택에서 마지막 지점을 팝업 따라서 마지막 지점으로 돌아 올바른 경로를 찾기 위해 우리의 탐구를 계속 할 수 있습니다.