추상 데이터 유형

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 기사에는 독창적인 연구가 포함되어 있을 가능성이 있다. 클레임을 확인하고 인라인 인용을 추가하여 개선해 주십시오. 독창적인 연구로만 구성된 문장은 삭제해야 합니다. (2015년 3월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '추상 데이터형'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2009년 5월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

컴퓨터 과학에서 추상 데이터 유형(ADT)은 데이터 유형의 수학적 모델입니다.추상 데이터 유형은 사용자의 관점, 데이터의 관점, 특히 가능한 값, 이 유형의 데이터에 대한 가능한 연산 및 이러한 연산의 동작에 대한 그 행동(의미학)에 의해 정의됩니다.이 수학적 모델은 데이터의 구체적인 표현인 데이터 구조와 대조되며 사용자가 아닌 구현자의 관점입니다.

형식적으로 ADT는 "값 집합과 연산 집합에 의해 논리적인 동작이 정의되는 객체의 클래스"^[1]로 정의될 수 있다. 이는 수학의 대수 구조와 유사하다."행동"이 의미하는 것은 작성자에 따라 다르며, 행동에 대한 두 가지 주요 형식 사양 유형은 자명(대칭) 사양과 추상 ^[2]모델이다. 이들은 각각 추상 기계의 자명 의미론과 작동 의미론에 해당한다.또한 일부 저자는 시간(계산 작업용)과 공간(가치 표현용) 모두에서 계산 복잡성("비용")을 포함합니다.실제로는 추상화가 완벽하지 않기 때문에 많은 일반적인 데이터 유형은 ADT가 아닙니다.또한 사용자는 표현에 기인하는 산술 오버플로우 등의 문제를 알고 있어야 합니다.예를 들어 정수는 고정 폭 값(32비트 또는 64비트 이진수)으로 저장되기 때문에 최대값을 초과할 경우 정수 오버플로가 발생합니다.

ADT는 컴퓨터 과학에서 알고리즘, 데이터 구조 및 소프트웨어 시스템의 설계 및 분석에 사용되는 이론적 개념으로 컴퓨터 언어의 특정 기능에 해당하지 않습니다. 주류 컴퓨터 언어는 공식적으로 지정된 ADT를 직접 지원하지 않습니다.그러나 다양한 언어 기능은 ADT의 특정 측면에 대응하고 있으며 ADT 고유의 특징과 혼동하기 쉽습니다. 여기에는 추상형, 불투명한 데이터 유형, 프로토콜 및 계약에 의한 설계가 포함됩니다.ADT는 1974년 ^[3]바바라 리스코프와 스티븐 질레스에 의해 CLU 언어 개발의 일부로 처음 제안되었다.

추상 데이터 유형

예를 들어 정수는 (정수 나눗셈에 주의하여) 친숙한 수학에 따라 동작하는 (정수 나눗셈에 주의하여) ..., -2, -1, -1, 0, 1, 2, ..., 덧셈, 뺄셈, 곱셈, 나눗셈 등의 연산에 의해 정의되는 ADT입니다.er. 명시적으로 "행동"은 다양한 공리(더하기의 연관성 및 교환성 등)와 연산에 대한 전제조건(0으로 나눌 수 없음)을 따르는 것을 포함한다.일반적으로 정수는 데이터 구조에서 2진수로 표현되며, 대부분 2의 보완수로 표현되지만, 2진수로 구분되거나 1의 보완으로 표현될 수 있습니다. 그러나 대부분의 경우 사용자는 구체적인 표현 선택이 아닌 추상화로 작업할 수 있으며, 단순히 유형이 정말로 추상적인 것처럼 데이터를 사용할 수 있습니다.

ADT는 연산뿐만 아니라 값의 도메인 및 정의된 연산에 대한 제약으로 구성됩니다."인터페이스"는 일반적으로 동작의 일부(예: 전제조건 및 사후조건)만을 가리킬 뿐, 동작간의 관계 등 다른 제약조건은 가리킬 수 없습니다.

예를 들어, 추상 스택은 3가지 조작으로 정의할 수 있습니다.즉, 스택에 데이터 아이템을 삽입하는 조작, 데이터 아이템을 삭제하는 조작, 또는 스택 상단의 데이터 아이템에 삭제 없이 액세스하는 조작입니다.선입선출 구조인 추상 큐에는 데이터 항목을 큐에 삽입하는 조작, 데이터 항목에서 첫 번째 데이터 항목을 삭제하는 조작, 큐 내의 첫 번째 데이터 항목에 액세스하여 서비스를 제공하는 조작의 3가지도 있습니다.만약 이것이 전체 정의라면, 이 두 가지 데이터 유형과 예상 주문 동작을 구분할 수 있는 방법은 없습니다.따라서 스택의 경우 각 팝이 아직 팝되지 않은 가장 최근에 푸시된 항목을 항상 반환(및 삭제)하도록 지정하고 큐의 경우 팝이 가장 최근에 푸시된 항목에서 작동하도록 지정하는 제약 조건이 도입되었습니다.

알고리즘의 효율성을 분석할 때 스택에 푸시된 데이터 항목의 수에 관계없이 모든 작업에 동일한 시간이 걸리고 스택이 각 요소에 대해 일정한 양의 스토리지를 사용하도록 지정할 수도 있습니다.단, 시간범위가 항상 ADT 정의의 일부로 간주되는 것은 아닙니다.

서론

추상 데이터형은 순수하게 이론적인 실체로 추상 알고리즘의 기술을 단순화하고, 데이터 구조를 분류 및 평가하며, 프로그래밍 언어의 유형 시스템을 공식적으로 기술하기 위해 사용됩니다.단, ADT는 특정 데이터 유형 또는 데이터 구조에 의해 구현될 수 있습니다.다양한 방법과 많은 프로그래밍 언어로 구현될 수 있습니다.또는 정식 사양 언어로 기술될 수도 있습니다.ADT는 모듈로 구현되는 경우가 많습니다.모듈의 인터페이스는 ADT 조작에 대응하는 프로시저를 선언합니다.경우에 따라서는 제약조건을 설명하는 코멘트를 사용합니다.이 정보 숨김 전략을 통해 클라이언트 프로그램을 방해하지 않고 모듈 구현을 변경할 수 있습니다.

추상 데이터 유형이라는 용어는 격자, 그룹 및 ^[4]링과 같은 여러 대수 구조의 일반화된 접근법으로도 간주할 수 있다.추상 데이터 유형의 개념은 객체 지향 프로그래밍 및 소프트웨어 ^[5]개발을 위한 계약 방법론에 의한 설계에서 중요한 데이터 추상화의 개념과 관련이 있습니다.

추상 데이터 유형 정의

추상 데이터 유형은 데이터 유형을 구성하는 데이터 개체와 이러한 개체에서 작동하는 함수의 수학적 모델로 정의됩니다.이들을 정의하기 위한 표준 규약은 없습니다."제국적"(또는 "작동적"(또는 "작동적")과 "기능적"(또는 "축적"(Axiomatic) 정의 스타일 사이에 광범위한 구분이 그려질 수 있다.

명령형 정의

명령형 프로그래밍 언어 이론에서 추상 데이터 구조는 변동 가능한 실체로 간주됩니다. 즉, 다른 시간에 다른 상태에 있을 수 있습니다.일부 동작은 ADT 상태를 변경할 수 있습니다.따라서 동작의 평가 순서가 중요하며, 같은 엔티티에서 동일한 동작이 다른 시간에 실행될 경우 다른 영향을 미칠 수 있습니다.이것은 컴퓨터의 명령이나 명령어의 명령과 절차와 유사합니다.이 관점을 강조하기 위해 추상 알고리즘을 기술할 때 자주 사용되는 명령형 스타일과 유사한 연산이 평가되지 않고 실행 또는 적용된다고 말하는 것이 관례입니다(자세한 내용은 Donald Knuth의 컴퓨터 프로그래밍 기술 참조).

추상 변수

ADT의 명령형 정의는 종종 추상 변수의 개념에 의존하며, 추상 변수는 가장 단순하지 않은 ADT로 간주될 수 있습니다.추상 변수 V는 다음 두 가지 작업을 허용하는 가변 엔티티입니다.

• store(V, x) 여기서 x는 불특정 성질의 값이다.
• fetch(V) 값을 산출하는 경우,

라는 제약으로

• fetch(V)는 항상 같은 변수 V의 최신(V, x) 연산에 사용된 값 x를 반환합니다.

저장하기 전에 가져오기를 허용하지 않거나 특정 결과를 가져오도록 정의하거나 동작을 지정하지 않은 상태로 둘 수 있습니다.

많은 프로그래밍 언어에서와 같이, 연산(V, x)은 종종 V ← x(또는 유사한 표기법)로 쓰이고, (V)는 값이 필요한 컨텍스트에서 변수 V를 사용할 때마다 암시됩니다.따라서, 예를 들어, V ← V + 1은 일반적으로 (V,fetch (V) + 1)의 약자로 이해된다.

이 정의에서는 이름이 항상 구별된다고 암묵적으로 가정합니다.변수 U에 값을 저장하는 것은 고유 변수 V의 상태에 영향을 주지 않습니다.이 가정을 명확히 하기 위해 다음과 같은 제약을 추가할 수 있다.

• U와 V가 별개의 변수인 경우 시퀀스 {(U, x);(V, y)}은(는) {(V, y);(U, x) }에 해당합니다.

보다 일반적으로 ADT 정의에서는 ADT 공리에 의해 특정 인스턴스가 특정 방법으로 연결되어 있다고 정의되지 않는 한 ADT 인스턴스의 상태를 변경하는 조작은 동일한 ADT의 다른 인스턴스 상태에 영향을 주지 않는다고 가정합니다(에일리어스 참조).이러한 접속의 가장 일반적인 예는 다음과 같습니다.

• 에일리어스: 두 개 이상의 이름이 완전히 동일한 데이터 개체를 참조합니다.
• ADT가 (동일 또는 기타) ADT 인스턴스를 포함하도록 정의되는 구성.
• 참조: ADT가 (동일 또는 기타) ADT 인스턴스를 참조하도록 정의되어 있습니다.

예를 들어 추상변수의 정의를 추상기록을 포함하도록 확장하는 경우, 레코드변수 R의 필드 F에 대한 연산은 R과 구별되지만 R의 일부인 F를 포함한다.

ADT의 정의는 인스턴스의 저장된 값을 변수 범위라고 불리는 특정 집합 X의 멤버로 제한할 수 있습니다.예를 들어 스택이나 큐 등의 집약에 대한 ADT는 큐 내의 모든 항목을 정수 또는 적어도 단일 유형으로 제한할 수 있습니다(동질성 참조).프로그래밍 언어에서와 같이 이러한 제한은 알고리즘의 설명과 분석을 단순화하고 가독성을 향상시킬 수 있습니다.

이 정의는 V가 초기화되지 않은 경우, 즉 V에 대한 작업을 수행하기 전에 (V)를 평가한 결과를 의미하는 것은 아닙니다.그렇게 하는 알고리즘은 (a) ADT에 의해 그러한 동작이 금지되어 있거나 (b) ADT에 의해 그 효과가 정의되어 있지 않기 때문에 무효로 간주될 수 있습니다.단, 효율은 그러한 것이 합법적이라는 가정에 따라 크게 달라지며 변수의 범위 내에서 임의의 값을 반환하는 중요한 알고리즘이 있습니다.)^{[citation needed]}

인스턴스 생성

알고리즘에 따라서는 일부 ADT의 새로운 인스턴스(새로운 변수 또는 새로운 스택 등)를 작성해야 합니다.이러한 알고리즘을 기술하기 위해 ADT 정의에는 보통 ADT의 인스턴스를 생성하는 () 연산을 포함하며, 보통 다음과 같은 공리를 사용합니다.

• ()의 결과는 알고리즘에서 이미 사용 중인 인스턴스와는 다릅니다.

이 공리는 다른 인스턴스와의^{[clarification needed]} 부분 에일리어싱을 제외하도록 강화될 수 있습니다.예를 들어, 공리(aciom)와 같은 실용적인 용도로는 ()의 구현이 프로그램이 액세스할 수 없게 된 이전에 생성된 인스턴스를 생성하는 것을 여전히 허용할 수 있습니다. 그러나 이러한 인스턴스마저도 추상적으로 정의하기는 어렵습니다(비록 재사용되는 메모리 블록은 특정 의미에서 "같은 객체"일 뿐이지만).

예: 추상 스택(임페리얼)

또 다른 예로서 추상 스택의 명령형 정의는 스택S의 상태를 조작에 의해서만 변경할 수 있도록 지정할 수 있습니다.

• push(S, x), 여기서 x는 지정되지 않은 성질의 값이다.
• pop(S) 결과적으로 값을 산출한다.

라는 제약으로

• 모든 값 x 및 추상 변수 V에 대해 작업 순서 {(S, x); V ← (S) }은(는) V ← x와 동일합니다.

할당 V ← x는 정의상 S의 상태를 변경할 수 없으므로, 이 조건은 V ← (S)가 S를 (S, x) 이전 상태로 복원한다는 것을 의미합니다.이 조건과 추상 변수의 속성으로부터, 예를 들어, 시퀀스는 다음과 같습니다.

{ (S, x), (S, y), U ← (S), (S, z), V ← (S), W ← (S) }

여기서 x, y 및 z는 값이고 U, V, W는 쌍으로 구분되는 변수이며 다음과 같습니다.

{ U ← y, V ← z, W ← x }

여기서는 스택인스턴스에서의 조작으로 다른 스택을 포함한 다른 ADT 인스턴스의 스테이트가 변경되지 않는 것을 암묵적으로 상정하고 있습니다.즉,

• 값 x, y 및 고유한 스택 S 및 T에 대해 시퀀스 { (S, x); (T, y)}은(는) { (T, y); (S, x) }에 해당합니다.

추상 스택 정의에는 보통 부울값 함수(S)와 스택인스턴스를 반환하는 () 연산도 포함됩니다.이 연산에는 다음과 같은 공리가 포함됩니다.

• create( ) 이전 스택S의 경우 (새로 작성된 스택은 이전 스택과는 다릅니다)
• empty()create (새로 작성된 스택은 비어 있습니다);
• not empty(pushS, x) (스택에 밀어넣으면 비어있지 않습니다.)

싱글 인스턴스 스타일

알고리즘 실행 중에 ADT의 인스턴스가1개밖에 존재하지 않는 것처럼 정의되어 모든 조작이 그 인스턴스에 적용되고 있는 경우가 있습니다.이것은 명시적으로 통지되지 않습니다.예를 들어, 위의 추상 스택은 기존 스택에서만 작동하는 연산(x) 및()을 사용하여 정의할 수 있습니다.이 스타일의 ADT 정의는 암묵적인 인스턴스를 사용하거나 변경하는 모든 조작에 명시적인 인스턴스 파라미터(이전 예의 S 등)를 추가함으로써 ADT의 여러 공존 인스턴스를 허용하도록 쉽게 고쳐 쓸 수 있습니다.

한편, 복수의 인스턴스를 상정하지 않고서는, 의미 있게 정의할 수 없는 ADT도 있습니다.이것은, 1개의 조작으로 ADT의 2개의 다른 인스턴스가 파라미터로서 취득되는 경우입니다.예를 들어, 스택 S와 T에 동일한 항목이 같은 순서로 포함되어 있는지 여부를 확인하는 연산(S, T)을 사용하여 추상 스택의 정의를 확장하는 것을 고려해 보십시오.

기능 스타일의 정의

기능 프로그래밍 정신에 가까운 ADT를 정의하는 또 다른 방법은 구조의 각 상태를 별개의 실체로 간주하는 것입니다.이 뷰에서 ADT를 수정하는 연산은 이전 상태를 인수로 사용하고 결과의 일부로 새 상태를 반환하는 수학 함수로 모델링됩니다.이러한 기능은 필수 조작과 달리 부작용이 없습니다.따라서 이들 명령어가 평가되는 순서는 중요하지 않으며 동일한 인수(같은 입력 상태 포함)에 적용되는 동일한 연산에서는 항상 동일한 결과(및 출력 상태)가 반환됩니다.

특히 기능적 관점에서는 명령 변수(즉, 명령 변수, with 및 연산)의 의미론을 사용하여 "추상 변수"를 정의할 방법(또는 필요)이 없습니다.값을 변수에 저장하는 대신 함수 인수로 전달합니다.

예: 추상 스택(기능)

예를 들어 추상 스택의 완전한 기능 스타일 정의에서는 다음 세 가지 연산을 사용할 수 있습니다.

• push: 스택 상태와 임의의 값을 가져와서 스택 상태를 반환합니다.
• top: 스택 상태를 취하고 값을 반환합니다.
• pop: 스택 상태가 되어 스택 상태가 반환됩니다.

함수 스타일의 정의에서는 연산이 필요하지 않습니다.실제로 "스택 인스턴스"라는 개념은 없습니다.스택 스테이트는 단일 스택 구조의 잠재적인 스테이트로 간주할 수 있으며, 같은 순서로 같은 값을 포함하는2개의 스택스테이트는 동일한 스테이트로 간주됩니다.이 뷰는 실제로 해시 콘센트가 있는 링크 목록과 같은 일부 구체적인 구현의 동작을 반영합니다.

() 대신 () 추상 스택의 기능 스타일 정의는 특수 스택 상태, 즉 δ 또는 (")와 같은 특수 기호로 지정된 빈 스택의 존재를 가정하거나 인수를 사용하지 않고 이 특수 스택 상태를 반환하는 () 연산을 정의할 수 있습니다.주의: 이 공리는 다음을 의미합니다.

• push(Ω, x) λ (.

스택의 함수형 정의에서는 술어가 필요하지 않습니다.대신 스택이 비어 있는지 여부를 테스트하는 것으로, 스택이 비어 있는지를 테스트할 수 있습니다.

s가 반환하는 스택 상태가 아닌 한 이러한 공리는 (s) 또는 (s)의 효과를 정의하지 않습니다. s가 반환하는 스택 상태를 비워두지 않는 한, s = Ω일 때 이들 두 연산은 정의되지 않습니다(무효). 반면, (및 부작용의 결여) 공리는 x와 y의 경우에만 (s, x) = (t, y)를 의미합니다.

수학의 다른 분야와 마찬가지로 스택 상태는 한정된 수의 단계에서 공리로부터 증명될 수 있는 상태라고 가정하는 것이 관례입니다.위의 추상 스택의 예에서 이 규칙은 모든 스택이 유한한 일련의 값임을 의미하며, 유한한 수의 s 뒤에 빈 스택(δ)이 됩니다.그 자체로는 무한 스택(영원히 다른 상태를 생성할 수 있음) 또는 순환 스택(유한 수의 s 후에 같은 상태로 돌아가는 것)의 존재를 배제하지 않습니다.특히, 일부 x에 대해 (s) = s 또는 (s, x) = s와 같은 상태는 제외하지 않는다.단, 특정 연산으로는 이러한 스택 상태를 얻을 수 없기 때문에 "존재하지 않는" 것으로 간주됩니다.

복잡성 포함 여부

공리에 관한 동작과는 별도로 ADT 연산의 정의에 알고리즘의 복잡성을 포함할 수도 있습니다.C++ Standard Template Library의 설계자인 Alexander Stephanov는 STL 사양에 복잡성 보증을 포함시키면서 다음과 같이 주장했습니다.

추상 데이터 유형의 개념을 도입한 이유는 소프트웨어 모듈을 상호 교환할 수 있게 하기 위해서입니다.이러한 모듈이 동일한 복잡성 동작을 공유하지 않는 한 호환 가능한 모듈을 가질 수 없습니다.기능 동작은 같지만 복잡도가 다른 모듈을 다른 모듈로 교체하면 이 코드 사용자는 불쾌하게 놀랄 것입니다.나는 그에게 데이터 추상화에 대해 내가 좋아하는 어떤 것이라도 말할 수 있었지만 그는 여전히 그 코드를 사용하고 싶어하지 않았다.복잡도 어설션은 인터페이스의 일부여야 합니다.

--

추상 데이터 입력의 이점

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2011년 5월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍에 대해 알아보기)

캡슐화

추상화는 ADT의 구현에 특정한 특성과 능력이 있음을 약속합니다. ADT 개체를 사용하기 위해 필요한 것은 이것뿐입니다.

변경의 현지화

ADT 오브젝트를 사용하는 코드는 ADT 구현이 변경되면 편집할 필요가 없습니다.실장 변경은 인터페이스에 준거해야 하며 ADT 오브젝트를 사용하는 코드는 인터페이스에 지정된 속성 및 기능만을 참조할 수 있으므로 ADT가 사용되는 코드를 변경하지 않고 실장 변경을 실시할 수 있습니다.

유연성

ADT 의 다른 실장은, 모두 같은 속성과 능력을 가지는 것으로, ADT 를 사용하는 코드에서는 어느 정도 교환 가능하게 사용할 수 있습니다.이것에 의해, 다양한 상황에서 ADT 오브젝트를 사용할 때, 큰 유연성을 얻을 수 있습니다.예를 들어, ADT의 다른 실장은 다른 상황에서 더 효율적일 수 있습니다.그것들이 바람직한 상황에서 각각의 실장을 사용할 수 있기 때문에 전체적인 효율이 향상됩니다.

일반적인 조작

ADT용으로 지정되어 있는 조작의 일부(다른 이름으로 되어 있을 가능성이 있습니다)는, 다음과 같습니다.

• (s, t) 두 인스턴스의 상태가 어떤 의미에서 동일한지 여부를 테스트한다compare.
• (s) 인스턴스 상태로부터 표준 해시 함수를 계산합니다hash.
• print(s) 또는 (s) 즉, 인스턴스 상태를 인간에 의해 표현합니다.

명령형 ADT 정의에서 흔히 찾을 수 있다.

• create()는 ADT의 새로운 인스턴스를 생성합니다.
• (s) 추가 작업을 위해 새로 생성된 인스턴스를 준비하거나 "초기 상태"로 재설정합니다initialize.
• (s, t), 인스턴스 s를 t와 동등한 상태로 한다copy.
• clone(t) s ←() (s, t)를 수행하고 s를 반환합니다.
• free(s) 또는 (s)에 의해 사용되는 메모리 및 기타 자원을 회수합니다.

ADT는 "메모리를 사용하지 않는" 이론적인 실체이기 때문에 이 작업은 일반적으로 관련이 없거나 의미가 없습니다.다만, ADT 를 사용하는 알고리즘에 의해서 사용되는 스토리지를 분석할 필요가 있는 경우는, 필요하게 됩니다.이 경우 각 ADT 인스턴스가 사용하는 메모리의 양, 상태 함수 및 에 의해 풀로 반환되는 메모리의 양을 지정하는 추가 공리가 필요합니다.

예

다양한 응용 프로그램에서 유용한 것으로 판명된 몇 가지 일반적인 ADT는 다음과 같습니다.

이러한 ADT 각각은, 반드시 동등하다고는 할 수 없는, 다양한 방법으로 정의될 수 있습니다.예를 들어 추상 스택은 푸시된 항목 수와 아직 팝되지 않은 항목 수를 알려주는 작업을 수행할 수도 있습니다.이 선택은 클라이언트뿐만 아니라 구현에도 영향을 미칩니다.

추상 그래픽 데이터 유형

컴퓨터 그래픽을 위한 ADT의 확장은 ^[7]1979년에 제안되었습니다. 추상 그래픽 데이터 유형(AGDT)입니다.Nadia Magnenat Thalmann과 Daniel Thalmann에 의해 소개되었습니다.AGDT는 구조화된 방식으로 그래픽 객체를 구축하는 기능을 갖춘 ADT의 장점을 제공합니다.

실행

ADT를 구현한다는 것은 추상적인 작업마다 하나의 절차 또는 기능을 제공한다는 것을 의미합니다.ADT 인스턴스는 ADT 사양에 따라 이러한 절차에 의해 조작되는 구체적인 데이터 구조로 나타납니다.

일반적으로 여러 가지 다른 구체적인 데이터 구조를 사용하여 동일한 ADT를 구현하는 방법은 많습니다.따라서 예를 들어 추상 스택은 링크된 목록 또는 배열에 의해 구현될 수 있습니다.

클라이언트가 실장에 의존하지 않도록 하기 위해 ADT는 1개 이상의 모듈에서 불투명한 데이터 타입으로 패키지화되어 있습니다.이 모듈에는 동작의 시그니처(파라미터와 결과의 수, 타입)만 포함되어 있습니다.모듈의 실장(즉, 사용된 절차의 본문 및 구체적인 데이터 구조)은 모듈의 대부분의 클라이언트에서 숨길 수 있습니다.이것에 의해, 클라이언트에 영향을 주지 않고 실장을 변경할 수 있습니다.구현이 노출되면 대신 투명한 데이터 유형으로 알려져 있습니다.

ADT를 구현할 때 각 인스턴스(명령형 정의) 또는 각 상태(기능형 정의)는 일반적으로 일종의 ^[8]핸들로 표시됩니다.

C++ 및 Java와 같은 최신 객체 지향 언어는 추상 데이터 유형을 지원합니다.클래스가 유형으로 사용되는 경우 숨겨진 표현을 참조하는 추상 유형입니다.이 모델에서 ADT는 일반적으로 클래스로 구현되며 ADT의 각 인스턴스는 보통 해당 클래스의 객체입니다.모듈의 인터페이스는 일반적으로 컨스트럭터를 일반 프로시저로 선언하고 다른 ADT 연산 대부분을 해당 클래스의 메서드로 선언합니다.그러나 이러한 접근방식은 ADT에서 발견되는 여러 표현적 변형을 쉽게 캡슐화하지 않습니다.또한 객체 지향 프로그램의 확장성을 저해할 수 있습니다.인터페이스를 유형으로 사용하는 순수한 객체 지향 프로그램에서 유형은 표현이 아닌 행동을 나타냅니다.

예: 추상 스택 구현

예를 들어 위의 추상 스택을 C 프로그래밍 언어로 구현한 예를 제시하겠습니다.

명령형 인터페이스

명령형 인터페이스는 다음과 같습니다.

유형화된 구조 스택_Rep 스택_Rep;       // 유형: 스택인스턴스 표현(레코드) 유형화된 스택_Rep* 스택_T;               // type: 스택인스턴스에 대한 핸들(스택 포인터) 유형화된 무효* 스택_아이템;                 // type: 스택인스턴스에 저장된 값(표준 주소)  스택_T stack_create(무효);               // 빈 스택인스턴스를 새로 만듭니다. 무효 stack_module(스택_T s, 스택_아이템 x); // 스택의 맨 위에 항목을 추가합니다. 스택_아이템 스택_팝(스택_T s);          // 스택에서 상위 항목을 제거한 후 반환 부울 stack_empty(스택_T s);              // 스택이 비어 있는지 확인합니다. 

이 인터페이스는, 다음의 방법으로 사용할 수 있습니다.

#실패하다 <stack.h>// 스택인터페이스 포함  스택_T s = stack_create(); // 빈 스택인스턴스를 새로 만듭니다. 인트 x = 17; stack_module(s, &x);          // 스택 상단에 x 주소를 추가합니다. 무효* y = 스택_팝(s);     // 스택에서 x 주소를 삭제하고 반환한다. 한다면 (stack_empty(s)) { }     // 스택이 비어 있는 경우 처리 

이 인터페이스는 다양한 방법으로 구현할 수 있습니다.위의 ADT의 정식 정의에서는 스택이 사용할 수 있는 공간이나 각 조작의 소요시간이 지정되어 있지 않기 때문에 실장은 임의로 비효율적일 수 있습니다.또, 콜 x ← (s) 후에도 스택스테이트가 계속 존재하는지 아닌지도 지정되어 있지 않습니다.

실제로 공식 정의에서는 공간이 푸시된 항목과 아직 팝되지 않은 항목 수에 비례하고 위의 모든 작업이 해당 수와 관계없이 일정한 시간 내에 완료되어야 한다고 명시해야 합니다.이러한 추가 사양을 준수하기 위해 구현에서는 링크 목록 또는 어레이(동적 크기 조정)를 2개의 정수(항목 수 및 어레이 크기)와 함께 사용할 수 있습니다.

기능형 인터페이스

기능형 ADT 정의는 기능형 프로그래밍 언어에 더 적합하며, 그 반대의 경우도 마찬가지입니다.단, C와 같은 명령어에서도 기능형 인터페이스를 제공할 수 있습니다.예를 들어 다음과 같습니다.

유형화된 구조 스택_Rep 스택_Rep;          // 유형: 스택 상태 표현(레코드) 유형화된 스택_Rep* 스택_T;                  // 유형: 핸들을 스택 상태로 전환합니다(예: 포인터). 유형화된 무효* 스택_아이템;                    // type: 스택스테이트의 값(표준 주소)  스택_T stack_empty(무효);                   // 빈 스택 상태를 반환합니다. 스택_T stack_module(스택_T s, 스택_아이템 x); // 스택 상태의 맨 위에 항목을 추가하고 결과 스택 상태를 반환합니다. 스택_T 스택_팝(스택_T s);                // 상위 항목을 스택 상태에서 제거하고 결과 스택 상태를 반환합니다. 스택_아이템 스택_탑(스택_T s);             // 스택 상태의 상위 항목을 반환합니다. 

ADT 라이브러리

C++ 및 Java와 같은 많은 현대 프로그래밍 언어에는 위에 나열된 것과 같은 몇 가지 공통 ADT를 구현하는 표준 라이브러리가 포함되어 있습니다.

기본 제공 추상 데이터 유형

일부 프로그래밍 언어의 사양은 특정 임베디드 데이터 유형의 표현에 대해 의도적으로 모호하며, 해당 유형에 대해 수행할 수 있는 작업만 정의합니다.따라서 이러한 유형은 "내장 ADT"로 볼 수 있습니다.예를 들어 Awk, Lua 및 Perl과 같은 많은 스크립트 언어의 배열은 추상 목록의 구현으로 간주할 수 있습니다.

「 」를 참조해 주세요.

• 개념(일반 프로그래밍)
• 형식적인 방법
• 기능사양서
• 일반화 대수 데이터형
• 초기 대수
• 리스코프 치환 원리
• 유형 이론
• 벽과 거울

메모들

인용문

레퍼런스

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다. (2022년 4월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

추가 정보

• Mitchell, John C.; Plotkin, Gordon (July 1988). "Abstract Types Have Existential Type" (PDF). ACM Transactions on Programming Languages and Systems. 10 (3): 470–502. doi:10.1145/44501.45065. S2CID 1222153.

외부 링크

• Wikimedia Commons의 Abstract 데이터 유형과 관련된 미디어
• NIST 알고리즘 및 데이터 구조 사전의 추상 데이터 유형