순환 큐에 제거하고 삽입

Question

대학에서 교수는 원형 큐를 구현하는 알고리즘을 고안해달라고 요청했습니다. 우리는 'remove()'및 'insert()'함수에 대한 알고리즘을 작성해야합니다. 이것은 내가 생각했던 몇 시간 후에 생각해 냈다.

Declarations: q = circular queue structure that contains 3 elements 
       --> x[MAX] = array of MAX integers 
       --> rear = logical pointer used for inserting elements at that particular index 
       --> front = logical pointer used for deleting elements at that particular index 
Predefined functions: 
       --> incr (int y) : special function to set y to 0 once it contains MAX else do y++ 
       --> decr (int y) : special function to set y to MAX if it contains 0 else do y-- 

Preconditions : At the initial time of defining the structure set rear and front both at 0 

Algorithm REMOVE(q): Returns an int 
1. set a <- q.x[q.front] 
2. incr (q.front) 
3. if q.front >= q.rear 
    1. decr (q.front) 
    2. print "Queue Empty" 
    else 
    1. return a 

Algorithm INSERT(q,a) : Returns nothing 
1. incr (q.rear) 
2. if q.rear = q.front 
    1. decr (q.rear) 
    2. print "Queue Full" 
    else 
    1. set q.x[q.rear] <- a 

이 알고리즘은 'front'가 결코 'rear'를 추월하지 않는다는 사실을 사용합니다. 따라서 'front'가 증가하면 'front = rear'는 대기열이 비어 있음을 의미합니다. 그리고 'rear = front'가 queue가 가득 찼다는 것을 의미한다면 'rear'가 증가 할 때.

그러나 내 교수에게 이것을 보여 주었을 때 그는 이것이 해결책이 아니라고 말했습니다.

이 논리가 올바르지 않습니까? 그렇다면이 알고리즘의 결함은 무엇입니까? 또한 가능하면 개선을 제안하십시오.

(PS :이 나 자신을 구현하려는 때문에이 솔루션을 봤하지 않은 이유입니다.) 대기열의 초기화 후 첫 번째 작업이 REMOVE 요청하는 경우

Answer 1

당신의 설치가 실패합니다. 그 이유는 먼저 앞 인덱스를 증가시킨 다음 큐가 비어 있는지 또는 가득 찼는지를 검색하기 위해 뒷 인덱스와 같은지 여부를 확인하기 때문입니다. 그러나 초기화 후에 대기열이 비어있는 동안 두 색인은 이미 동일합니다.