추상적 자료 구조

추상 자료형이 말 그대로 자료의 형식만을 정의하는 가장 높은 단계의 추상화라면,
추상적 자료구조는 해당 자료형을 구체적으로 구현하기 위한 조건들도 함께 정의한다.

“스택(stack)이라는 자료형(data type)의 입출력을 위한 방법에는 push와 pop이 있고, 이 연산들은 O(1)만에 이뤄져야 한다."

고 정의된 것이 있다면 이것을 추상적 자료구조라고 말하며, 이를 구현한 것을 구체적 자료구조라고 말한다.

이렇게 위키피디아 한글 문서에서는 설명하고 있으나 영문판에서는 ‘추상 자료구조’와 ‘추상 자료형’의 정의 간에 특별한 구분을 두고 있지는 않는 것 같다. 추상 자료형과 자료구조의 차이 정도만 인식하고 있으면 될 것 같다.

자료구조를 어떻게 정의하여 내부적으로 어떻게 구현했는가는 작성자에게 달려있기에 프로그래밍 언어에 따라 다르다. 예를 들어 스택 (Stack)은 리스트로도 구현할 수 있고 배열 (Array)로도 구현할 수 있다.