Cómo implementar una pila que pueda obtener eficientemente el valor máximo
1. Obtenga rápidamente el valor máximo de la pila
Estructura
Requiere dos matrices: una matriz stackItem almacena los elementos de la pila y la otra matriz. link2NextMaxValueIndex almacena el siguiente La posición del valor máximo
Dos punteros: uno es stackTop que apunta a la parte superior de la pila y el otro es maxValueIndex que apunta al subíndice del valor máximo
Operación
Al insertar: compare el tamaño del elemento insertado con el valor máximo. Si es mayor que el valor máximo, link2NextMaxValueIndex apunta a la posición del valor máximo original (es decir, maxValueIndex). maxValueIndex se convierte en la posición donde está insertado actualmente el elemento; de lo contrario, link2NextMaxValueIndex apunta a -1
Al eliminar: la posición del elemento eliminado está fuera. Si maxValueIndex es la misma que la posición actual, maxValueIndex es link2NextMaxValueIndex[. satckTop]
Devuelve el elemento más grande de la pila
Imagen
Tome empujar 2 7 1 y hacer estallar la pila como ejemplo:
#include
#include
#define MAX 100
usando el espacio de nombres std;
pila de clases
{
público:
pila() : stackTop( -1), maxValueIndex(-1) {}
void push( int val);
int pop();
int max();
int size() { return stackTop + 1 }
int vacío() { return pilaTop < 0 ? 1 : 0 }
privado:
p>
int stackItem[MAX];
int link2NextMaxValueIndex[MAX];
int stackTop;
int maxValueIndex;
};
void stack::push( int val)
{
++stackTop;
if(stackTop == MAX)
{
cout << "¡La pila ha estado llena!" << endl;
return;
}
else
{
stackItem[stackTop] = val;
if(max() < val)
{
link2NextMaxValueIndex[stackTop] = maxValueIndex;
maxValueIndex = stackTop;
}
else
link2NextMaxValueIn
dex[stackTop] = -1;
}
}
int pila::pop()
{
int ret;?
if(stackTop == -1)
{
cout << "¡La pila está vacía!" ;
return -1;
}
else
{
ret = stackItem[stackTop];
if(stackTop == maxValueIndex)
maxValueIndex = link2NextMaxValueIndex[stackTop];
--stackTop;
return ret;
}
}
int pila::max()
{
if(maxValueIndex >= 0 )
devuelve stackItem[maxValueIndex];
else
devuelve INT_MIN;
}
int main( )
{
pila s;
cout << "s.empty():" << s.empty() << endl;
s.push(3);
s.push(4);
cout << "s.top():" << s.pop( ) << endl;
cout << "s.top():" << s.pop() << endl;
cout << "s.top() :" << s.pop() << endl;
cout << "s.size():" << s.size() << endl;
cout << "s.empty():" << s.empty() << endl;
}
Resultado