ਅਧਿਕਤਮ ਸਟੈਕ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਸੇਬ ਲਿੱਟ ਉਬੇਰ
ਡਿਜ਼ਾਈਨ ਸਟੈਕ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ “ਮੈਕਸ ਸਟੈਕ” ਇਕ ਵਿਸ਼ੇਸ਼ ਸਟੈਕ ਨੂੰ ਡਿਜ਼ਾਈਨ ਕਰਨ ਲਈ ਕਹਿੰਦੀ ਹੈ ਜੋ ਇਹ ਕਾਰਜ ਕਰ ਸਕਦੀ ਹੈ:

  1. ਧੱਕਾ (x): ਇੱਕ ਤੱਤ ਨੂੰ ਸਟੈਕ ਵਿੱਚ ਧੱਕੋ.
  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) ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਵਿੱਚ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਪਾ ਸਕਦੇ ਹਾਂ.

ਪੌਪਮੈਕਸ ()

ਪੀਕਮੈਕਸ () ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਅਸੀਂ ਆਸਾਨੀ ਨਾਲ ਸਟੈਕ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਪਾ ਸਕਦੇ ਹਾਂ. ਇਸ ਲਈ ਅਸੀਂ ਸਟੈਕ ਤੋਂ ਤੱਤ ਨੂੰ ਪੌਪ ਕਰਾਂਗੇ ਅਤੇ ਇਸਨੂੰ ਬਫਰ ਸਟੈਕ ਵਿੱਚ ਧੱਕਾਂਗੇ. ਅਸੀਂ ਇਸਨੂੰ ਦੁਹਰਾਵਾਂਗੇ ਜਦੋਂ ਤੱਕ ਸਾਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਨਾ ਮਿਲੇ.

ਫਿਰ ਅਸੀਂ ਸਟੈਕ ਤੋਂ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਨੂੰ ਪੌਪ ਕਰਾਂਗੇ. ਇਸ ਤੋਂ ਬਾਅਦ ਅਸੀਂ ਬਫਰ ਸਟੈਕ ਵਿਚਲੇ ਸਾਰੇ ਤੱਤ ਆਪਣੇ ਅਸਲੀ ਸਟੈਕ ਵਿਚ ਤਬਦੀਲ ਕਰ ਦੇਵਾਂਗੇ.

ਕੋਡ

ਮੈਕਸ ਸਟੈਕ ਲਈ ਸੀ ++ ਕੋਡ

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. ਧੱਕਾ (x): ਓ (1) ਅਸੀਂ ਇਕੋ ਕਦਮ ਵਿਚ ਤੱਤਾਂ ਨੂੰ ਸਟੈਕ ਵਿਚ ਧੱਕ ਸਕਦੇ ਹਾਂ.
  2. ਪੌਪ(): ਓ (1) ਅਸੀਂ ਇਕੋ ਕਦਮ ਵਿਚ ਸਟੈਕ ਤੋਂ ਇਕ ਐਲੀਮੈਂਟ ਪੌਪ ਕਰ ਸਕਦੇ ਹਾਂ.
  3. ਸਿਖਰ (): ਓ (1) ਅਸੀਂ ਇਕ ਪੜਾਅ ਵਿਚ ਸਟੈਕ ਦੇ ਚੋਟੀ ਦੇ ਤੱਤ ਨੂੰ ਵਾਪਸ ਕਰ ਸਕਦੇ ਹਾਂ.
  4. ਪੀਕਮੈਕਸ (): ਓ (1) ਅਸੀਂ ਇਕ ਪੜਾਅ ਵਿਚ ਸਟੈਕ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਪਾ ਸਕਦੇ ਹਾਂ.
  5. ਪੌਪਮੈਕਸ (): ਓ (ਐਨ) ਸਭ ਤੋਂ ਮਾੜੇ ਮਾਮਲੇ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਸਟੈਕ ਦੇ ਤਲ 'ਤੇ ਹੋ ਸਕਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿਚ ਇਕੋ ਸਮੇਂ ਸਾਰੇ ਤੱਤ ਸਟੈਕ ਵਿਚ ਮੌਜੂਦ ਹੁੰਦੇ ਹਨ.