Saturday, September 21, 2024

Disadvantage of Linear / Static Queue and Its Solution

Disadvantage of Linear/Static Queue- 

लीनियर/स्टेटिक क्यू की हानियाँ:-

We know that when any element is inserted in linear queue then rear will be increased by 1. Let, assume after insertion operations rear is shifted to last position(N-1) in queue. It means, now queue is full. Now if a new element is inserted then overflow condition will occur. Now, if we delete some elements from queue then front will be increased by 1. After deletion memory space occupied by those elements will be blank and it should be reused by other new element. But it cannot possible because rear is still pointing to the last position(N-1). Hence, we cannot able to reuse free memory space present in linear/static queue and memory is not effectively used. To solve this problem following two types are used.

हमे ज्ञात है कि जब लीनियर क्यू में किसी नए एलिमेंट को इन्सर्ट किया जाता है तब रियर को एक से बढाया जाता है। माना कि कई इंसर्शन ऑपरेशन के पश्चात् रियर अभी लास्ट पोजीशन(N-1) पर है अर्थात क्यू फुल है और अब इंसर्शन ऑपरेशन करने पर ओवरफ्लो कंडीशन उत्पन्न होती है। अब यदि क्यू से कुछ एलिमेंट को डिलीट किया जाता है तब फ्रंट को एक से बढाया जाता है। कुछ डिलीशन ऑपरेशन के पश्चात् क्यू में जगह रिक्त हो जाती है जिसका प्रयोग नए एलिमेंट के इंसर्शन में किया जाना चाहिए परन्तु यह संभव नहीं हो पता है क्यूंकि रियर अभी भी लास्ट पोजीशन(N-1) पर है। अत: लीनियर क्यू में मेमोरी का प्रभावी उपयोग नहीं हो पाता है। इस समस्या को निम्न दो तरीको से हल किया जा सकता है- 


1. To convert static/linear queue into physical queue:- 

लीनियर/स्टेटिक क्यू को फिजिकल क्यू में बदल कर :-

In Linear Queue, Let us assume rear=N-1, it means rear is pointing to last position of Queue and front is always pointing to first position (front=0) of Queue, It wont be increased by 1. Now, For each deletion operation, we need to shift all the remaining elements one-by-one towards first position due to which last position will automatically left blank and we can insert new element on it. It is called Physical Queue and It utilizes memory space. In daily life, a queue of students or customers at counter where students and customers are shifting towards the counter.

लीनियर क्यू में, माना कि rear=N-1 अर्थात रियर लास्ट पोजीशन पर है एवं फ्रंट सदैव फर्स्ट पोजीशन(front=0) पर रहेगा, इसे बढाया नहीं जायेगा। अब प्रत्येक डिलीशन ऑपरेशन के लिए, सभी शेष एलिमेंट को एक-एक करके ,एक पोजीशन आगे की ओर शिफ्ट किया जाता है जिससे लास्ट पोजीशन स्वत : ही रिक्त हो जाती है एवं नए एलिमेंट का इंसर्शन रियर पर हो जाता है,  इसे फिजिकल क्यू कहा जाता है। इसमें मेमोरी का प्रभावी उपयोग होता है। दैनिक जीवन में - काउंटर पर स्टूडेंट्स या कस्टमर की कतार जिसमे काउंटर आगे नहीं बढ़ता है स्टूडेंट्स या कस्टमर ,उसकी ओर बढ़ते है। 


Physical queue is an effectively technique for small queue,but if a queue has large number of elements then a single deletion operation of an element requires many swapping process for shifting all other elements of physical queue which is a time consuming process and CPU spends more time in swapping values. Due to which execution of program is getting slower. So, we use circular queue for large elements queue instead of physical queue.

फिजिकल क्यू छोटे क्यू के लिए एक सफल युक्ति है परन्तु यदि किसी क्यू में एलिमेंट की संख्या अधिक हो तब एक डिलीशन ऑपरेशन के लिए कई स्वैपिंग ऑपरेशन करने की आवश्यकता होगी, जो कि अधिक समय खर्च करने वाली प्रक्रिया है एवं इसमें सी.पी.यू का अत्यधिक समय, एलिमेंट के डिलीशन के स्थान पर, कई एलिमेंट की स्वैपिंग में खर्च होता है जिससे प्रोग्राम का एक्सीक्यूशन धीमा हो जाता है अत: अधिक एलिमेंट वाले क्यू के लिए फिजिकल क्यू के स्थान पर सर्कुलर क्यू का प्रयोग किया जाता है।          


2. To convert static/linear queue into circular queue

लीनियर/स्टेटिक क्यू को सर्कुलर क्यू में बदल कर


No comments:

Post a Comment

Priority Queue

Priority queue:-  It is a special type of queue which stores group of elements. Each element has a priority number associated with it. Prior...