06.큐

목차

1. 2. 10, 20, 30, 40, 50을 큐에 넣었다고 가정하고 3개의 항목을 삭제하였다. 남아 있는 항목은?
2. 4. 크기가 8인 원형 큐에서 front가 3이고, rear가 5라고 하면 현재 원형 큐에 저장된 요소들의 개수는?
3. 6. 큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 되는가?
4. 8. 연결 리스트로 구현된 큐에서 공백 상태는?
5. 10. 크기가 10이고 front가 3, rear가 9인 원형 큐에서 새로운 항목이 삽입되었을 경우, 배열의 어떤 인덱스에 들어가는 가?
6. 12. 크기가 6인 원형 큐 A에 다음과 같이 삽입과 삭제가 되풀이되었을 경우에 각 단계에서의 원형 큐의 내용(1차원 배열의 내용, front와 rear의 값)을 나타내어라.
7. 14. 원형 큐에서 front와 rear의 초기값이 0이 아니고 만약 1로 시작하였다면 이것이 문제를 일으키는가?
8. 16. 만약 연결된 큐에 15번 문제와 같은 구조체를 저장하려고 하면 소스의 어떤 부분들이 변경되어야 하는가?
9. 18. 17번 문제의 소스에서 중복된 문장이 존재한다. 중복된 문장을 제거하고 다시 작성해보라.
10. 20. 연결 리스트로 구현된 큐에 존재하는 요소의 개수를 반환하는 연산 get_count를 추가하여 보라.
11. 22. 원형 큐에서는 공백 상태와 포화 상태를 구분하기 위하여 필수적으로 하나의 빈 공간이 필요하다. 이것은 하나의 변수를 큐에 추가함으로써 모든 배열 공간을 사용할 수도 있다. last0p라고 하는 변수는 가장 최근에 큐에 행해진 연산을 기억하고 있다. 만약 최근에 행해진 연산이 삽입 연산이었다면 큐는 절대로 공백 상태가 아닐 것이다. 마찬가지로 만약 최근에 행해진 연산이 삭제 연산이었다면 절대로 포화 상태는 아닐 것이다. 따라서 last0p 변수는 front == rear일 때 공백 상태와 포화 상태를 구분하는데 이용될 수 있다. 이러한 추측이 맞게 동작되는지를 프로그램으로 구현하여 테스트하라.
12. 24. 본문에는 단순 연결 리스트를 이용하여 연결된 큐를 구현하였다. 4장 리스트에서 학습하였던 원형 연결리스트를 이용하여 연결된 큐를 구현해보라. 삽입과 삭제 연산만 작성하라.

본문내용

2. 10, 20, 30, 40, 50을 큐에 넣었다고 가정하고 3개의 항목을 삭제하였다. 남아 있는 항목은?
큐는 선입선출 방식으로 실행되기 때문에 가장 먼저 들어온 10, 20, 30의 데이터가 삭제된다. 따라서 남아있는 항목은 40과 50이다.

4. 크기가 8인 원형 큐에서 front가 3이고, rear가 5라고 하면 현재 원형 큐에 저장된 요소들의 개수는?
rear가 가리키는 자리에는 데이터가 존재하고, front가 가리키는 자리에는 데이터가 존재하지 않으므로 현재 원형 큐에는 5 - 3 = 2 즉, 2개의 요소가 저장되어있다.

6. 큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 되는가?
큐에 항목들을 삽입하거나 삭제하는 연산의 수는 반복적으로 연산되는 것이 없으므로 상수로 나타난다. 따라서 시간 복잡도를 빅오로 표시하면 O(1) 이다.

8. 연결 리스트로 구현된 큐에서 공백 상태는?
(1) front == NULL && rear == NULL
2개의 포인터 front와 rear가 가리키는 값이 아무것도 없으면 즉, NULL일 경우 큐에 어떠한 요소가 없는 공백 상태로 인지한다.

참고자료

· 없음