Найти максимум в стеке за время O(1)

Можно ли найти максимальный элемент в контейнере, в частности в стеке, не организуя дополнительного прохода по нему? Да, но за это, конечно, придётся заплатить дополнительным объёмом хранимой информации.

Идея состоит в том, чтобы вместе с элементом помещать в стек дополнительное поле "локального максимума", найденного к этому моменту.

Тогда нам остаётся вернуть при поиске максимума запись, находящуюся по фиксированному адресу памяти.

Можно было, наверное, попытаться обойтись и одной дополнительной переменной, включённой в класс стека, просто сравнивая с ней вставляемый элемент и, при необходимости, запоминая новый максимум. Но как быть при удалении элемента, совпадающего с максимальным, чтобы не делать нового прохода по стеку? Думаю, математика может помочь решить и эту проблему, подумайте над ней сами :)

Вот листинг консольной программы, решающей задачу с помощью поля "локального максимума". Проверялась она в Visual Studio 2015.

#include <iostream> 
#include <climits> 
using namespace std;

struct record {
 int val, currentMax; //Элемент и локальный максимум
};

class Stack {
private:
 struct record *data; //Указатель на данные стека
 int size, top; //Размер и вершина стека
public:
 Stack(int);
 void push(int);
 int pop();
 int max();
};

Stack::Stack(int n) { //Создать стек
 size = n;
 data = new record[n];
 top = -1;
}

void Stack::push(int n) { //Поместить элемент в стек
 if (top == size - 1) {
  cout << "stack is full" << endl; return;
 }
 top++;
 if (top == 0) {
  data[top].val = n;
  data[top].currentMax = n;
 }
 else {
  if (data[top - 1].currentMax > n) {
   data[top].val = n;
   data[top].currentMax = data[top - 1].currentMax;
  }
  else {
   data[top].val = n;
   data[top].currentMax = n;
  }
 }
 cout << n << " item was pushed in stack" << endl;
 return;
}

int Stack::pop() { //Удалить элемент из стека
 if (top == -1) {
  cout << "stack is empty" << endl; return INT_MAX;
 }
 int item = data[top].val;
 top--;
 cout << item << " item was popped from stack" << endl;
 return item;
}

int Stack::max() { //Найти максимум за время O(1)
 if (top == -1) {
  cout << "stack is empty" << endl; return INT_MAX;
 }
 cout << "maximum val in the stack is " << data[top].currentMax << endl;
 return data[top].currentMax;
}

int main() {
 Stack S1(5);

 S1.push(2);
 S1.push(6);
 S1.push(11);
 S1.push(3);
 S1.push(12);
 S1.max();
 S1.pop();
 S1.max();
 cin.get(); return 0;
}

01.04.2019, 09:05 [4251 просмотр]