자료구조
-
원형 큐(Circular Queue)프로그래밍 기초/자료구조 2021. 1. 8. 11:56
스택 순차 자료구조를 사용한 큐는 데이터를 인출할 때마다 모든 데이터를 이동시켜야 하는 오버헤드가 발생한다. 이를 방지하기 위한 자료구조가 원형 큐이다. 원형 큐는 기본적으로 시작 지점과 끝 지점을 연결해 계속해서 이어질 수 있도록 만든 것으로 논리적 구조는 다음과 같다. 이때 데이터를 삽입하는 위치와 인출하는 위치는 다음과 같다. 삽인 위치 front = (front + 1) % n 삭제 위치 rear = (rear + 1) % n 큐 구현 준비 큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. 구현에 필요한 메서드 및 속성은 다음과 같다. 생성자 CircularQueue() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 CircularQueue(Circular..
-
자료구조...57일지 2021. 1. 7. 12:11
원형 큐 기능 메서드 구현 CircularQueue.cpp /// /// CircularQueue에 지정한 값이 존재하는지 확인한다. /// /// CircularQueue에서 찾을 값 /// 값의 존재 여부 bool CircularQueue::Contains(int value) { for (size_t i = 0, j = m_rear; i < m_count; i++) { if (m_items[j] == value) { return true; } j = (j + 1) % (m_capacity + 1); } return false; } 더보기 참고문헌 만들면서 배우는 인터프리터하야시 하루히코 상세보기
-
자료구조...55일지 2020. 12. 30. 11:51
원형 큐 삽입 메서드 구현 CircularQueue.cpp /// /// CircularQueue의 끝 부분에 값을 추가한다. /// /// 추가할 값 void CircularQueue::Enqueue(int value) { if (IsNeedToResize()) { Resize(); } m_items[m_front++] = value; m_count++; m_front = m_front % (m_capacity + 1); } /// /// CircularQueue에 count만큼의 값을 삽입할 수 있는지 확인한다. /// /// 삽입 가능 여부 bool CircularQueue::IsNeedToResize() { return m_capacity < m_count + 1; } /// /// 데이터 삽입 ..
-
자료구조...54일지 2020. 12. 29. 11:55
원형 큐 구현 준비 큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. 구현에 필요한 메서드 및 속성은 다음과 같다. 생성자 Queue() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 Queue(Queue&) 다른 Queue 데이터로 인스턴스 생성 Queue(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성 속성 Capacity 저장될 수 있는 총 크기 Count Queue에 포함된 데이터의 개수 Item[int] 저장된 데이터의 접근 및 설정 메서드 Enqueue(data) Queue의 끝 부분에 데이터를 저장 Peek() Queue의 시작 부분의 데이터를 제거하지 않고 반환 Dequeue() Stack의 시작 부분의 데이터를 제거하고 반환 Clear(..
-
큐(Queue)프로그래밍 기초/자료구조 2020. 12. 18. 12:34
스택 스택과는 달리 하나의 입구와 하나의 출구를 가진 자료구조로 선입선출(First In Fist Out) 구조를 가진다. - 삽입 연산(EnQueue) 큐에 데이터를 삽입하고 삽입된 데이터를 마지막으로 표시한다. * 원본 데이터 인덱스 0 : FIRST 1 2 3 : REAR 4 데이터 10 20 30 40 인덱스 0 : FIRST 1 2 3 4 : REAR 데이터 10 20 30 40 50 - 인출 연산(DeQueue) 첫 데이터를 인출하고 해당 데이터 다음에 존재하는 데이터를 최상단으로 표시한다. 인덱스 0 1 : FIRST 2 3 4 : REAR 데이터 10 20 30 40 50 ┗→ 10 큐 구현 준비 큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다. 구현..
-
자료구조...52일지 2020. 12. 16. 10:58
연결 리스트 큐 삽입 메서드 구현 LinkedListQueue.cpp /// /// LinkedListQueue의 끝 부분에 값을 추가한다. /// /// 추가할 값 void LinkedListQueue::Enqueue(int value) { m_items.Add(value); } 연결 리스트 큐 인출 메서드 구현 LinkedListQueue.cpp /// /// LinkedListQueue의 시작 부분을 제거하지 않고 반환한다. /// /// 시작 부분에 있는 값 int LinkedListQueue::Peek() { if (m_items.Count()