حداکثر پشته


سطح دشواری ساده
اغلب در سیب چطوری حال بارگذاری
طرح پشته

بیان مسأله

مسئله "حداکثر پشته" برای طراحی یک پشته خاص است که می تواند این عملیات را انجام دهد:

  1. فشار (x): یک عنصر را به داخل پشته فشار دهید.
  2. بالا(): عنصری را که در بالای پشته است برمی گرداند.
  3. ترکیدن(): عنصر را از پشته ای که در بالا است بردارید.
  4. peekmax (): حداکثر عنصر پشته را برمی گرداند.
  5. popmax (): حذف بیشترین عنصر از پشته و برگرداندن آن.

اگر پشته شامل چندین عنصر حداکثر باشد ، برای popmax () فقط یک عنصر را که بالاترین است حذف کنید.

در چهار عملیات گذشته ، این اطمینان حاصل می شود که پشته خالی نیست در غیر این صورت این عملیات فراخوانی نمی شود.

مثال

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

توضیح

مکس پشته

روش

روش بسیار ساده است. در اینجا ما یک پشته حداکثر را حفظ خواهیم کرد که حداکثر عنصر موجود در آن را ردیابی می کند پشته تا حالا. از آنجا که شروع سه عملیات توسط پشته معمولی پشتیبانی می شود ، بنابراین ما باید به ویژه برای دو عملیات گذشته برنامه ریزی کنیم.

peekmax ()

فرض کنید ما پشته ای داریم [5,2,3,6,8،5,5,5,6,8،1،XNUMX،XNUMX] بنابراین پشته دیگری را حفظ خواهیم کرد. بگذارید آن را به عنوان حداکثر پشته نام ببرید که حداکثر مقدار آن را ذخیره می کند. بنابراین برای پشته داده شده ، حداکثر پشته ما [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] خواهد بود. به این ترتیب می توانیم حداکثر عنصر را در پیچیدگی زمانی O (XNUMX) پیدا کنیم.

popmax ()

با استفاده از peekmax () به راحتی می توانیم حداکثر عنصر را در پشته پیدا کنیم. بنابراین ما عناصر را از پشته پاپ خواهیم کرد و آن را به یک پشته بافر فشار خواهیم داد. این کار را تکرار می کنیم تا زمانی که بیشترین عنصر را پیدا کنیم.

سپس ما حداکثر عنصر را از پشته پاپ خواهیم کرد. پس از آن همه عناصر موجود در پشته بافر را به پشته اصلی خود منتقل خواهیم کرد.

رمز

کد ++ C برای Max Stack

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): O (1) ما می توانیم عناصر را در یک مرحله به درون پشته فشار دهیم.
  2. ترکیدن(): O (1) ما می توانیم یک عنصر را از پشته در یک مرحله جدا کنیم.
  3. بالا(): O (1) می توانیم عنصر بالای پشته را در یک مرحله برگردانیم.
  4. peekmax (): O (1) ما می توانیم حداکثر عنصر را در یک مرحله پیدا کنیم.
  5. popmax (): O (n) در بدترین حالت ممکن است حداکثر عنصر در پایین پشته باشد.

پیچیدگی فضا

O (n) در بدترین حالت همه عناصر همزمان در پشته وجود دارند.