टीएल;डीआर

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

तुम एक छोटा कैफ़े चलाते हो, दो ट्रे के साथ। नई कप इन ट्रे पर आती हैं। तुम हमेशा उस ढेर के ऊपर कप रखते हो। जब ग्राहक माँगे, तुम आउट ट्रे से परोसते हो, जो भी सिर्फ ऊपर से लेने देती है। जब आउट ट्रे खाली हो, तुम इन ट्रे की हर कप को एक-एक करके आउट पर उलट देते हो। जो कप सबसे पहले आई थी, अब आउट के ऊपर बैठी है, तैयार। यही है दो स्टैक से बनी कतार।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली "स्टैक से कतार" समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३, समस्या ३.४।

१. रोज़मर्रा की उपमा

दो ट्रे; हर एक अकेले स्टैक की तरह चलती है (उसी ट्रे पर अंतिम अंदर, पहले बाहर):

  • इन ट्रे (stackNewest) नई पहुँच रखती है। इनक्यू हमेशा यहीं पुश है। सबसे नई कप ऊपर।
  • आउट ट्रे (stackOldest) फाइफो क्रम में परोसने लायक कप रखती है। डीक्यू और पीक हमेशा यहीं, जब शिफ्ट से भरी हो।
  • शिफ्ट: तभी जब आउट खाली हो और परोसना हो। इन से सब निकालकर आउट पर डालो। क्रम ऐसे उल्टता है कि पहली आई कप पहली बाहर जाए।

आउट में कप बची हों तो शिफ्ट मत करो। यही आलसी चाल औसत लागत सस्ती रखती है।

२. समस्या सादे शब्दों में

लक्ष्य: सिर्फ दो स्टैक भंडार से कतार लागू करो जिसमें इनक्यू (ऐड), डीक्यू (रिमूव) और पीक हों। नीचे कोई लाइब्रेरी Queue नहीं।

कतार का वादा: पहले अंदर, पहले बाहर। अगर 1, फिर 2, फिर 3 जोड़ो, पहला रिमूव 1 लौटाए।

स्टैक से जो इस्तेमाल कर सकते हो: पुश, पॉप, पीक, isEmpty (या साइज़)। जावा का Stack या सिर्फ स्टैक की तरह इस्तेमाल Deque ठीक।

MyQueue पर संक्रियाएँ:

विधि अर्थ
add(x) / enqueue(x) कतार के पीछे x रखना
remove() / dequeue() सामने वाला निकालकर लौटाना
peek() बिना निकाले सामने देखना
isEmpty() / size() खाली या गिनती (वैकल्पिक, काम की)

उदाहरण:

क्रम परिणाम
add(1), add(2), add(3), remove() 1 लौटता है; कतार में 2, 3
फिर peek() 2 लौटता है
फिर remove(), remove() पहले 2, फिर 3
खाली पर remove() अनिर्धारित / अपवाद (नीति चुनो और बोलो)

कोड से पहले साफ करो:

  • खाली पर डीक्यू? फेंको, या संतरी मान? इंटरव्यू में बोल दो तो दोनों चलते हैं।
  • सिर्फ पूर्णांक, या जेनेरिक? स्पष्टता के लिए int से शुरू; जेनेरिक बाद में छोटी लपेट।
  • दोनों स्टैक हमेशा "सही" रहें, या आलसी शिफ्ट चले? आलसी ही मानक अच्छा जवाब है।

३. पहले सोचो (एक स्टैक कम, दो जीतते हैं)

एक स्टैक अकेला क्यों काफी नहीं

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

हर डीक्यू पर पूरा स्टैक फिर से बना सकते हो (सब अस्थायी में, तली वाला लो, बाकी वापस)। काम करता है, पर हर डीक्यू ओ(एन)। पहली सोच ठीक; फिर औसत लागत बेहतर माँगते हैं।

दो स्टैक: न्यूएस्ट और ओल्डेस्ट

रखो:

  • stackNewest: हर नए तत्व को इनक्यू पर यहीं ले
  • stackOldest: ऐसे रखे कि उसकी चोटी कतार का अगला हो

इनक्यू: हमेशा stackNewest.push(x)। ओ(१)।

डीक्यू / पीक: सबसे पुराना चाहिए। वह stackOldest की चोटी पर है अगर पहले शिफ्ट हो चुका। अगर stackOldest खाली है, सारा stackNewest stackOldest में उड़ेलो:

while stackNewest is not empty:
    stackOldest.push(stackNewest.pop())

फिर stackOldest पर पीक या पॉप।

क्रम सही क्यों: इनक्यू क्रम 1, 2, 3 से न्यूएस्ट की चोटी=3, फिर 2, नीचे 1। शिफ्ट के बाद ओल्डेस्ट की चोटी=1, फिर 2, फिर 3। सही फाइफो।

आलसी नियम: शिफ्ट तभी जब stackOldest खाली हो। अगर ओल्डेस्ट पर अभी 1 है और तुम 4 इनक्यू करो, 4 न्यूएस्ट पर छोड़ो। अगला रिमूव अभी भी ओल्डेस्ट से 1 लेगा। जब ओल्डेस्ट खाली हो, बाद का रिमूव 4 (और साथियों) को खिसकाएगा।

औसत लागत की सहज समझ

हर तत्व न्यूएस्ट पर एक बार पुश होता है, न्यूएस्ट से अधिकतम एक बार पॉप, ओल्डेस्ट पर अधिकतम एक बार पुश, ओल्डेस्ट से अधिकतम एक बार पॉप। कतार में पूरे जीवन पर हर तत्व स्थिर काम चुकाता है। यही औसत ओ(१) प्रति संक्रिया है, भले एक शिफ्ट में एन चीज़ें एक साथ हिलें तो वह कॉल ओ(एन) लगे।

४. जावा हल

import java.util.EmptyStackException;
import java.util.Stack;

/**
 * Queue implemented with two stacks.
 * stackNewest: inbound (enqueue). stackOldest: outbound (dequeue/peek).
 * Shift only when outbound is empty and we need the front.
 */
class MyQueue {
    private final Stack<Integer> stackNewest = new Stack<>();
    private final Stack<Integer> stackOldest = new Stack<>();

    public int size() {
        return stackNewest.size() + stackOldest.size();
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    /** Enqueue: always push onto the newest stack. */
    public void add(int value) {
        stackNewest.push(value);
    }

    /**
     * Move everything from newest to oldest only if oldest is empty.
     * After this, stackOldest.top is the queue front (if any elements exist).
     */
    private void shiftStacks() {
        if (stackOldest.isEmpty()) {
            while (!stackNewest.isEmpty()) {
                stackOldest.push(stackNewest.pop());
            }
        }
    }

    /** Front without remove. Shifts if needed. */
    public int peek() {
        shiftStacks();
        if (stackOldest.isEmpty()) {
            throw new EmptyStackException(); // queue empty
        }
        return stackOldest.peek();
    }

    /** Dequeue front. Shifts if needed. */
    public int remove() {
        shiftStacks();
        if (stackOldest.isEmpty()) {
            throw new EmptyStackException(); // queue empty
        }
        return stackOldest.pop();
    }
}

चलकर देखो: add(1), add(2), add(3), फिर remove()।

कदम stackNewest (चोटी→…) stackOldest (चोटी→…) नोट
add(1) १ (खाली) न्यूएस्ट पर पुश
add(2) २, १ (खाली)
add(3) ३, २, १ (खाली)
remove → शिफ्ट (खाली) १, २, ३ न्यूएस्ट को ओल्डेस्ट में उड़ेलो
remove → पॉप (खाली) २, ३ 1 लौटता है

फिर add(4), remove():

कदम stackNewest stackOldest नोट
add(4) ४ २, ३ अभी शिफ्ट मत करो
remove ४ ३ ओल्डेस्ट पॉप → 2 (शिफ्ट नहीं; ओल्डेस्ट खाली नहीं)
remove ४ (खाली) पॉप → 3
remove → शिफ्ट (खाली) ४ अब शिफ्ट, फिर पॉप → 4

५. जटिलता तालिका

संक्रिया सबसे खराब समय औसत समय अतिरिक्त जगह
add ओ(१) ओ(१) प्रति कॉल ओ(१)
remove / peek (बिना शिफ्ट) ओ(१) ओ(१) ओ(१)
remove / peek (के चीज़ों का पूरा शिफ्ट) ओ(के) औसत ओ(१) स्टैक के अलावा ओ(१)
एन चीज़ों वाली कतार - - दोनों स्टैक मिलाकर ओ(एन)

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

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर इन्हें छूते हैं:

  • खाली कतार → दोनों स्टैक खाली पर remove / peek। फेंको या साफ संतरी लौटाओ। खाली स्टैक पर बिना जाँच pop मत करो।
  • एक तत्व → ऐड फिर रिमूव चलता है: शिफ्ट एक चीज़ लाता है, पॉप लौटाता है।
  • बहुत इनक्यू, फिर बहुत डीक्यू → एक बड़ा शिफ्ट, फिर सस्ते पॉप। क्रम फाइफो रहना चाहिए।
  • बिच-बिच में मिली संक्रियाएँ → आंशिक डीक्यू के बाद इनक्यू सामने को न तोड़े। आलसी शिफ्ट इसे संभालता है अगर ओल्डेस्ट खाली होने पर ही हिलाओ।
  • पीक फिर रिमूव → दोनों को एक ही सामने दिखे; पीक स्टैक असंगत न छोड़े (शिफ्ट ठीक; पीक पर पॉप नहीं)।
  • size / isEmpty → दोनों स्टैक जोड़ो। सिर्फ एक मत देखो।

आम गलतियाँ:

१. हर इनक्यू या हर डीक्यू पर शिफ्ट, भले ओल्डेस्ट भरा हो। काम बर्बाद, तोड़ना आसान। द्वार: if (stackOldest.isEmpty())। २. ओल्डेस्ट खाली न होने पर न्यूएस्ट उड़ेलना। क्रम मिल जाता है। ओल्डेस्ट में अभी पुरानी चीज़ें हैं; ऊपर नई डालना फाइफो तोड़ता है। ३. एक स्टैक और हर डीक्यू पर उलटी नकल, लागत बिना बताए। चलता है पर हर बार ओ(एन); दोनों तरफ़ बेपरवाह उलटाव में औसत कहानी नहीं बनती। ४. पीक को वही शिफ्ट भूलना जो रिमूव को चाहिए। पीक को भी ओल्डेस्ट की चोटी पर सामने चाहिए। ५. गलती से न्यूएस्ट से लौटाना। न्यूएस्ट की चोटी आखिरी आगमन है, पहला नहीं।

खाली-सुरक्षित छोटे सहायक (वही नीति):

public int removeOrThrow() {
    return remove();
}

public boolean tryPeek(int[] out) {
    if (isEmpty()) {
        return false;
    }
    out[0] = peek();
    return true;
}

७. दोस्त को समझाने वाला सार

दो स्टैक से कतार पूछती है: क्या सिर्फ लाइफो ढेरों से फाइफो मिल सकता है?

१. दो स्टैक रखो: नई पहुँच (stackNewest), परोसना (stackOldest)। २. इनक्यू हमेशा न्यूएस्ट पर पुश। यह ओ(१) है। ३. जब सामने चाहिए और ओल्डेस्ट खाली हो, न्यूएस्ट को ओल्डेस्ट में उड़ेलो। चोटियाँ उल्टती हैं, सबसे पहले आई चीज़ ओल्डेस्ट की चोटी पर बैठती है। ४. डीक्यू और पीक सिर्फ ओल्डेस्ट पर (संभव शिफ्ट के बाद)। ५. गैर-खाली ओल्डेस्ट पर कभी मत उड़ेलो। यही नियम क्रम बचाता है। ६. हर तत्व स्थिर बार हिलता है, इसलिए संक्रियाएँ औसत ओ(१) हैं, भले एक शिफ्ट महँगा दिखे।

दो ट्रे खींच सको, कब पलटना है बोल सको, और औसत लागत बिना धुंध के समझा सको, तो समस्या ३.४ तुम्हारी है।

सीरीज़