CS 기초를 위해 자료구조를 다시 처음부터 공부하며 학습한 내용을 정리해 갈 예정이다.
카테고리는 TIL이지만, 사실 한 주 전에 공부한 내용을 미뤄두다가 겨우 정리한 글이다.
이후 추가로 학습한 내용이나 구현, 연산자는 보충되거나 별도로 분리되어 작성될 예정.
배열 (Array)
순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조
- 원소 : 배열에 저장된 객체
- 인덱스 : 각 원소에 순서대로 지정된 번호
* 메모리 주소가 연속될 것을 요구하므로 배열의 크기를 늘릴 수 없으며, 생성 시 배열의 크기를 지정해 주어야 한다.
Python의 경우 리스트(list)나 튜플(tuple)과 같은 데이터 컨테이너 자료형으로 구현 가능하다.
- 리스트(list) : 원소 변경이 가능한(mutable) 객체
- 튜플(tuple) : 원소 변경이 불가능한(immutable) 객체
스택 (Stack)
데이터를 임시 저장할 때 사용하는 자료구조로, 후입선출(Last In First Out = LIFO) 방식이다.
* 용어 정리
- Push : 스택에 데이터를 넣는 작업
- Pop : 스택에서 데이터를 꺼내는 작업
- Top : Push와 Pop이 발생하는 스택의 윗부분
- Bottom : 스택의 가장 밑 부분
큐 (Queue)
데이터를 임시 저장할 때 사용하는 자료구조로, 선입선출(First In First Out = FIFO) 방식이다.
* 용어 정리
- Enqueue : 큐에 데이터를 추가하는 작업
- Dequeue : 큐에서 데이터를 꺼내는 작업
- Front : 데이터를 꺼내는 쪽
- Rear : 데이터를 넣는 쪽
덱 (Deque)
큐와 스택이 합쳐진 형태로, 양 끝에서 데이터를 모두 삽입·삭제할 수 있는 자료구조이다.
* 2개의 포인터를 사용하여 데이터가 존재하는 양 끝의 위치를 파악한다.
덱의 종류
- Scroll (입력 제한 덱) : 입력은 한쪽으로 제한되며, 출력은 양쪽 모두 가능하다.
- Shelf (출력 제한 덱) : 입력은 양쪽 모두 가능하며, 출력은 한쪽으로 제한된다.