자료구조12 자료구조(7) 덱 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조! 덱은 양방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는, 혹은 스택과 큐를 조합한 형태의 자료구조로 이해되고 있다. 덱도 배열을 기반으로, 그리고 연결 리스트 기반으로도 구현이 가능하다. 하지만 우리는 덱의 구현에 가장 어울린다고 알려진 "양방향 연결 리스트"를 기반으로 덱을 구현할 것이다. 그 이유는 다음 함수와 관련이 있다. "Data DQRemoveLast(Deque * pdeq); // 꼬리에 위치한 데이터(노드) 삭제 위 함수는 꼬리에 위치한 노드를 삭제하는 함수인데, 노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방.. 2022. 3. 16. 자료구조(6) 큐 큐는 "선입선출" 구조의 자료구조이다. 때문에 FIFO(First-in , First-out) 구조의 자료구조라 불린다. 큐 역시 스택과 마찬가지로 배열을 기반으로, 그리고 연결 리스트를 기반으로도 구현이 가능하다. 처음 큐를 접하면 다음과 같이 생각하는 것이 보통이다. "스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같다" 하지만 큐의 구현모델을 알게되면 이보다는 큰 차이가 있다고 느낄 것이다. 큐의 배열 기반 구현 F를 참조하여 dequeue 연산을 하고, R을 참조하여 enqueue연산을 한다 (F=머리, R=꼬리) "뒤로 넣고 앞으로 빼는 자료구조" // 이것만 외워도 큐의 원리가 쉽게이해된다. 잘못된 .. 2022. 3. 16. 자료구조(5) 스택 스택은 나중에 들어간것이 먼저 나오는 구조다 보니 "후입선출" 방식의 자료구조라고도 불리고 LIFO(Last-in, First-out)구조의 자료구조라고도 불린다. 스택자체는 어려운것 아니나, "스택의 활용", "스택 기반의 알고리즘"과 관련된 전통적인 예가 하나 있는데, 이것이 의외로 간단하지 않다. 오히려 스택을 공부하는 것보다 이것을 경험하는데 더 많은 노력이 필요할것이다. 스택은 배열을 이용해서도 구현이 가능하고, 또 연결 리스트를 이용해서도 구현이 가능하다. 사실 배열구조도 자료구조이다. 그럼에도 불구하고 리스트의 구현의 도구로 사용하지 않는가? 마찬가지로 연결리스트도 하나의 자료구조이만 다른 자료구조의 구현에 사용되는 중요한 도구이기도 하다. 어찌 보면 연결리스트는 다른 자료구조의 구현에 사용.. 2022. 3. 16. 자료구조(4) 양방향 연결리스트(이중연결리스트) + 머리추가 이름이 의미하듯 노드가 양쪽 방향으로 연결된 구조의 리스트이다. 즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드가 왼쪽 노드를 가리키는 구조다. 양방향 연결리스트가 복잡해서 구현하기 부담스러울꺼같지만, 이는 그림상에서 느껴지는 복잡함 때문에 발생 오해이다. 실제로 코드를 비교해보면 상대적으로 더 복잡하지 않음을 알 수 있다. 양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다. 포인터 변수 before의 용도를 기억하는가? 이는 리스트가 한쪽 방향으로만 조회가 가능하기 때문에 유지해야 하는, 삭제의 과정을 위해 유지해야 하는 멤버이다. 하지만 양방향 연결리스트는 양방향으로 얼마든지 조회가 가능.. 2022. 3. 16. 자료구조(3) 원형 연결리스트 + tail로 머리추가, 꼬리추가 (더미 x) 바로 전에 배운 더미, 머리 연결 리스트의 마지막 노드는 Null을 가르켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 "원형 연결 리스트"가 된다. 원본 : (head) 2-3-4-5 (tail) 머리추가 : head->1-2-3-4-5 // 1->2->3->4->5 꼬리추가 : head->2-3-4-5-1 tail // 1->2->3->4->5 // 꼬리부터 1,2,3,4,5로 볼수있다 "두 연결 리스트 모두 5가 저장된 노드는 1이 저장된 새 노드를 가리키고, 1이 저장된 새 노드는 2가 저장된 노드를 가르킨다" 위의 원형 연결 리스트의 특성 때문에 머리와 꼬리의 구분이 없다고 이야기한다. 실제로 두 연결 리스트의(머리,꼬리) 유일한 차이점은 포인터 변수 head가 무엇을 .. 2022. 3. 16. 이전 1 2 3 다음
