스택은 자료를 쌓아올리는 방식으로 저장한다. 책을 쌓아둔 것과 같다. 5권의 책을 쌓아뒀을 때, 첫 번째 책을 꺼내보려면 그 책 위의 네 권을 먼저 들어올려야 한다. 이러한 특징을 FILO(First In Last Out), LIFO(Last In First Out). 처음 들어온 게 마지막에 나간다고 줄여 말한다. 스택은 추상적 자료 구조이고, 이를 구체적으로 어떻게 구현할지는 구현자 마음대로이다.
추상 자료형이 말 그대로 자료의 형식만을 정의하는 가장 높은 단계의 추상화라면, 추상적 자료구조는 해당 자료형을 구체적으로 구현하기 위한 조건들도 함께 정의한다. “스택(stack)이라는 자료형(data type)의 입출력을 위한 방법에는 push와 pop이 있고, 이 연산들은 O(1)만에 이뤄져야 한다." 고 정의된 것이 있다면 이것을 추상적 자료구조라고 말하며, 이를 구현한 것을 구체적 자료구조라고 말한다. 이렇게 위키피디아 한글 문서에서는 설명하고 있으나 영문판에서는 ‘추상 자료구조’와 ‘추상 자료형’의 정의 간에 특별한 구분을 두고 있지는 않는 것 같다. 추상 자료형과 자료구조의 차이 정도만 인식하고 있으면 될 것 같다. ...
추상 자료형이란 # 추상 자료형은(Abstract Data Type, ADT)는 자료의 형태와 그와 관계된 연산을 수학적으로만 정의한 것이다. 해당 자료형이 내부적으로 어떤 방식으로 구현되는지는 관심이 없다. ‘형’과 ‘Type’, ‘자료’와 ‘Data’가 동일한 뜻인 것을 가끔 인지하지 못할 때가 있다. 정수는 추상 자료형(ADT)이다. …, -2, -1, 0, 1, 2, …의 값으로 정의되며, 연산은 더하기, 빼기, 곱하기, 나누기가 가능하고, 대소 비교 등도 가능하다. 추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다. ...
배열은 연속적인 자료의 나열이다. 배열 내에는 동일한 형(type)의 자료가 나열되어야 한다. 보통의 프로그래밍 언어에서 인덱스는 0부터 시작한다. 루아는 특이하게 1부터 시작한다. C에서는 선언 시에 배열로 사용될 메모리 주소의 범위를 정적으로 할당한다. 반면 Javascript에서의 배열은 동적으로 할당되며, 메모리 주소의 연속일 뿐인 C와 다르게 다양한 메서드를 포함하고 있는 객체로 구현되어 있다. 내부 작동은 브라우저의 엔진마다 다를 수 있다고 한다. const arr = [1, 2, 3]; arr[1]; > 2 arr["1"]; > 2 인덱스는 특이하게 “1"로도 1로도 접근 가능한데 내부적으로 toString() 메소드를 호출하기 때문이라고 한다. ...
자료구조란 추상 자료형을 구현한 것. 자료(데이터)의 모임, 자료간의 관계, 자료의 입출력 방식. 왜 자료구조를 알아야 할까 # 주어진 문제를 해결할 때 자료구조를 선택하고 나면 어떤 알고리즘을 사용할지 명확해진다. 구현의 난이도, 결과물의 성능이 자료구조에 크게 의존한다. 자료구조의 5가지 필수 구성 요소 # 참조 링크 어떻게 접근 할 것인가. 어떻게 입력 할 것인가. 어떻게 삭제 할 것인가. 어떻게 탐색 할 것인가. 어떻게 정렬 할 것인가. 자료구조 선택 방법 # 자료구조의 분류 # 자료구조는 추상적인 구조인지, 자료간의 관계가 선형(1:1)적인지 비선형적인지 등으로 분류 되어진다. ...