زیادہ سے زیادہ اسٹیک


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایپل لفٹ Uber
ڈیزائن اسٹیک

مسئلہ یہ بیان

"میکس اسٹیک" مسئلہ میں ایک خاص اسٹیک ڈیزائن کرنے کی ہدایت کی گئی ہے جو ان کاموں کو انجام دے سکتی ہے۔

  1. دھکا (ایکس): اسٹیک میں ایک عنصر کو دبائیں۔
  2. اوپر (): اسٹیک کے اوپری حصے میں والا عنصر لوٹاتا ہے۔
  3. پاپ (): عنصر کو اسٹیک سے ہٹا دیں جو سب سے اوپر ہے۔
  4. چیک میکس (): اسٹیک کا زیادہ سے زیادہ عنصر لوٹاتا ہے۔
  5. پاپ میکس (): اسٹیک سے زیادہ سے زیادہ عنصر کو ہٹانا اور اسے واپس کرنا۔

اگر اسٹیک میں متعدد زیادہ سے زیادہ عنصر شامل ہیں تو پھر کیلئے پاپ میکس () صرف ایک عنصر کو ہٹا دیں جو سرفہرست ہے۔

آخری چار کارروائیوں کے لئے ، یہ یقینی طور پر ہے کہ یہ اسٹیک خالی نہیں ہے ورنہ ان کارروائیوں کو نہیں بلایا جائے گا۔

مثال کے طور پر

push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

وضاحت

زیادہ سے زیادہ اسٹیک

نقطہ نظر

نقطہ نظر بہت آسان ہے. یہاں ہم ایک زیادہ سے زیادہ اسٹیک کو برقرار رکھیں گے جو اس میں زیادہ سے زیادہ عنصر کا پتہ لگائے گا ڈھیر لگانا اب تک. چونکہ تین کاموں کو شروع کرنا عام اسٹیک کی مدد سے ہوتا ہے لہذا ہمیں خاص طور پر آخری دو کارروائیوں کے لئے پروگرام کرنا ہے۔

چیک میکس ()

فرض کریں کہ ہمارے پاس اسٹیک ہے [5,2,3,6,8،5,5,5,6,8،1،XNUMX،XNUMX] لہذا ہم ایک اور اسٹیک کو برقرار رکھیں گے۔ اسے زیادہ سے زیادہ اسٹیک کا نام دیں جو اس عنصر تک زیادہ سے زیادہ ذخیرہ کرے گا۔ تو دیئے گئے اسٹیک کے ل our ، ہمارا زیادہ سے زیادہ اسٹیک [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] ہوگا۔ اس طرح ، ہم او (XNUMX) وقت کی پیچیدگی میں زیادہ سے زیادہ عنصر تلاش کرسکتے ہیں۔

پاپ میکس ()

چیک میکس () کا استعمال کرتے ہوئے ہم اسٹیک میں زیادہ سے زیادہ عنصر آسانی سے تلاش کرسکتے ہیں۔ لہذا ہم اسٹیک سے عناصر کو پاپ کریں گے اور اسے بفر اسٹیک میں ڈالیں گے۔ ہم اسے اس وقت تک دہرائیں گے جب تک کہ ہمیں زیادہ سے زیادہ عنصر نہ ملے۔

اس کے بعد ہم اسٹیک سے زیادہ سے زیادہ عنصر پاپ کریں گے۔ اس کے بعد ہم بفر اسٹیک میں موجود تمام عناصر کو اپنے اصل اسٹیک پر منتقل کردیں گے۔

ضابطے

زیادہ سے زیادہ اسٹیک کے لئے C ++ کوڈ

class MaxStack {
    public MaxStack() {
         stack<int> tmpStack, maxStack;
    }
    public void push(int x) {
        int max = maxStack.empty() ? x : maxStack.top();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        int tmp=tmpStack.top();
        tmpStack.pop();
        maxStack.pop();
        return tmp;
    }
    public int top() {
        return tmpStack.top();
    }
    public int peekMax() {
        return maxStack.top();
    }
    public int popMax() {
        int mx = peekMax();
        stack<int> buffer;
        while (tmpStack.top() != mx){
            buffer.push(tmpStack.top());
            tmpStack.pop();
        }
        while (!buffer.empty()){
            tmpStack.push(buffer.top());
            buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

زیادہ سے زیادہ اسٹیک کے لئے جاوا کوڈ

class MaxStack {
    Stack<Integer> tmpStack;
    Stack<Integer> maxStack;
    public MaxStack() {
        tmpStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        maxStack.pop();
        return tmpStack.pop();
    }
    public int top() {
        return tmpstack.peek();
    }
    public int peekMax() {
        return maxStack.peek();
    }
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<Integer>();
        while(tmpStack.top() != mx){
        	buffer.push(tmpStack.top());
        	tmpStack.pop();
        }
        while (!buffer.isEmpty()){
        	tmpStack.push(buffer.top());
        	buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

  1. دھکا (ایکس): O (1) ہم عناصر کو ایک قدم میں اسٹیک میں دھکیل سکتے ہیں۔
  2. پاپ (): O (1) ہم ایک قدم میں اسٹیک سے عنصر پاپ کرسکتے ہیں۔
  3. اوپر (): O (1) ہم ایک ہی قدم میں اسٹیک کے اوپری عنصر کو واپس کرسکتے ہیں۔
  4. چیک میکس (): O (1) ہم ایک ہی قدم میں اسٹیک میں زیادہ سے زیادہ عنصر تلاش کرسکتے ہیں۔
  5. پاپ میکس (): O (n) خراب صورتحال میں زیادہ سے زیادہ عنصر اسٹیک کے نچلے حصے میں ہوسکتا ہے۔

خلائی پیچیدگی

O (n) بدترین صورت میں تمام عناصر بیک وقت اسٹیک میں موجود ہیں۔