सर्कुलर ऐरे के रूप में पंक्तियों को लागू क्यों करें?

Question

क्यूई जैसे फीफो को कार्यान्वित करते समय, मेरे प्रशिक्षक हमेशा हमें एक सर्कुलर सरणी के रूप में प्रतिनिधित्व करने की सलाह देते हैं, न कि नियमित सरणी में। क्यूं कर?

क्या ऐसा इसलिए है क्योंकि बाद में, हम सरणी में कचरा डेटा समाप्त कर देंगे?

Answer 1

यदि आप एक निश्चित संख्या में ऐरे-स्लॉट/तत्वों का उपयोग कर रहे हैं, तो अपने स्लॉट को गोलाकार व्यवस्था में रीसायकल करना आसान है, क्योंकि आपको अपने तत्वों को पुन: व्यवस्थित करने की आवश्यकता नहीं है। जब भी पहली तत्व को ऐरे-लाइक व्यवस्था में हटा दिया जाता है, तो आपको अपने शेष तत्वों को एक स्थिति को आगे ले जाना चाहिए, इसलिए सिर null नहीं है। अपने परिपत्र कतार में, आप बस अपनी पॉइंटर को पहली स्थिति में बढ़ाएं। यह एक अद्यतन पर कम संचालन है और आपको बेहतर प्रदर्शन देता है।

यदि आप असीमित/गतिशील संख्याओं के साथ एक कतार का निर्माण कर रहे हैं, इससे कोई फर्क नहीं पड़ता, क्योंकि आप गतिशील रूप से स्मृति को आवंटित और आवंटित कर सकते हैं।

Answer 2

एक कतार की कल्पना करें जो एक सरणी द्वारा समर्थित है जहां इंडेक्स 0 हमेशा पहला आइटम होता है और सूचकांक n हमेशा अंतिम होता है। कतार से किसी आइटम को निकालने के लिए, सभी इंडेक्स 1 से n को इंडेक्स 1 में इंडेक्स 1 में रखने के लिए आगे स्थानांतरित किया जाना चाहिए। जैसा कि आप कल्पना कर सकते हैं, इस प्रक्रिया में बड़ी कतारों के लिए काफी समय लगेगा और/या कतार पर लगातार संचालन।

एक सर्कुलर बफर के रूप में सरणी का इलाज करके, कतार के सिर को अगले आइटम पर इंगित करते समय एक आइटम को एक असाइनमेंट के रूप में सरल हो जाता है, जो स्पष्ट रूप से अधिक प्रदर्शनकारी होता है।

Answer 3

यह मुख्य रूप से प्रदर्शन और सादगी का विषय है। मानक सरणी में आपको कतार से तत्व चुनने पर हर तत्व को सभी तत्वों को स्थानांतरित करना होगा। परिपत्र सरणी के साथ, आपको केवल वर्तमान सूचक और आकार को अद्यतन करने की आवश्यकता है ... कहीं अधिक कुशल।

Answer 4

मैं आपको एक समानता दूंगा।

सड़क विक्रेताओं पर एक कतार की कल्पना करें जहां लोग लाइन के अंत में शामिल होते हैं और सामने से सेवा प्राप्त करते हैं। जैसे-जैसे प्रत्येक व्यक्ति की सेवा की जाती है, कतार में शेष लोग आगे बढ़ते हैं (आम तौर पर इसे लेने में कितना समय लगता है), और अंत में नए लोग शामिल हो जाते हैं। इस उदाहरण में लोगों को लाइन में शामिल होने में सक्षम बनाने के लिए आगे बढ़ना होगा, अन्यथा कतार का अंत हमेशा विक्रेता से आगे निकल जाएगा। तो इस उदाहरण में सर्वर कतार के सामने रहता है और जो भी आगे या किसी के साथ सौदा करता है।

अब कल्पना करें कि क्या लोग नहीं चले गए थे, लेकिन कतार के सिर की सेवा करने के बाद विक्रेता स्वयं कतार के साथ आगे बढ़े, असल में जहां कतार का सिर है। आखिरकार 100 लोगों की सेवा करने के बाद सर्वर सड़क के नीचे आधा रास्ते है और 500 के बाद सर्वर अगली सड़क आदि में है ... यह कहां रुकता है?

तो सुविधा के लिए विक्रेता एक बड़े सर्किट क्षेत्र को मानचित्र करता है जहां लोग हमेशा कतार के अंत में शामिल हो सकते हैं और वह हमेशा अगले व्यक्ति के पास जाता है, लेकिन कतार एक ही स्थान पर बनी हुई है। वह सिर्फ कतार में लोगों की सेवा करता है। निश्चित रूप से वह केवल कतार में लोगों की सेवा कर सकता है, लेकिन बशर्ते वह इतना बड़ा कर सके तो वह मांग के साथ रह सकता है, और उसे अपने निर्दिष्ट बिक्री क्षेत्र से दूर जाने की जरूरत नहीं है।

इस समरूपता को कंप्यूटर पर वापस लेना ... में पहले उदाहरण के लिए एक कतार प्रबंधक है और आइटमों की सेवा के रूप में यह बफर के साथ आइटम को घुमाता है। दूसरा उदाहरण में प्रोग्राम तब तक चलता है जब तक सरणी = इसके निश्चित आकार (या तो परिभाषित या स्थान द्वारा सीमित) में जोड़ने के लिए कोई और स्मृति नहीं होती है।तीसरे उदाहरण में सर्वर दूसरे की तरह कतार के सिर पर चला जाता है लेकिन सरणी तय होती है और केवल इतनी सारी चीज़ें कतार में शामिल हो सकती हैं, लेकिन उन्हें अभी भी सर्विस फीफो मिल जाएगी।

टीएल; डॉ: संसाधनों का कुशल प्रबंधन।

Answer 5

परिपत्र ऐरे सामान्य सरणी के अलावा कुछ भी नहीं है; केवल पॉइंटर (सामने/पीछे) अंत तक पहुंचने पर इसकी प्रारंभ स्थिति में रीसेट हो जाएगा। यदि यह मामला नहीं है और केवल पॉइंटर आगे बढ़ सकता है तो हमें सरणी तत्वों को शीर्ष पर स्वैप करने की आवश्यकता है।

import java.lang.reflect.Array; 

/** 
* Based on 
* https://www.youtube.com/watch?v=z3R9-DkVtds 
* Data Structure & Alogorithm: Queue using Circular Array by Ripon Datta 
* 
* 1) When front and rear are equal there is no data. 
* 2) For each addition rear get incremented to new (empty) position, and for each removal 
* front get moved right to point to the next available element. 
* 3) Q Size (N - front + rear) % N :where N is total array size allocated 
* 4) Resize the array as part of adding new element and founding front and rear are equal 
* OR size is reached the MAX value. 
* 5) While resizing add the element from front to rear to the new array. 
* 
*/ 
public class QueueUsingCircularArray<T> { 
    T[] array; 
    int front = 0; 
    int rear = 0; 
    int N; 
    Class<T> clazz; 

    public QueueUsingCircularArray(Class<T> clazz, int size) { 
     N = size; 
     this.clazz = clazz; 
     array = (T[]) Array.newInstance(clazz, N); 
    } 

    public int size() { 
     return (N - front + rear) % N; 
    } 

    public void add(T data) { 
     int size = size(); 
     if (size == N - 1) { 
      resize(); 
     } 
     array[rear++] = data; 
     if (rear == N) { 
      rear = 0; 
     } 
    } 

    private void resize() { 
     int size = size(); 
     N = N * 2; 
     T[] newArray = (T[]) Array.newInstance(clazz, N); 
     int i = 0; 
     while (size > 0) { 
      size--; 
      newArray[i++] = array[front++]; 
      if (front == array.length) { 
       front = 0; 
      } 
     } 
     rear = i; 
     front = 0; 
     array = newArray; 
    } 

    public T remove() { 
     if (size() == 0) { 
      return null; 
     } 
     T data = array[front++]; 
     array[front - 1] = null; 
     if (front == N) { 
      front = 0; 
     } 
     return data; 
    } 

    public static void main(String[] args) { 
     QueueUsingCircularArray ca = new QueueUsingCircularArray(Integer.class, 5); 
     ca.add(1); 
     ca.add(2); 
     ca.add(3); 
     ca.remove(); 
     ca.add(4); 
     ca.add(5); 
     ca.add(55); //RESIZE 
     ca.remove(); 
     ca.remove(); 
     ca.add(6); 
     ca.add(7); 
     ca.add(8); 
     ca.add(9); 
     ca.add(10); 
    } 
}