* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 큐(queue)는 말 그대로 대기열이다. 놀이기구 줄을 설 때, 나중에 온 사람이 먼저 탑승하면 그건 새치기가 된다. 따라서, 대기열은 먼저 온 사람이 먼저 탑승하고, 나중에 온 사람은 나중에 탑승하는 선입선출(FIFO, First in First Out) 구조이다. LIFO 구조였던 스택과는 대비된다. 큐의 ADT 스택에는 push, pop, peek의 기능이 핵심적이었다. 큐는 데이터를 넣는 부분과 빼는 부분의 위치가 다르기 때문에, 아래와 같은 두 개의 연산이 핵심적이다. enqueue: 큐에 데이터를 넣음 dequeue: 큐에서 데이터를 뺌 이를 이용하여, ADT에 아래 5가지를 구현하자. 1...

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 드디어 길고 길었던 연결 리스트가 무려 6개의 포스팅 만에 끝났다!! 이제 6강인 스택에 대해 다뤄 보자. 스택은 지난 번 코딩 연습 때 백준에서 다룬 바 있다. https://cascade.tistory.com/61 스택(stack)구조란? (백준 9012번, 10828번) 스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. cascade.tistory.com 스택의 정의는 지난 번 포스팅을 참고하도록. LIFO 구조라는 건 기억하고 가고, 어떤 기능을 구..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 리스트 그림그리기 힘들군요 앞서 4강에서 구현한 단순 연결 리스트를 변형하여 원형 연결 리스트를 제작하자. 원형 연결 리스트는 단순 연결 리스트에서 머리에서 가장 먼 노드가 NULL을 가리키는 것이 아니라, 머리에서 가장 가까운 노드를 가리키도록 하여 원형 구조를 이루는 것을 말한다. 새로운 노드 1을 머리에 추가한다고 한다면 아래와 같이 변한다. 새로운 노드 1을 꼬리에 추가한다고 하면 아래와 같이 변한다. 이때, 마지막 노드를 가리키는 포인터 변수는 tail이고, 첫 노드를 가리키는 포인터 변수는 tail->next가 된다. 이렇게 원형으로 연결 리스트를 구현하는 것의 특징은, LNext 함수의 무..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 본 포스팅에서는 교재를 바탕으로 단순 연결 리스트의 ADT를 정의하고, 정렬 기능과 노드 삽입 기능을 구현해 보고자 한다. 정렬 기능의 추가 ADT는 구현 방식과 무관하며 기능만 포함되면 되기 때문에, 앞선 포스팅에서 다루었던 배열로 정의한 리스트(https://cascade.tistory.com/69)를 그대로 가져와 써도 된다. 대신, 정렬 기능만 추가해 보자. 1. 리스트의 생성 : 리스트의 주소 값을 인자로 전달하고 초기화한다. void ListInit(List *plist); 2. 데이터의 저장 : 리스트에 데이터를 저장한다. void LInsert(List * plist, LData data..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 앞선 포스팅에서는 열혈자료구조 3장에서 다루었던 추상 자료형(ADT)과 배열로 정의한 리스트의 구현을 정리하였다. 4강부터는 배열이 아닌, "연결"을 기반으로 한 리스트의 새로운 정의에 대해 다룬다. 리스트를 배열로 정의하는 것의 단점은, 앞선 포스팅의 코드를 보면 알 수 있겠지만 최대 길이가 정해져 있다는 것이다. 즉 정적으로 100개의 메모리를 할당했으므로, 100개가 넘는 자료를 저장할 수 없다. 이에 따라 메모리를 동적으로 구성하여 리스트를 정의해야 한다. 이를 위해, 노드를 연결하여 리스트를 만드는 방식을 사용하자. 노드의 정의 노드(Node)는 데이터를 저장할 수 있으며 다른 노드와 연결이 ..