[Python] 큐의 구조

큐

 - 선입 선출 ( FirstInFirstOut - FIFO )

 

 공백 큐 생성createQueue()

-1 || front = rear= -1

0 ||

1 ||

 

원소 a 삽입 enQueue(A);

-1 || front = -1

0 || A가 삽입됨 || rear

1 ||

 

원소 B삽입 : enQueue(B)

-1 || front = -1

0 || A가 삽입됨 ||

1 || B가 삽입됨 || rear

front = -1

 

선형 큐

- 문제점

  잘못된 포화상태 인식

선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞 부분에 활용할 수 있는 공간이 있음에도 불구하고, rear = n-1 인 상태 즉, 포화상태로 인식 더이상 삽입을 수행하지 않는다.

<포화상태로 잘못 인식>

0 ||

1 ||

2 || front

3 || rear

 해결방법

매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킴

원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어짐

<큐의 원소들을 이동>

0 || rear

1 ||

2 ||

3 ||

 ㄴ 공백부분이 front 가온다.

 

초기 공백 상태 

front = rear = 0 

                       왜 -1에서 시작안하죠? 어차피 원형으로 빙둘러서 하기떄문에

 

 원형의 Q라고 생각해주세요.

1) enQueue(C); 

0 ||

1 || front

2 || B

3 || C || rear

2) enQueue(D); 

0 || D || rear

1 || front

2 || B

3 || C || rear