وڌ اسٽيڪ


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايپل ڪني سليمان وساڻ
ڊيزائن چتي

مسئلي جو بيان

مسئلو "ميڪس اسٽيڪ" بيان ڪندي هڪ خاص اسٽيڪ ٺاهي ٿو جيڪا انهن آپريشنن کي انجام ڏئي سگهي ٿي.

  1. ڌڪيو (x): ھڪڙي عنصر کي اسٽوري ۾ وڌو.
  2. مٿين () عنصر کي واپس ڏئي ٿو جيڪو اسٽيڪ جي چوٽي تي آهي.
  3. پاپ () عنصر کي اسٽيڪ مان هٽايو جيڪو مٿي تي آهي.
  4. peekmax (): اسٽيڪ جي وڌ کان وڌ عنصر کي واپس ڏئي ٿي.
  5. پاپماڪس (): وڌ ۾ وڌ عنصر کي اسٽيڪ مان ڪ andڻ ۽ ان کي واپس ڪرڻ.

جيڪڏهن اسٽيڪ ۾ وڌيڪ کان وڌيڪ عنصر شامل هجن ها پاپماڪس () صرف هڪ عنصر هٽايو جيڪو سڀني کان مٿاهون هجي.

آخري چار آپريشنن لاءِ ، ھي پڪ آھي ته اسٽيڪ خالي نه آھي ٻي صورت ۾ اھي آپريشن نه سڏيا ويندا.

مثال

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

وضاحت

وڌ اسٽيڪ

چرچو

طريقو بلڪل سادو آهي. هتي اسان وڌ کان وڌ اسٽيڪ کي برقرار رکنداسين جيڪا وڌ ۾ وڌ عنصر کي ٽريڪ ڏيندي اسٽيڪ اڃان تائين. شروع کان وٺي XNUMX آپريشن عام اسٽيڪ جي مدد سان آهن تنهنڪري اسان کي خاص طور تي آخري ٻن آپريشنن لاءِ پروگرام ڪرڻو آهي.

پئڪماڪس ()

فرض ڪيو ته اسان وٽ اسٽيڪ آهي [5,2,3,6,8،5,5,5,6,8،1،XNUMX،XNUMX] تنهن ڪري اسان هڪ ٻي اسٽيڪ کي برقرار رکنداسين. نالو ڏيو ان کي وڌ کان وڌ اسٽيڪ جي طور تي جيڪو ان عنصر تائين وڌ کان وڌ ذخيرو ڪندو. تنهنڪري ڏنل اسٽيڪ لاءِ ، اسان جي وڌ کان وڌ اسٽيڪ هوندي [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]. انهي طريقي سان ، اسان O (XNUMX) وقت جي پيچيدگي ۾ وڌ کان وڌ عنصر ڳولي سگهون ٿا.

پاپماڪس ()

پيڪماڪس () استعمال ڪندي اسان آساني سان اسٽيڪ ۾ وڌ کان وڌ عنصر ڳولي سگھون ٿا. تنهنڪري اسان عناصر کي اسٽيڪ مان پاپ ڪنداسين ۽ ان کي بفر واري اسٽيڪ ۾ دٻايو. اسين ٻيهر ورجائينداسين جيستائين اسان کي وڌ ۾ وڌ عنصر نه مليو.

پوءِ اسان اسٽيڪ مان وڌ کان وڌ عنصر پاپ ڪنداسين. ان کان پوء اسان سڀني عناصر کي بفر اسٽيڪ ۾ پنهنجي اصل اسٽيڪ ڏانهن منتقل ڪنداسين.

ڪوڊ

وڌ اسٽيڪ لاءِ سي ++ ڪوڊ

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

جاوا ڪوڊ Max Stack لاءِ

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. ڌڪيو (x): اي (1) اسان هڪ ئي قدم ۾ عناصر کي اسٽيڪ ۾ دٻائي سگهون ٿا.
  2. پاپ () اي (1) اسان هڪ درجي ۾ اسٽيڪ کان هڪ عنصر پاپ ڪري سگهون ٿا.
  3. مٿين () اي (1) اسان هڪ ئي قدم ۾ اسٽيڪ جي مٿين عنصر کي واپس ڪري سگهون ٿا.
  4. peekmax (): اي (1) اسان هڪ ئي قدم ۾ اسٽيڪ کي وڌ کان وڌ عنصر ڳولي سگهون ٿا.
  5. پاپماڪس (): اي (ن) بدترين حالت ۾ شايد وڌ ۾ وڌ عنصر اسٽيڪ جي تري ۾ هوندو.

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

اي (ن) خراب ترين صورتحال ۾ سڀ عنصر هڪ ئي وقت اسٽيڪ ۾ موجود آهن.