क्या स्टैक और कतार (डेक) एडीटी दोनों का उपयोग करके कोई दिलचस्प एल्गोरिदम हैं?

Question

हम अक्सर हमारे एल्गोरिदम में ढेर या कतार का उपयोग करते हैं, लेकिन क्या ऐसे कोई मामले हैं जहां हम दोनों को एल्गोरिदम में एक स्टैक और कतार लागू करने के लिए एक दोगुनी लिंक्ड सूची का उपयोग करते हैं? उदाहरण के लिए, एक चरण में, हम स्टैक, पॉप() 2 आइटम पर 6 आइटम पुश करते हैं, और फिर दोगुनी लिंक्ड सूची की पूंछ से शेष आइटम (4) को हटाते हैं। जो मैं खोज रहा हूं वे अस्पष्ट, रोचक एल्गोरिदम हैं जो इस विधि में कुछ भी लागू करते हैं, या यहां तक ​​कि अजनबी भी। स्यूडोकोड, लिंक और स्पष्टीकरण अच्छा होगा।

Answer 1

Melkman एल्गोरिथ्म एक डबल एंडेड कतार (उर्फ Deque) का उपयोग करता कोने पहले से ही संसाधित के लिए एक वृद्धिशील पतवार स्टोर करने के लिए (रेखीय समय में एक साधारण बहुभुज श्रृंखला के उत्तल पतवार की गणना के लिए) ।

Input: a simple polyline W with n vertices V[i] 

    Put first 3 vertices onto deque D so that: 
    a) 3rd vertex V[2] is at bottom and top of D 
    b) on D they form a counterclockwise (ccw) triangle 

    While there are more polyline vertices of W to process 
    Get the next vertex V[i] 
    { 
     Note that: 
     a) D is the convex hull of already processed vertices 
     b) D[bot] = D[top] = the last vertex added to D 

     // Test if V[i] is inside D (as a polygon) 
     If V[i] is left of D[bot]D[bot+1] and D[top-1]D[top] 
      Skip V[i] and Continue with the next vertex 

     // Get the tangent to the bottom 
     While V[i] is right of D[bot]D[bot+1] 
      Remove D[bot] from the bottom of D 
     Insert V[i] at the bottom of D 

     // Get the tangent to the top 
     While V[i] is right of D[top-1]D[top] 
      Pop D[top] from the top of D 
     Push V[i] onto the top of D 
    } 

    Output: D = the ccw convex hull of W. 

स्रोत: http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

जो मिशेल: Melkman’s Convex Hull Algorithm (पीडीएफ)

Answer 2

इस संरचना को डेक कहा जाता है, यह एक कतार है जहां तत्वों को सिर या पूंछ से जोड़ा या हटाया जा सकता है। 1 पर और देखें।

Answer 3

चौड़ाई पहले खोज (कि आम तौर पर 1 भारित किनारों के साथ एक ग्राफ में कम से कम pathes लगाने के लिए प्रयोग किया जाता है) करने के लिए हम संशोधित कर सकते हैं 0-1 ग्राफ के साथ काम करें (यानी 0 और 1 भार के किनारों वाला ग्राफ)। हम इसे अगली तरह से कर सकते हैं: जब हमने 1-एज का उपयोग किया तो हम पीछे की ओर वर्टेक्स जोड़ते हैं और जब हम 0-एज का उपयोग करते हैं तो हम शुरुआत में वर्टेक्स जोड़ते हैं।

Answer 4

मुझे यकीन नहीं है कि यह योग्य है या नहीं, लेकिन आप स्मृति में फ़िट होने के लिए फ़ाइल के लिए बहुत बड़ी फ़ाइल को क्विकपोर्ट लागू करने के लिए डबल-एंडेड प्राथमिकता कतार का उपयोग कर सकते हैं। विचार यह है कि एक नियमित क्विकॉर्ट में, आप एक पिवट के रूप में एक तत्व चुनते हैं, फिर तत्वों को तीन समूहों में विभाजित करते हैं - पिवट से कम तत्व, पिवट के बराबर तत्व, और पिवट से अधिक तत्व। यदि आप सभी वस्तुओं को एक साथ स्मृति में फिट नहीं कर सकते हैं, तो आप इस समाधान को निम्नानुसार अनुकूलित कर सकते हैं। पिवट के रूप में एक तत्व को चुनने के बजाय, इसके बजाय कुछ बड़ी संख्या में तत्व चुनें (जितना आप राम में फिट कर सकते हैं, कहें) और उन्हें डबल-एंड प्राथमिकता कतार में डालें। फिर, एक समय में शेष तत्वों को स्कैन करें। यदि तत्व डबल-एंडेड प्राथमिकता कतार के सबसे छोटे तत्व से कम है, तो इसे सभी पिवटों से छोटे तत्वों के समूह में रखें। यदि यह प्राथमिकता कतार के सबसे बड़े तत्व से बड़ा है, तो इसे पिवट से अधिक तत्वों के समूह में रखें। अन्यथा, तत्व को डबल-एंडेड प्राथमिकता कतार में डालें और फिर कतार से सबसे छोटा या सबसे बड़ा तत्व निकाल दें और इसे उचित समूह में रखें। एक बार ऐसा करने के बाद, आप तत्वों को तीन टुकड़ों में विभाजित कर देंगे - छोटे तत्वों का एक समूह जिसे बाद में क्रमबद्ध किया जा सकता है, मध्य में तत्वों का एक समूह जो अब पूरी तरह से क्रमबद्ध है (क्योंकि यदि आप उन्हें सभी को अस्वीकार करते हैं डबल-एंडेड प्राथमिकता कतार से उन्हें क्रमबद्ध क्रम में निकाला जाएगा), और मध्य तत्वों से अधिक तत्वों का एक समूह जिसे हल किया जा सकता है।

सामान्य रूप से इस एल्गोरिदम और डबल-एंड प्राथमिकता कतारों के बारे में अधिक जानकारी के लिए, इस विषय पर एक अध्याय में this link पर विचार करें।