clase_05.md

Uso de stacks

supongamos que queremos realizar las siguientes operaciones:

1. agregar un elemento

2. quitar el ultimo elemento

3. consultar el minimo de todos los elementos actuales

para resolver este problema podemos aprovechar que cuando quedan i elementos en mi "stack" me interesa el minimo de los i primeros. esto lo podemos hacer solo manteniendo el minimo despues de cada insercion.

stack<int> myStack;

void add(int x) {
  if (myStack.empty()) myStack.push(x);
  else myStack.push(min(x, myStack.top()));
}

void pop() {
  myStack.pop(); 
}

int query() {
  return myStack.top();
}

previous minimum in array:

Dado un array de n enteros, para cada elemento en el array deseo hallar el elemento mas cercano que sea menor a dicho elemento y este a a la izquierda (imprimir el array de estos elementos, si todos los elementos a la izquierda son mayores, imprimir '?' sin las comillas).

ejemplo:

array inicial : [5, -1, 4, 3, 10, 8, 7, 1]

array final: [?, ?, -1, -1, 3, 3, 3, -1]

note que el -1 es el siguiente menor para 4, 3 y 1.

solucion: claro! este es otro problema con stack. Podemos mantener un stack de elementos decrecientes. y al agregar un elemento nuevo elimino todos los >= a ese elemento.

for (int i = i; i <= n; ++i) {
  cin >> arr[i];
}
stack<int> s;
for (int i = 1; i <= n; ++i) {
  while (not s.empty() and s.top() >= a[i]) s.pop();
  if (s.empty()) cout << "? ";
  else cout << s.top() << " ";
  s.push_back(a[i]);
}
cout << endl;

challenge: que sucede si ahora me piden el segundo previo menor en un array?

array inicial : [5, -1, 4, 3, 10, 8, 7, 1]

array final: [?, ?, ?, ?, 4, 4, 4, ?]

cualquier pregunta por slack.

como podria mantener el minimo en una queue?

solucion: claro! Esta tambien es un problema de stack.

podemos mantener dos stacks! uno que mantenga la respuesta en una variable a parte y otra que vacie la primera cuando hay que eliminar un elemento y esa esta vacia.

como funcionaria?

stack<int> l, r;
int rightMinimum = 2e9;

void add(int x) {
  rightMinimum = min(rightMinimum, x);
  r.push(x);
}

void erase() {
  if (not l.empty()) {
    l.pop();
    return;
  }
  while (not r.empty()) {
    if (l.empty()) l.push(r.top());
    else l.push(min(l.top(), r.top()));
    r.pop();
  }
  rightMinimum = 2e9;
}

int query() {
  if (not l.empty()) {
    return min(l.top(), rightMinimum);
  }
  return rightMinimum;
}