주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 양방향 연결 리스트, 스택, 큐를 제대로 이해하고 있다면 덱을 이해하는 것은 껌입니다. 덱에 대해 한 줄로 설명하자면 다음과 같습니다. "덱은 데이터를 앞으로도 뒤로도 입력 가능하며, 앞으로도 뒤로도 출력이 가능한 큐 혹은 스택 혹은 두 개 모두와 같다" 스택은 데이터를 앞으로 넣었으면 앞으로 빼야 하는 것이 특징입니다. 반면 큐는 데이터를 앞으로 넣었으면 뒤로 빼야 하는 것이 특징입니다. 그런데 덱은 데이터를 앞으로 넣었으면 앞으로도 뒤로도 뺄 수 있고, 이는 데이터를 뒤에서 넣었을 때도 마찬가지라는 특징을 가지고 있습니다. 덱의..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조입니다. 그리고 '큐잉 이론'이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션'하게 되는데, 이때에도 큐는 중요한 역할을 담당합니다. 따라서 우리도 시뮬레이션이라는 주제를 통해서 큐가 활용되는 형태를 적절한 범위 내에서 확인하고자 합니다. 시뮬레이션을 구현해 보기 위해 이와 관련한 상황을 예로 들겠습니다. 어느 햄버거 가게의 점장은 주문된 음식이 포장돼 나오기를 기다리는 손님들을 위해 대기실을 만들려고 합..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이번에는 연결 리스트를 기반으로 하는 큐를 구현해 보겠습니다. 큐는 데이터를 저장하는 위치와 데이터를 가져오는 위치가 다르다는 특징을 가지고 있습니다. 이를 연결 리스트 기반으로 구현하면, 꼬리로 데이터를 저장하면서, 머리로 데이터를 가져올 것이라는 것을 쉽게 생각해 볼 수 있습니다. 그럼 바로 연결 리스트 기반 큐의 헤더 파일을 정의해 보겠습니다. 앞서 정의했던 큐의 ADT를 바탕으로 직접 헤더 파일을 정의해 보는 것도 좋습니다. //LBQueue.h 헤더 파일로 저장 #ifndef LB_QUEUE_H #define LB_QUEU..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 큐는 스택과 상당히 유사합니다. 유일한 차이점은 먼저 저장한 데이터가 먼저 사용된다는 것입니다. 그래서 배열 기반 큐는 배열 기반 스택을 구현했던 것을 조금 수정하면 구현할 수 있을 것만 같습니다. 하지만 생각보다는 그렇게 간단히 끝나지 않습니다. 다음의 배열을 생각해 보겠습니다. 1 2 3 4 위 배열에는 1, 2, 3, 4의 순서대로 데이터가 입력되었습니다. 여기에서 데이터를 하나 빼보겠습니다. 이 배열이 큐인 경우 먼저 저장된 데이터를 먼저 빼야 하기 때문에 다음과 같이 1이 빠져나옵니다. 2 3 4 여기서부터가 문제입니다. ..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 큐는 앞서 설명한 스택과 함께 언급되고 또 비교되는 자료구조입니다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조입니다. 이것이 스택과 큐의 유일한 차이점입니다. 스택과 마찬가지로 큐의 ADT도 정형화된 편입니다. 큐의 핵심이라고 할 수 있는 두 가지 연산을 소개하겠습니다. enqueue 큐에 데이터를 넣는 연산 dequeue 큐에서 데이터를 꺼내는 연산 스택에서 데이터를 넣고 빼는 연산을 가리켜 각각 push, pop이라고 하는 것처럼, 큐에서 데이터를 넣고 빼는 연산에 대해..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 다음과 같은 후위 표기법의 수식을 계산할 알고리즘을 어떻게 구현할 것인지 고민해 봅니다. 3 2 4 * + 저는 후위 표기법의 계산 방법이 꽤 복잡할 것으로 생각했습니다. 하지만 그렇지 않았습니다. 후위 표기법의 수식을 계산하는 알고리즘은 스택을 이용하면 정말 간단하게 구현할 수 있습니다. 그 알고리즘은 다음과 같습니다. 후위 표기법의 수식에서 데이터를 하나씩 읽어 들인다. 읽어 들인 데이터가 피연산자라면 이를 스택에 저장한다. 읽어 들인 데이터가 연산자라면 스택에서 두 개의 피연산자를 꺼내어 이를 계산한 후, 결과를 스택에 저장한..