정의와 성질 저번에 정리한 스택이랑 이번에 배울 큐랑 비슷한게 많다. 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First In First Out)이라고 하기도 한다. 큐의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤의 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서 추가되는 곳을 rear, 즉 뒤 쪽이라고..

1. 정의와 성질 자료구조에서의 스택은 한쪽 끝에서 원소를 넣거나 뺄 수 있는 자료 구조이다. 스택은 구조적으로 먼저 들어간 원소가 제일 마지막에 나오는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 한다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다. 스택의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 상단의 원소 확인 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 2. 기능과 구현 const int MX = 1000005; int dat[MX]; int pos = 0;..

연결 리스트가 무엇인지 알아보고, 구현도 해볼 것이다. 1. 정의와 성질 연결 리스트 정의 연결 리스트란 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 배열과는 다르게 이곳 저곳 흩어져있다. 연결 리스트 성질 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요 - 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) - 배열과 비교앴을 때 큰 차이가 있는 성질이고, 연결 리스트의 큰 장점이다. 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 - 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할..

지금까지 프로그래밍 언어의 관점에서 배열을 다뤘었기 때문에 자료구조로써의 배열을 익힐 필요가 있어 공부하였다. 1. 정의와 성질 배열의 정의 배열이란 메모리 상에 원소를 연속하게 배치한 자료구조를 말한다. C++에서는 이미 선언된 배열의 길이를 변경하는게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 생각하겠다. 배열의 성질 1. O(1)에 K번째 원소를 확인/변경 가능 - 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 - 다른 자료구조와는 다르게 추가적으로 소모되는 메모리 양이 거의 없슴 3. Cache hit rate가 높음 - 메모리 상에 데이터들이 붙어있으니까 Cache hit rate가 ..