배열(Array)
- 가장 기본적인 순차적(sequential) 자료구조
- index를 이용하여 배열에 있는 특정 데이터을 상수 시간 O(1) 내에 읽고 쓸 수 있다.
- (파이썬 기준) 정수 데이터만을 지니는 A라는 array가 있다고 할 때 A[2]의 값을 알고 싶으면 RAM(메모리)에 저장된 주소를 알면 된다. 그렇다면 A[0]의 주소를 기준으로 2X4Byte(정수의 크기)를 더해주면 그 주소를 알 수 있다. 이 과정이 모두 상수시간내의 연산이기 때문에 연산 시간이 O(1)이 된다.
- 파이썬의 경우, A[3] = 10이라고 선언한다면 이는 실제로 A라는 리스트에 3 index에 10이라는 값을 넣는 것이 아닌 A[3]가 메모리에 저장된 10이라는 객체의 주소를 가르키게 하는 것이다. 이후 A[3] = 14 라고 선언한다면 A[3]이 14라는 객체의 주소를 가르키는 것이다.
- dynamic array : 크기가 바뀜에 따라 그 용량을 자동으로 조절하는 배열이다. Python의 List가 dynamic array이다.
스택(Stack)
- 제한된 접근(삽입, 삭제)만 허용
- 데이터가 메모리에 연속적으로 저장됨
- LIFO (Last In First Out) : 가장 마지막에 삽입된 객체가 가장 먼저 삭제. 즉 배열의 끝에서만 접근이 일어남
- 삽입: push / 삭제: pop / 마지막(최상위) 객체 반환 : top / 길이: len
큐(Queue)
- 제한된 접근(삽입, 삭제)만 허용
- 데이터가 메모리에 연속적으로 저장됨
- FIFO (First In First Out) : 먼저 삽입된 객체가 가장 먼저 삭제
- 삽입: enqueue / 삭제: dequeue
- 두 개의 포인터(first/last)로 구현
- 배열을 이용하여 구현된 선형 queue 의 경우 enqueue와 dequeue를 할수록 앞쪽은 비워지고 뒤쪽은 채워져 할당할 메모리가 계속 늘어나는 문제가 발생하며 이를 해결하기 위해 원형 큐를 사용한다.
- 원형 queue의 경우 MAX_SIZE를 지정한 후 마지막 데이터가 queue의 끝에 닿은 상태로 새로운 데이터가 들어오면 해당 데이터를 queue의 맨 앞으로 보내는 방식으로 구현된다.
덱(Deque) (Double-ended Queue)
- 제한된 접근(삽입, 삭제)만 허용
- 데이터가 메모리에 연속적으로 저장
- 양방향으로 삽입과 삭제가 가능
우보천리