큐란, 먼저 들어온 데이터가 먼저 나가는, 선입선출, FIFO(First in First out)구조를 가진다. 큐(queue)는, 영어단어인 queue라는 단어의 뜻에서도 이러한 의미를 가지는데, 대기 행렬, 줄이라는 뜻을 가진다. 먼저 줄선 사람이 먼저 나가듯이, queue라는 뜻 자체가 선입선출의 의미를 갖는다고 볼 수 있다. 저번에 스택을 구현할 때는 동적 할당으로 길이를 늘리는 배열처럼 사용하여 데이터를 배열에 순차적으로 입력하면서 처리하면 되었지만, 큐는 그런 방식으로 해결을 볼 수 없었다. 배열을 사용하면, 데이터를 앞에서부터 뒤로 순차적으로 입력하면, pop을 수행할 때마다 데이터가 배열 중간에 위치하게 되는데, 이때 데이터들을 앞으로 한칸씩 복사하면서 값을 갱신하는데, 이 때 배열 내부를..
스택이란, 데이터가 들어가는 부분과 나오는 부분이 같아, LIFO(Last in, First out), 후입선출구조를 이루는 제한적인 접근이 가능한 선형 자료구조이다. 쉽게 말해, 책을 쌓아올리면, 보통은 제일 마지막에 쌓은 책부터 꺼내는 모양과 같다고 말할 수 있겠다. 그러면 스택을 구현해보자. 이번에 스택이 동작시키기 위해 구현할 함수는 총 7가지로, 다음과 같다. 스택을 초기화할 init_stack 데이터를 추가할 push 제일 마지막 데이터를 제거할 pop 데이터가 얼마나 담겨있는지 알아낼 size 스택이 비었는지 체크할 empty 제일 마지막 데이터를 반환할 top 얼마나 할당받았는지 반환할 capacity 먼저 스택 구조체를 먼저 선언해보자. 얼마나 많은 데이터가 들어올지 모르기 때문에 포인터..
앞서 연결리스트를 구현하긴 했지만, 자료구조가 뭔지 정리하지도 않고 일단 구현한거 같아 매우 찜찜했다. 그래서 이번에는 다른 자료구조를 공부하고, 구현하기에 앞서 자료구조가 뭔지부터 공부하고 넘어가보자 한다. 이 글은 여러 블로그와 설명을 보며 공부한 것을 정리한 노트이다. 자료구조란? 자료구조(data structure)의 사전적 정의는 컴퓨터 과학에서 데이터의 효율적인 접근 및 수정을 가능케 하는 자료의 집합을 의미한다. 더 자세히 말하자면, 데이터 간의 논리적으로 정의된 규칙에 의해 구조화되어있으며, 자료에 대한 효율적인 처리를 수행하도록 조직적, 체계적으로 구분한 것을 의미한다. 왜 사용하는가? 사실 이 질문은 이미 자료구조의 정의에서 이미 나와있다. 데이터를 효율적으로 다루기 위해서이다. 예를 ..
연결 리스트란, 하나의 노드가 값과 다음 노드를 가르키는 노드로 이루어진 자료구조이다. 그림으로 정리하면 다음과 같다. 이때, node가 다음 노드만을 가르키기 때문에, 단일 연결 리스트라고 한다. 그런데 우리는 이미 배열(array)이 있는데, 왜 이것을 사용해야 하는지 의문이 들 것이다. 필자도 연결리스트가 "노드로 이루어진 구조이다"라는 것만 어렴풋이 알고 있었을 때 이 생각을 했었다. 그 이유는 생각보다 간단했다. 왜냐하면 배열과 연결리스트는 trade-off 관계이기 때문이다. trade-off란 한 특성이 좋아진다면, 다른 특성이 안좋아지는데, 이 둘의 관계가 이러한 특성을 갖기 때문이다. 배열의 경우, 원소에 접근하는 것은 효율적이지만, 데이터를 추가하거나 삭제하기 위해서는, 그 위치의 요소..
