6.3formula-based representation front rear Q Maxsize -1 ueue ABC 0j[1][2] the queue size =rear+ an empty queue has rear--1
6.3formula-based representation the queue size =rear+1; an empty queue has rear=-1 A B C …… Queue: front rear Maxsize-1 [0] [1] [2] [n-1]
6.3formula-based representation To add an element rear-rear+l; queuerear=x; To delete an element: two methods 1)frontfront+1; O( 2)shift the queue one position left. O(n)
6.3formula-based representation To add an element: rear=rear+1; queue[rear]=x; To delete an element: two methods: 1) front=front+1; O(1) 2) shift the queue one position left. O(n)
6.3formula-based representation Figure 6.3 front rear front rear front rear ABC B BIC D
6.3formula-based representation Figure 6.3 front rear front rear front rear A B C … B C … B C D …
6.3formula-based representation Figure 6.4 front rear ABC p Free space
6.3formula-based representation Figure 6.4 … A B C D E Front rear Free space
6.3formula-based representation as the figure6. 4 shows each deletion causes front to move right by 1 So there will be times when rearmaxsize-1 and front>o At these times the queue is not full, there is space at the left end of it
6.3formula-based representation As the figure6.4 shows ,each deletion causes front to move right by 1 So,there will be times when rear=maxsize-1 and front>0 At these times the queue is not full,there is space at the left end of it